Лучший контейнер для поиска и сортировки

Question

У меня есть чистый виртуальный класс для хранения данных журнала.Этот класс содержит две части информации: std::string id (уникальный) и int64_t time (допускаются дубликаты) с функциями getId() и getTime().Как только записи журнала будут созданы, они будут помещены в контейнер, и по завершении приложения сообщения журнала будут записаны в файл.искать id, чтобы найти правильную запись для обновления.При завершении работы я хочу, чтобы результаты регистрировались в time порядке.

Я думал о сохранении объектов в std::map, где id в качестве ключа, объект в качестве значения для удобного поискаи обновление.При завершении работы создайте std::multimap или std::vector, чтобы выполнить сортировку перед записью.Это лучший подход?Или есть лучший объект, который может удовлетворить обе потребности?

Answer 1

Контейнеры http://adrinael.net/containerchoice

(первоисточник: Лиам Девайн )

Answer 2

Поскольку вам нужно будет отсортировать записи по времени только один раз, при выходе из программы, я думаю, что предложенное вами решение хорошо.

Если вы хотите, чтобы записи сортировались по времени и идентификатору несколько раз, boost::multi_index будет хорошим кандидатом.

Answer 3

Если записи генерируются в порядке их time значений и , то time не изменяется при обновлении, чем вы можете просто:

• Добавить записи в std::vector<entry*> (или std::list<entry*>) по мере их создания.
• И также добавить их в std::map<std::string, entry*> (или std::unordered_map<std::string, entry*>).

map позволяет осуществлять быстрый поиск во время обновлений.Когда придет время вывести записи в файл, просто проследуйте по порядку std::vector.

(Существуют варианты, которые могут сэкономить некоторые кучи, например: std::vector<entry> и std::map<std::string, std::vector<entry>::size_type>, где size_type - индекс элемента вектора.)

Если, однако, вам также необходимо обновить time, я не думаю, что вы будетевозможность избежать использования std::multimap вместо std::vector.

- EDIT ---

OK, поэтому у вас нет порядка time, как насчет этого:

Поддерживать только один map<string, entry>, и когда придет время записать его в файл, сгенерировать из него vector< map<string, entry>::const_iterator > и std::sort на time (используйте comparer параметр std::sort).

Замечания:

• Вы также можете просто использовать vector<entry*> для сортировки - идея в том, что вы не выделяете никакихновые записи, вы просто «указываете» на записи в map.
• Также обратите внимание, что вы можете предварительно зарезервировать vector для соответствия map.size(), поэтому перераспределения векторов избегают.
• Если вам не нужна сортировка по идентификаторам записей, рассмотрите возможность использования unordered_map (вместо простого map) для повышения производительности.

В целом это дешевле, чем поддержаниевторой map, но добавляет задержку перед сбросом в файл.В зависимости от ваших требований к производительности, это может быть или не быть оптимальным решением.

Answer 4

Решение было бы иметь пару карт.Отслеживайте как map<string, entry*>, так и map<integer, entry*>.

. При обновлении вам потребуется выполнять поиск только по идентификатору и редактировать указанный объект.При извлечении всех записей из временной карты у вас будут измененные записи.Это предполагает, что значения id и времени для записей неизменны.

Answer 5

Вы можете использовать вектор для записей магазина. При создании вы можете назначить UID каждую запись, но вы можете использовать запись HANDLE, чтобы изменить элемент. HANDLE может быть указателем на запись или индексом массива. В этом случае вы получите O (1) сложность при входе. Также вам не нужна сортировка перед выводом журнала. массив уже отсортирован в порядке создания записи. Лучшее решение для создания статического массива входных структур с разумным размером. Это исключит использование динамической памяти.

Редактировать: перед выводом вы можете отсортировать этот массив, чтобы получить записи в порядке времени

Answer 6

stl::map все будет хорошо. И если я правильно помню, std::map реализован с бинарными деревьями под колпаком, поэтому он должен быть уже отсортирован, если вы перегрузите оператор operator<. Чтобы отсортировать карту по отметке времени, переопределите operator<, чтобы сравнить отметки времени.