существуют ли реализации списков, к которым можно обращаться по числовым порядковым индексам (0,1,2...),
применимы к ним операции удаления по произвольному индексу, и при этом и индексация и удаление выполняется за конечное количество итераций?

существуют, и называются "массивы"

только массивы не удовлетворяют условию "удаление"&&"конечное колич итераций" - весь хвост нужно перемещать на позицию назад.

Вашим условиям массивы с прямым доступом удовлетворяют. Потому что количество итераций конечно. 

Хэш-мап, например, с целым ключом. Правда, удаленный элемент образует дырку в индексации. Но зато все операции выполняются за постоянное время.

>Хэш-мап, образует дырку в индексации
теряется весь смысл. Смысл выполнять такую весчъ:
 
конечно можно и итераторами, но случаи бывают разные...

Итераторы как раз, более общи, чем индексы.
И ты уверен вообще, что паришься не зря, насчет стоимости удаления? У тебя что, несколько мильонов элементов?
Если нет, то расслабься и бери вектор (массив). Преждевременная оптимизация - одно их худших зол. 

Не стоит путать постоянное и конечное время исполнения

как раз миллионы значений и интересуют.

Осознал, что если не нужно сохранение порядка, то можно при удалении из центра на освободившееся пространство перемещать один элемент из конца списка.

Но алгоритм с сохранением порядка если кто придумает, то будет тоже гуд.

Под своим "конечное колич итераций" я подразумеваю, что время выполнения не должно расти линейно с размером списка. Максимум логарифмически. Извеняюсь, если где напутал с понятиями.

Это сообщение отредактировал(а) victor79 - 20.7.2010, 20:52

возможно, что-то дерево-образное может подойти

думаю, реализацию чего-то вроде std::set можно расширить, чтобы позволить доступ по индексу за логарифмическое время

за константу - вряд ли...

но вообще, лучше бы знать всю задачу
если это только, чтобы писать for(int c=0;... вместо for(std::set<T>::iterator..., то оно того не стоит

>если это только, чтобы писать for(int c=0;... вместо for(std::set<T>::iterator..., то оно того не стоит
оно того стоит, столько дополнительной писанины с объявлением этих итераторов, поиском где какой тип напутал, и вообще совместимость между разнотипными деревьями - это жуть.
Оно конечно по скорости может будет медленее (хотя вышеуказанная мной реализация вряд ли), но пока придумываешь
алгоритм, столько раз напишешь iterator, столько дополнительных мозготактов тратится, что жуть.
Плюс еще один плюсик - можно отслеживать процент выполнения без дополнительной считающей переменной.

>реализацию чего-то вроде std::set
это да, осталось только определиться, что за алгоритм.
Первые задумки были типа запоминать удаленные в отдельном множестве, но для этого нужно в дереве удаленных считать сколько там уже есть до этого элемента. Т.е. каждая ветка в удаленных должна знать, сколько в ней есть элементов. Если массивы на диске - то будет то что нужно, но для массивов в памяти пока не решился такую делать.

Ты просто не умеешь их готовить... дело опыта. Год-два хорошей практики, и тебя будет коробить от индексов. И путать ничего не будешь. Разыменованный итератор гораздо нагляднее, чем нагромождение скобок.

кто что умеет готовить, и что не умеет - это дело привычки. У меня одни блюда, у Вас другие... И мы никогда не узнаем, чье блюдо вкуснее(эффективнее), т.к. это зависит не только от повара, но и от потребителя, от времени вкушания, и от времени отведенного на вкушание, и от... да много от чего   
У меня эта задача ОТЧАСТИ для реализации списков в интерпретируемом языке, в котором итераторы будут совершенно излишни. Часть вещей решается через foreach, часть через перебор по индексу.

Если дерево будет хранить сколько элементов в каждой ветке, тогда все решается. При вставке элемента, всем родителям cnt_childs++, при удалении cnt_childs--, при получении по индексу... там чуть посложнее чем ++, но время выполнения укладывается в логарифмическое. Самого родителя при этом сохранять не нужно, так же как и в RedBlack, но на размер int cnt_childs все же будет увеличен каждый элемент.
Если нужен порядок перебора в порядке добавления, то индекс для дерева будет предыдущийИдентификатор+1 (этот идентификатор не уменьшаем при удалениях).
При наличии двух деревьев возможен перебор значений и по индексам-значениям (произвольный индекс), и по числовому индексу в порядке добавления, и по числовому индексу в порядке возрастания индекса-значения.

Решение найдено!!!  

Это сообщение отредактировал(а) victor79 - 22.7.2010, 22:24