Почему я никогда не буду использовать STL. (111 стр)

Lamer007
> > таки не нашлись реализации stl с skip list ?
> Да и не надо. Одни минусы, кроме быстрой итерации по элементам. И то, как мы не
> давеча выяснили, не на много быстрее...

есть тесты ? хотелось бы взглянуть

кстати, если распределены равномерно вроде как быстрее будет поиск чем по rb

innuendo
> есть тесты ?
тесты чего?

Lamer007
> > есть тесты ?
> тесты чего?

скорости, вставки\удаления\поиска

innuendo
> скорости, вставки\удаления\поиска
Я не видел таких тестов, тк не интересовало особо.

Ну судя по алгоритму skip_lists_map, мы получаем, 1)ограничение на число максимальных элементов коллекции с некоторым перерасходом памяти, либо 2)получаем алгоритмическую сложность поиска более чем О(log n), либо 3)вставка элементов периодически будет сопровождаться нехилым числом аллокаций О(n) памяти. Вот такие вот компромиссы...
Судя по всему, перерасход памяти в skip_list_map, по сравнением с деревом все равно есть.
Единственное, что радует - это перечисление элементов за О(n), но не сильно, ибо необходимость в этом встречается редко. И темболее это не нужно, ибо можно реализовать итерирование в дереве за O(n) через дерево + связанный список узлов дерева. Кстати, последний вариант перечисления элементов, если забить на сортированность элементов делается вообще без накладных расходов (по скорости), разве что лишняя трата памяти 2*sizeof(TItem*)*N.

Lamer007
> Единственное, что радует - это перечисление элементов за О(n)

Оно и в обычном дереве так.
Просто для отдельных элементов время может подскочить с единицы до логарифма.

TarasB
> Просто для отдельных элементов время может подскочить с единицы до логарифма.
Спасибо, мы это уже обсуждали, да.

Там еще хорошесть в локализации изменений при вставке (перебалансировать дерево - оно как-бы глобальней). Может дать профит при оргинизации потокобезопасных контейнеров (в жабе оно так и называется - ConcurrentSkipListSet/ConcurrentSkipListMap).

vladislav

есть тесты этого на C++ ?

апну, сравнивал кто-нибудь skip list и rbtree на практике ?

Xunter
> можешь загрузку с map<string, замерить. и протестить сколько займет просто
> загрузить нужные ресурсы - сравни разницу.
> у меня в 2 с небольшим раза загрузка быстрее стала. это без инплейса и из
> текстовых ресурсов.

это на каком примере загрузка в два раза быстрее стала ? что-то верится с трудом

Xunter
> во, расскажи о применении стл в играх - вообще и в S.T.A.L.K.E.R. в частности.
> и от чего Метро на консолях есть, а сталкера нету.
> может дураку и нафиг нож не нужен, если у него только кисель и гвозди? даже
> если нож хорош.

о ну как же как же, нашли stl в Метро то :)

innuendo
ты просто в силу умственных способностей не поймешь о чем тебе пишут.

Xunter
> ы просто в силу умственных способностей не поймешь о чем тебе пишут.

я в силу своих умственных способностей понимаю куда больше тебя :)

и кто начинает хамит ?

innuendo
> и кто начинает хамит ?
беги скорее жаловаться!!!

kas
> > и кто начинает хамит ?
> беги скорее жаловаться!!!

зажги про кошерные контейнеры