сортировка списка STL после всех откатов или просто использование Multimap?

Question

Мы использовали мультикартухранить несколько сотен тысяч элементов (> 300 КБ), когда мы поняли, что нам нужно добавить больше данных для анализа.Итак, мы создали класс, который содержал несколько элементов и необходимые переопределенные операторы для stl, и использовал мультикарту,Это работало нормально и не занимало намного больше времени, чем раньше (с некоторыми тестовыми данными), когда мы поняли, что stl будет работать нормально, если мы отсортировали его после того, как закончили добавлять все элементы.К нашему удивлению, мы обнаружили, что добавление всех элементов в мультикарту по-прежнему легко превосходит общее время добавления всех элементов в список, а затем сортировки.
Это не имеет смысла для типов EE, поскольку, по нашему мнению, каждая вставка вmultimap придется пройти по списку, а затем прикрепить его к концу, где, как и в случае со списком, мы просто добавим его в конец (путем возврата назад), тогда, надеюсь, сортировка не займет много времени.
Еще один фактоид: мы изначально провели сравнительный тест без сортировки списка и были рады увидеть значительное увеличение скорости при использовании списка.Потом мы добавили сортировку, и были немного ошеломлены ...
Кто-нибудь из гуру КС хочет взвесить?

Answer 1

std::multimap использует сбалансированное дерево ¹ , поэтому не пересекает весь список при вставке элемента.Количество элементов, пройденных для вставки, приблизительно равно логарифму числа 2 в коллекции из базовых 2.

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

---

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

Answer 2

Удалены ссылки на хеш. Сбалансированное дерево - это то, почему требуется только ход n2.