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

AD>тут можно идею доп деревьев чуть поподробнее ? без учета нагрузки на фрагментацию памяти
AD>какой из показателей вставка , удаление , проход улучшиться ?

Если хранить размеры поддеревьев, то скорость произвольного доступа по индексу из линейной (std::advance(begin,N)) превратится в логарифмическую.
Спрашивать у гугля, ясеня и рсдн ключевое слово "augmented red black tree"

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


NB>у тебя какой-то неправильный дек.
NB>наши деки обычно реализованы через вектор чанков.

И что это даёт при вставке с раздвижкой в случайное место?

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

E>Здравствуйте, night beast, Вы писали:


NB>>у тебя какой-то неправильный дек.
NB>>наши деки обычно реализованы через вектор чанков.

E>И что это даёт при вставке с раздвижкой в случайное место?

тупанул. чето думал, что чанки могут быть частично заполненными.

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

А>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

А>на первый взгляд 2 решения
А>1) std::vector , после вставки /удаления сортируемся

Если уж так вот очень надо делать так, то лучше тогда не сортbроваться, а сдвигать "хвост" вектора, пока не найдёшь место для вставки...

Ну, что-то типа

std::vector<XXX> v;

if( v.size() == 0 || to_add > v.back() ) {
    v.push_back( to_add );
} else {
    v.push_back( v.back() );
    std::vector<XXX>::iterator i = v.end();
    for( i -= 2; i != v.begin() && i[-1] > to_add; --i ) {
        *i = i[-1];
    }
    *i = to_add;
}

Или, если думаешь, что swap для типа элемента работает быстрее копирования:

v.push_back( to_add );
for( std::vector<XXX>::iterator i = v.end() - 1; i != v.begin() && i[-1] > *i ; i-- ) {
    assert( *i == to_add );
    std::swap( i[-1], *i );
}

и то и то -- О(N), а не O(N ln N), как в случае с сортировкой после вставки...

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

А>Всем добрый день!!

А>какие могут быть еще варианты ?

avlarray

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

А>3) итератор произвольного доступа (нужен проход по сортированному содержимому)

А зачем для прохода итератор произвольного доступа?

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

А>теперь о частоте вызова операций
А>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

Или, если наблюдается реальный провал производительности, — придётся изгаляться.
Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...

Кстати, зачем нужен произвольный доступ к упорядоченной коллекции?
Не исчерпывается ли он быстрым поиском и последовательным доступом в окрестностях найденных элементов?

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

NB>деку можно попробовать.
А что это даст?

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

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


E>Если второе, то моет просто можно приделать в модель механизм кэширования позиции и строить инекс не на всю коллекуию. а только на нужную часть? Ну там постранично, например?

да я впринципе уже так и сделал
т.е. я ввел преположение что при сканированиии он запрашивает элементы последовательно. i, i+1 , ... i+k

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

E>Здравствуйте, night beast, Вы писали:

NB>>деку можно попробовать.
E>А что это даст?
кода не подходит std::vector или std::map, говорят "попробуй деку"

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


NB>>тупанул. чето думал, что чанки могут быть частично заполненными.

E>Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать

ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое

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

_>А что значит в наивном исполнении и в дополненном? Я так понимаю, доступ за логарифм, перебрать все элементы в произвольном порядке O(n), итого O(n*logn). Откуда квадратичная сложность?

Доступ не по ключу, а по индексу. В наивном исполнении это std::advance(begin,n) — линейный забег КАЖДЫЙ раз.
В дополненном — если в дереве есть информация об индексах, то — как обычно, за логарифмическое время спуск от корня до нужного листа.

_>Если обход прыжками, то надо брать hash_map, будет О(n). Заодно и вставка-удаление-одиночный доступ более быстрыми будут.

Обход прыжками — это если в алгоритме даже используется arr[k], arr[k+1], arr[k+2], — но мы-то не догадываемся, что arr[k+1] запрошен сразу после arr[k] и вынуждены честно прыгать по-новой.

Да, и не надо вестись на поводу стереотипов.
У топикстартера не ассоциативный, а просто упорядоченный контейнер.
Понятно, что упорядоченность нахаляву получается в set/map/multi_index, — до тех пор, пока не захотим работать с номерами элементов.

Всем добрый день!!

Мне необходим контейнер с поддержкой следующих операций

1) вставка элемента
2) удаление элемента
3) итератор произвольного доступа (нужен проход по сортированному содержимому)

теперь о частоте вызова операций
предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

на первый взгляд 2 решения
1) std::vector , после вставки /удаления сортируемся
2) std::map ,но тут придется эмулировать итератор при помощи std::advance

