Эффективность stl::map of stl::sets

Question

Я полагаю, что я хотел бы использовать boost:: icl:: interval_map для решения проблемы (описано здесь, я опубликую полный ответ, если интервал_карты в конечном итоге сработают.)

Я хочу использовать interval_map<unsigned long long, set<foo*>>, но в документации для boost:: icl упоминается, что существуют потенциальные проблемы с эффективностью (ниже).

Мы представляем интервал_карты, используя карту интервалов наборов строк, из-за ее дидактических преимуществ. Пример партии используется, чтобы дать немедленный доступ к основным идеям карт интервалов и агрегировать на перекрытии. Для реальных приложений интервал_карта наборов не обязательно рекомендуется. Он имеет те же проблемы эффективности, что и std:: map для std:: sets. Тем не менее, существует большая область использования interval_maps с числовыми и другими эффективными типами данных для связанных значений.

Каковы проблемы эффективности с std:: map из std::sets? и как я могу их избежать?

Answer 1

И то и другое std::map<K, V> а также std::set<V> являются узлами на основе контейнеров, связанных указателями. Их обход имеет хорошие гарантии сложности (т. Е. Каждая отдельная операция не более O(log n)), но на самом деле вам нужны достаточно большие контейнеры для сложности по сравнению, например, с std::vector<std::pair<K, V>> особенно когда K а также V являются фундаментальными типами. Основная проблема производительности с контейнерами на основе узлов заключается в том, что они более или менее случайным образом размещаются в памяти, в то время как современные ЦП любят получать доступ к данным, которые в той или иной форме сгруппированы.

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