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

К>Здравствуйте, 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 и не получится.

Здравствуйте, 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, — до тех пор, пока не захотим работать с номерами элементов.