Сравнение сложности операций
vector : map
вставка: n*log(n) , log(n)
удаление: n*log(n) , log(n)
проход: n , n*n

отсюда я делаю вывод выбрать 1 вариант.

какие могут быть еще варианты ?

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

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

Здравствуйте, 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 с подсчетом детей справа и слева
пока не вкурил как построить алгоритм

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

А>>теперь о частоте вызова операций
А>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

К>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

деку можно попробовать.

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

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

А>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

А>>на первый взгляд 2 решения
А>>1) std::vector , после вставки /удаления сортируемся

E>Если уж так вот очень надо делать так, то лучше тогда не сортbроваться, а сдвигать "хвост" вектора, пока не найдёшь место для вставки...

E>Ну, что-то типа

E>std::vector<XXX> v;

E>if( v.size() == 0 || to_add > v.back() ) {
E>    v.push_back( to_add );
E>} else {
E>    v.push_back( v.back() );
E>    std::vector<XXX>::iterator i = v.end();
E>    for( i -= 2; i != v.begin() && i[-1] > to_add; --i ) {
E>        *i = i[-1];
E>    }
E>    *i = to_add;
E>}

Или, если думаешь, что swap для типа элемента работает быстрее копирования:

E>v.push_back( to_add );
E>for( std::vector<XXX>::iterator i = v.end() - 1; i != v.begin() && i[-1] > *i ; i-- ) {
E>    assert( *i == to_add );
E>    std::swap( i[-1], *i );
E>} 
E>

E>и то и то -- О(N), а не O(N ln N), как в случае с сортировкой после вставки...

Да , это хороший вариант , наверное он мне подходит

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

К>Кстати, зачем нужен произвольный доступ к упорядоченной коллекции?
т.к. есть сторонний фреймверк которому надо скормить данные
а работает он по схеме
1) сколько дашь элементов
2) дай такой то элемент

К>Не исчерпывается ли он быстрым поиском и последовательным доступом в окрестностях найденных элементов?
спасибо за совет . я подумаю

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


К>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

это по сути то про что писал Егор , чуть выше.
вставка n
удаление n
проход n


К>Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...
тут можно идею доп деревьев чуть поподробнее ? без учета нагрузки на фрагментацию памяти

какой из показателей вставка , удаление , проход улучшиться ?

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

NB>Здравствуйте, Кодт, Вы писали:

А>>>теперь о частоте вызова операций
А>>>предполагается что каждый вызов , вставки/удаления влечет за собой полный проход по сортированному контейнеру (при помощи итератора произвольного доступа) это одно из условий!!!

К>>Тогда сортированный вектор, вставка в середину (поддержание упорядоченности). Это будет стоить O(N), но, поскольку там всё равно сразу же грядёт полный проход по коллекции, то это не страшно.

NB>деку можно попробовать.

в моем случае не катит

вставка n
вырезание n
проход с учетом произвольного доступа n*n

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

AD>Для boost::flat_map вроде хуже чем с vector получается
виноват, имелся в виду flat_set и его сложность совпадает с sorted array, т.к. по сути это он и есть

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

ссылка по теме: http://www.rsdn.ru/forum/cpp.applied/5380434.flat#5380434

Автор: kolobok55
Дата: 02.12.13

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

К>Или, если наблюдается реальный провал производительности, — придётся изгаляться.
К>Дополненные двоичные деревья (там, правда, нагрузка на менеджер кучи и на фрагментацию памяти — т.е. это не cache-friendly), B±деревья всякие...
1) зато у них есть плюс : элементы не копируются при вставке\удалении других элементов
2) кастомные аллокаторы решают проблему фрагментациии памяти и локализации данных. есть в бусте и в студии >=2012, #include <allocators>

при оценке сложности алгоритмов желательно учитывать кол-во копирований элементов, это может критически повлиять на общую производительность
стратегий передвигания элементов в sorted array может быть несколько (зависит от типа данных):
1) поэлементное копирование
2) поэлементный move \ swap
3) групповой memmove

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

AD>Да , это хороший вариант , наверное он мне подходит
Рад, что помог.
Если я верно понял о чём речь, то тебе после добавления, надо ещё и всё просканировать. Возможно можно циклы совместить, но это имеет смысл только для очень длинного вектора, который в кэш не лезет, иначе получишь усложнение кода без всякой пользы.

В любом случае, если ты расскажешь, зачем нужно сканировать ветор после добавления, и зачем нужен итератор с произвльным доступом, а не двунаправленный например, то может тебе что-то более глобальное тут подскажут.
Например, если произвольный доступ нужен только для +- 1..2, то может оказаться более быстрым std::list, хотя в целом он более медленный. В общем если расскажешь больше, могут дать более хороший совет.

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

