Здравствуйте, uzhas, Вы писали:

U>Здравствуйте, Аноним, Вы писали:

А>>какие могут быть еще варианты ?
U>могу предложить два варианта: boost::flat_map, aurgmented RB-tree с подсчетом детей справа и слева (за основу можно взять что-ни будь такое: http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm )


Для boost::flat_map вроде хуже чем с vector получается

вставка : log n
удаление : log n
проход : n*log(n)

мат ожидание сложности для boost::flat_map
(при условии что вставка, удаление, проход равновероятны + вставка и удаление порождают проход)

E = (log n + n*log(n)) *0,33 + (log n + n*log(n) )*0,33 + n*log(n)*0,33 = n*log(n) + 0.66*n

мат ожидание сложности для контейнера на основе std::vector
(при условии что вставка, удаление, проход равновероятны + вставка и удаление порождают проход)

E = (n*log(n) + n) *0,33 + (n*log(n)+ n)*0,33 + n*0,33 = 0.66*n*log(n) + n

для
>>для aurgmented RB-tree с подсчетом детей справа и слева
пока не вкурил как построить алгоритм