<это не домашнее задание, просто образования нормального нету, а жизнь заставляет програмульки писать>
Такая задача: перебраем КУЧУ (M) (около 10^9 объектов) и держим N (между 100 и 1000) лучших из них. Очевидно, что список лучших должен (хотя-бы) время от времени сортироваться. Такие варианты:
а. держать stl::multimap<object_type, int> (int -dummy) - он всё время сортирован, вставляя каждый новый объект, стераем последний. Плюсы - простота использования. Минусы - время: каждый insert берет (если память не подводит) log(N) времени (и того - MlogN).
б. stl::list<object_type>. Набрать 2*N элементов, отсортировать, отбросить последние N, набрать заново, отсортировать .... . (+): мало сортировок. сортировки быстрые, но... (-): отброс последних элементов - log(N)
в. тоже самое, но с std::vector. (+): быстрый отброс (-): сортировка медленнее чем в list-е, и жрет больше памяти (последнее - не очень важно).
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.