Распределение памяти в std :: map

Question

Я делаю отчет о различных реализациях словаря C ++ (карта, словарь, векторы и т. Д.).

Результаты для вставок с использованием std :: map показывают, что производительность равна O (log n). Есть также последовательные всплески в исполнении. Я не уверен на 100%, что является причиной этого; Я думаю, что они вызваны распределением памяти, но мне не удалось найти какую-либо литературу / документацию, чтобы доказать это.

Кто-нибудь может прояснить этот вопрос или указать мне правильное направление?

Приветствие.

Answer 1

Вы правы: это O (log n) сложности. Но это связано с отсортированной природой карты (обычно основанной на двоичном дереве).

Также см. http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html есть примечание на вкладыше. В худшем случае это O (log n) и амортизированный O (1), если вы можете намекнуть, где делать вставку.

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

Answer 2

Если я правильно помню, std :: map - это сбалансированное красно-черное дерево. Некоторые из пиков могут быть вызваны, когда std :: map определяет, что базовое дерево нуждается в балансировке. Кроме того, при выделении нового узла ОС может вносить вклад в некоторые пики во время части выделения.

Answer 3

Эмпирический подход не является строго необходимым, когда дело доходит до STL. Нет смысла экспериментировать, когда стандарт четко диктует минимальную сложность операций, таких как вставка std :: map.

Я призываю вас прочитать стандарт, чтобы вы знали о минимальных гарантиях сложности, прежде чем продолжать эксперименты. Конечно, могут быть ошибки в любой реализации STL, которую вы тестируете; но популярные STL - довольно хорошо отлаженные существа и очень широко используемые, так что я сомневаюсь в этом.