Alex_VCВопрос такой: имеется некоторое множество (map) в котороя я добавляю элементы <ключ,значение>. Так вот если добавляемые ключи заведомо упорядочены (например, <1,"sss">,<2,"fff">,<4,"sdfs">,...), то не превратится ли множество в список (т.е. добавление элементов будет идти по одной ветке):

<1,"sss">
\
<2,"fff">
\
<4,"sdfs">
И поиск в данном множестве из логарифмической сложности превратится в линейную ? Или все-таки множества устроены по-другому (в виде, например, сбалансированного бинарного дерева). Но тогда получается при каждом добавлении элемента необходимо перестраивать дерево?

Спасибо за внимание...

Да, добавление данных по порядке возрастание ключей будет приводить к баллансировке дерева после каждого добавления. С поиском будет сооотвественно всё нормально, а вот добавление элементов будет долгим.

Alex_VCПардон, речь идет об отображениях (день тяжелый, после праздника...)

Я тебя понял :) На самом деле для множеств тоже самое - это ведь считай просто набор ключей ;)

Alex_VCТ.е., получается, быстрее будут вставляться неупорядоченные значения ключей, т.к. при упорядоченной вставке (когда вставляемый эл-т всегда больше имеющихся) дерево каждый раз будет перестраиваться?

В принципе да, хотя это не совсем полная перестройка дерева.