Вопрос по stl, c++ – Оптимизирован ли контейнер карт STL (сбалансированное дерево) при его создании?

4

Если я вставлюordered (увеличивая) последовательность элементов в карте, будет ли как-то оптимизировано конечное двоичное дерево? Или у каждого элемента будет дочерний элемент "по отношению к нему"? Это сделало бы такое дерево очень неэффективным, так какthen поиск будет линейным.

Я не смог найти никакой подробной информации о процессе вставки в карту STL.

@HWende: Если вы хотите знать, прочитайте код STL, вы можете скачать его бесплатно. Если вы говорите о стандартной библиотеке c ++, а не о stl, то вам следует прочитать конкретную реализацию, которую вы используете. Это может быть реализовано по-разному, и хотя rb-деревья являются наиболее распространенными, вы наверняка найдете разные реализации, например. скиплисты, авл деревья, б деревья ... PlasmaHH
Вы оба очень правы. Часто люди склонныrely на эту информацию - хотя я просто хотел знать. :-) HWende
Это строго зависит от реализации, и вам не следует полагаться на специфическое поведение реализации, если вы не беспокоитесь о переносимости. Вы должны полагаться только наbehavior чтоstd::map должен выставляться. Alok Save
@Als Существует различие между «положением о поведении, специфичном для имплементации»; и зная, как поведение реализуется с точки зрения понимания. Benj
@Benj: И по этой причине я разместил его в качестве комментария. Вы возражаете против этого? Alok Save

Ваш Ответ

5   ответов
23

ихinsert а такжеfind для ассоциативных контейнеров. Построение их из двух итераторовi а такжеj такой, что[i, j) обозначает соответственно отсортированный диапазон значений, который требуется для линейной сложности по времени. Означает ли это, что «окончательное двоичное дерево оптимизировано», или же карты являются бинарными деревьями вообще, не указывается.

На практике, однако,std::set, std::map и их мульти-друзья фактически всегда красно-черные деревья, поскольку это то, что исходная эталонная реализация HP / SGI STL имела, и все современные библиотеки C ++, которые я знаю, происходят от этой реализации.

+1 Потому что он отвечает на вопрос в рамках спецификаций стандартов.
@larsmans: но преимущество их использования заключается в лучшей локализации памяти, которую вы потеряете, если добавите еще один уровень косвенности. Вот почему я считаю, что стабильность не должна быть частью базовых требований (это никак не связано со сложностью), и пользователь должен сам решать, нужна ли ему эта дополнительная косвенность.
@MatthieuM .: Я пришел к такому же выводу относительно. отображать деревья и списки пропусков, но еще не думал о B-деревьях. Я подозреваю, B-дерево или 2-3 дереваcan быть использованы за счет дополнительного уровня косвенности, однако.
@MatthieuM .: правда. Тем не менее, я понимаю требование стабильности, потому что библиотека позволяет хранить произвольно большие структуры вstd::map; в специализированном контейнере, таком как карта указателей, это требование может быть снято.
@larsmans: на практикеstd::map реализованы как двоичные деревья (красно-черные или avl) из-за нескольких ограничений: 1. Запрещено отключать звук при доступеconst методы, 2. Элементы должны быть стабильны в памяти. Недавно я спрашивал об использовании skip-списков, но, видимо, они работали хуже. Splay Trees нарушает1B деревья (и варианты) нарушает2, Оглядываясь назад, я думаю, что2 должен был быть оспорен, так как B-деревья обеспечивают лучшую производительность (больше памяти, следовательно, больше кеша).
1

ента в std :: map (23.4.4.3 ISO / IEC 14882), поэтому std :: map должен быть реализован в виде самобалансирующегося дерева.

0

Взгляни наРуководство программиста стандартной библиотеки шаблонов SGI, Вы найдете следующие спецификации сложности для вставки и поиска элементов:

Average complexity for insert range is at most O(N * log(size() + N)), where N is j - i. Average complexity for find is at most logarithmic.
В этой конкретной реализации библиотеки STL, которая не является стандартной библиотекой.
@PlasmaHH Я думаю, что STL все еще является исключением. Довольно часто люди говорят "STL" и они означают «бит стандартной библиотеки C ++ с контейнерами, алгоритмами и тому подобными шаблонами»;
@PlasmaHH, но документы SGI относятся к SGI STL, который не полностью соответствует стандартной библиотеке C ++. Я предполагаю, что OP имел в виду стандартную библиотеку, а не STL ...
@juanchopanza: Но это / / STL. В прошлый раз, когда я проверял стандарт, ничего не определялось под названием STL.
@juanchopanza: Ну, я (и некоторые другие, вероятно, тоже) предполагаю, что OP означает STL. Возможно, потому что ОП упоминает STL ... Довольно часто люди имеют в виду X, когда говорят X. Если только они не девочки. Но это становится оффтопом сейчас.
3

std::map реализовано с использованием красно-черного дерева, которое является самобалансирующимся. Так что да, это оптимизировано.

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

Подача отсортированных данных в самобалансирующееся дерево ВСЕГДА требует, чтобы при его создании тратилось много времени на перебалансировку, поэтому 2-й оператор неверен. Для больших наборов данных лучше, если возможно, читать их случайным образом.
Ну, что ж, спасибо! Есть ли у вас ссылки на эту информацию? (без обид!) HWende
@HWende никто не взял. У меня нет ссылки, потому что ее реализация определена. Вот почему я сказал "в общем". Стандарт гарантирует некоторые временные ограничения, поэтому вы определенно получите не O (n) для вставки или удаления, а O (log (n)).
0

set а такжеmap  поэтому find - это O (log n). Многие из операций & apos; сложности показаны здесь: http://www.cplusplus.com/reference/stl/

Повезло тебе. :-)
Мой набор и карта не выполняют балансировку деревьев, поскольку они не являются деревьями ....

Похожие вопросы