Оптимизирован ли контейнер карт STL (сбалансированное дерево) при его создании?

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

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

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

Ответы на вопрос(5)

Решение Вопроса

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

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

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

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

Взгляни наРуководство программиста стандартной библиотеки шаблонов 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.
 03 мая 2012 г., 14:09
@PlasmaHH Я думаю, что STL все еще является исключением. Довольно часто люди говорят "STL" и они означают «бит стандартной библиотеки C ++ с контейнерами, алгоритмами и тому подобными шаблонами»;
 03 мая 2012 г., 13:54
@PlasmaHH, но документы SGI относятся к SGI STL, который не полностью соответствует стандартной библиотеке C ++. Я предполагаю, что OP имел в виду стандартную библиотеку, а не STL ...
 03 мая 2012 г., 13:52
@juanchopanza: Но это / / STL. В прошлый раз, когда я проверял стандарт, ничего не определялось под названием STL.
 03 мая 2012 г., 13:57
@juanchopanza: Ну, я (и некоторые другие, вероятно, тоже) предполагаю, что OP означает STL. Возможно, потому что ОП упоминает STL ... Довольно часто люди имеют в виду X, когда говорят X. Если только они не девочки. Но это становится оффтопом сейчас.
 03 мая 2012 г., 11:34
В этой конкретной реализации библиотеки STL, которая не является стандартной библиотекой.

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

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

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

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

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

Ваш ответ на вопрос