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

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

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

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

Cheers.

источник

2009-02-08 Anonymous

Я думаю, что поведение сильно зависит от реализации (поскольку STL не указывает, как он должен реализовываться только в том, как он должен использоваться). – mmmmmmmm

@restevens - это не так, есть определение того, как должен себя вести STL (то есть, что должно быть для больших типов вывода каждого типа контейнера). – ChrisW

@rstevens: Это неправильно. Контейнеры STL определяются с точки зрения гарантий сложности различных операций. –

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

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

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

источник

2009-02-08 16:07:30 kmkaplan

Первоначально я думал, что шипы вызваны вращением дерева, но всплески не появляются, пока на карту не будет добавлено 50 000 предметов. После этого числа шипы происходят последовательно (приблизительно) каждые 25 000 предметов после этого, каждый из которых соответствует по величине. – 2009-02-09 11:13:42

Я отвечаю поздно, но это может быть полезно: балансировка может выполняться при каждой вставке с минимальным количеством операций, поэтому пики в моей догадке - это перераспределения, которые выполняются, когда объем памяти, предварительно выделенный для элементов . – Gui13

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

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

источник

2009-02-08 16:01:22

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

источник

2009-02-08 16:04:10

GCC реализация std :: map на самом деле красно-черное дерево. Я считаю, что MS VS также использует красно-черное дерево, но я не уверен в этом на 100%. Спайки, скорее всего, будут перебалансировать дерево. – paxos1977

ответ

Смежные вопросы