NB>>деку можно попробовать.
E>А что это даст?

чуть быстрее вектора с некоторых случаях работает.

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

NB>чуть быстрее вектора с некоторых случаях работает.
Ну эти "некоторые случаи", в основном, сводятся к добавлению/удалению в начало, а это вроде как не особо надо ТС...
Тут, скорее, может стоило бы посмотреть в сторону какой-то деревянной коллекции с индексом в векторе, который строится,перестраивается по требованию и, возможно, по кускам.

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

то есть, например, если у нас в узле дерева, скажем красно-чёрного будет лежать число элементов в поддереве, а само дерево будет на указателях + прошитое + на отдельном непрерывном аллокаторе, что бы данные по куче не размазывать, то, доавление/удаление элемента будет не сильно дороже, а в результате процедуры добавления/удаления, получим сразу и число элементов ДО модифицируемого элемента + быстрый индекс в векторе, куда вставки будут на memmove'ах...
Правда получим лишнюю косвенность при запросе элемента по индексу. В общем, если я верно понял задачу ТС, ему это не надо...

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

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

AD>>Да , это хороший вариант , наверное он мне подходит
E>Рад, что помог.
E>Если я верно понял о чём речь, то тебе после добавления, надо ещё и всё просканировать. Возможно можно циклы совместить, но это имеет смысл только для очень длинного вектора, который в кэш не лезет, иначе получишь усложнение кода без всякой пользы.

E>В любом случае, если ты расскажешь, зачем нужно сканировать ветор после добавления, и зачем нужен итератор с произвльным доступом, а не двунаправленный например, то может тебе что-то более глобальное тут подскажут.
E>Например, если произвольный доступ нужен только для +- 1..2, то может оказаться более быстрым std::list, хотя в целом он более медленный. В общем если расскажешь больше, могут дать более хороший совет.

есть некий фреймверк который отображает items
для этого ему (фреймверку ) я должен передать model из которой он извлечет данные

class CModel
{
public:
    size_t count();
    TItem  data(size_t index);
}

дальше он показывает показывает model.
соответственно данные добавляются новые / удаляются / редактируются (при всем этом должен поддерживаться сортировка)
вот как то так.
Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные

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

E>Здравствуйте, night beast, Вы писали:


E>например, если у нас будет какое-то дерево, которое по элементу быстро умеет получить номер в упорядоченной последовательности, и в качествеитератора, позволяет использовать указатель на узел, то можно было бы иметь дерево с данными + индекс в виде вектора итераторов узлов. Тогда после добавления, мы сразу бы получали и место в индексе, куда надо вставить новый итератор...

правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?

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

AD>Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные
а он реально сканирует все данные хаотично при таком апдейте? А то может, например, у него есть там какой-то курсор, который он как-топ озиционирует, и потом он от курсора просто получает скока ему надо итемов подряд?
Если второе, то моет просто можно приделать в модель механизм кэширования позиции и строить инекс не на всю коллекуию. а только на нужную часть? Ну там постранично, например?

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

AD>есть некий фреймверк который отображает items
AD>для этого ему (фреймверку ) я должен передать model из которой он извлечет данные


AD>

AD>class CModel
AD>{
AD>public:
AD>    size_t count();
AD>    TItem  data(size_t index);
AD>}
AD>

AD>дальше он показывает показывает model.
AD>соответственно данные добавляются новые / удаляются / редактируются (при всем этом должен поддерживаться сортировка)
AD>вот как то так.
AD>Соответственно после каждой каждой модификации данный модуль отображения должен перерисовать данные

в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке
нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку
для этой задачи самый простой set может подойти

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

AD>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?
Нет, не правильно.
1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать.
2) Дерево может быть и с индексом.

Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...

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

U>в данной постановке можно было бы вообще отказаться от поиска по index, т.к. мы заранее знаем, что индексы будут подсовываться в возрастающем порядке
U>нам достаточно внутри хранить некий итератор, который будет инкрементиться после вызова data(index). можем ассерты вставить на то, что индексы подсовываются по порядку
U>для этой задачи самый простой set может подойти

Зачем assert'ы?
Лучше обработать + дебаг-средство по сбору статистики...

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

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

AD>>правильно я понимаю что как только возникает дерево , то сразу произвольный доступ по индексу мы выполняем за log n ?
E>Нет, не правильно.
E>1) "произвольный доступ" может быть не таким уж и произвольным. Например, может быть какой-то важный паттерн доступа, который и надо оптимизировать.
E>2) Дерево может быть и с индексом.

