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

R>Здравствуйте, c-smile, Вы писали:

CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу. А над O(log N) — вообще сплошное надругательство.

R>Так ведь никто и не обещал, что O(1) ВСЕГДА будет быстрее O(log N), а O(log N) ВСЕГДА быстрее O(N). Потому, что все эти оценки задают лишь асимптотику зависимости времени выполнения от размера входной последовательности, но не являются точной зависимостью. Они позволяют лишь говорить о том, что существует такой размер входной последовательности, свыше которого O(1) начинает выигрывать у O(log N), а O(log N) у O(N). А вот каким будет этот размер, зависит уже от...

Ну собственно об этом и речь. Это все про эту вот цитату:

Практик: "Если он вызывается не один раз, то очевидно что std::map будет эффективнее, т.к. инициализация дерева будет происходить только один раз. И это кстати не теория — я использую на практике именно такой подход (только со string_view, а не string в качестве ключа для map)."