Re[14]: std::set::find медленней std::set::insert
От: sokel Россия  
Дата: 21.08.09 06:07
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Каждый узел дерева — это значение, три указателя и флажок. Хороший аллокатор позволит экономно расходовать кучу, но ты его сперва ещё сделай, этот аллокатор...


Можно выделить всё сразу — вектор нод + intrusive::set. Вообще сделать дерево с двумя указателями на ноду. Parent по большому счёту не очень нужен, при вставке-балансировке можно хранить текущую ветку на стеке. А цвет при этом паковать в left или right. Тогда потребуется максимум n*3*sizeof(void*) дополнительной памяти. Всего на треть больше, чем для quicksort. А если уж совсем память не расходовать, тогда можно и пузырьком пройтись

К>Алюминиевая пуля?


Вроде того в худшем случае будет не намного прожорливей, чем quicksort. Зато в лучшем даст фору.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.