E>Ещё раз говорю, что пусть у меня в каждом узле хранится число узлов в растущем из этого узла поддереве. Тогда операции "промотать 100500 элементов влево/вправо" и апдейты индекса тоже могут оказаться существенно дешевле...

может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)
Или после выполнения поиска , мы запоминаем позицию в дереве ,и просто следующий поиск мы как то начинаем с запомненой позиции и учитываем доп инфу в узлах ?

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

NB>>чуть быстрее вектора с некоторых случаях работает.
E>Ну эти "некоторые случаи", в основном, сводятся к добавлению/удалению в начало, а это вроде как не особо надо ТС...
E>Тут, скорее, может стоило бы посмотреть в сторону какой-то деревянной коллекции с индексом в векторе, который строится,перестраивается по требованию и, возможно, по кускам.

у тебя какой-то неправильный дек.
наши деки обычно реализованы через вектор чанков.

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

AD>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)

Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д...
Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко...
Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...

просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.

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

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

AD>>может я конечно туплю , но промотать 100500 элементов мы все равно только за логарифмическое время можем? (начинаем с головы)

E>Ну, если дерево прошитое, то есть узлы хранят указатели на родителей, то ходить можно вообще локально. Типа идём всё время вниз влево, пока можем, потом начинаем выходить наружу и сворачивать правее, при возможности, и т. д...
E>Конечно иногда мы будем подниматься на несколько узлов, но в среднем это даст О(1) на узел, а в худшем O9( ln N ), и, довольно таки редко...
E>Мало того, если на надо не на один влево/вправо, а например, на 100, то использую инфу о размере поддеревьев, это дело можно сильно оптимизировать, так как можно проматывать узлы сразу поддеревьями...

E>просто нарисуй дерево, как граф на бумажке, и подумай, как написать алгоритм, который позволяет перейти от любого узла к следующему при переборе в ширину или в глубину, например, и всё поймёшь.

ок , спасибо я понял принцип ))

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


NB>тупанул. чето думал, что чанки могут быть частично заполненными.

Обычно такой "дек" называют B-дерево Только тогда уж выгоднее его невырожденным делать

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

NB>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое

Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически, то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...

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

NB>>ну, В-дерево -- это все же дерево, а тут вложенность всего одна будет. недодерево такое

E>Ну, в целом, да. Но если у нас число элементов в чанке всё равно непредсказуемое, то есть смысл искать нужную чанку не линейно, а логарифмически,

да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.

E>то есть такую структуру данных логичнее немного допилить и получить не вырожденное B-дерево, а обычное...

хз. возможно.

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

NB>да. в чанке хранить индекс первого элемента. тогда и поиск будет логарифмический. но при инсерте придется все чанки апдейтить.
Зачем так сложно? B-дерево, почти такое же сложное, но работать будет лучше

NB> хз. возможно.

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

А>Сравнение сложности операций
А> vector : map
А>вставка: n*log(n) , log(n)
А>удаление: n*log(n) , log(n)
А>проход: n , n*n

Если что, полный обход мэпа std::map это О(n), а не О(n*n).

А>отсюда я делаю вывод выбрать 1 вариант.
А>какие могут быть еще варианты ?

Я так и не понял, для чего тебе это надо.
Опиши плз саму задачу.

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

_>Если что, полный обход мэпа std::map это О(n), а не О(n*n).

Это если обход последовательный. А если прыжками в произвольную точку, то — в наивном исполнении он такой же, как у списка, т.е. O(n*n), а в дополненном — O(n*logn).

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

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

_>>Если что, полный обход мэпа std::map это О(n), а не О(n*n).

К>Это если обход последовательный. А если прыжками в произвольную точку, то — в наивном исполнении он такой же, как у списка, т.е. O(n*n), а в дополненном — O(n*logn).

А что значит в наивном исполнении и в дополненном? Я так понимаю, доступ за логарифм, перебрать все элементы в произвольном порядке O(n), итого O(n*logn). Откуда квадратичная сложность?

Если обход прыжками, то надо брать hash_map, будет О(n). Заодно и вставка-удаление-одиночный доступ более быстрыми будут.

Ну и там в исходном третьем пункте была фраза такая: "3) итератор произвольного доступа (нужен проход по сортированному содержимому)" — я это понял как:
3а) нужен доступ к произвольному элементу,
3b) нужен последовательный обход по возрастанию/убыванию элементов,
т.е. пункт распадается на два. И из-за последовательного обхода как раз-таки hash_map и не получится.