Повышение квалификации: посоветуйте литературу

Алгоритмы в STL ХОРОШИЕ. По крайней мере, асимптотическая сложность у них наилучшая из возможных.

А теперь прикинь. У тебя есть набор каких-то объектов. Что тебе нужно, чтобы отыскать в этом наборе нужный тебе объект за O(ln n)? Ответ: тебе нужна сортировка или что-то более сильное. Что более сильное? Ну, скажем, хэш-таблица, она тебе даст даже O(1). Кроме того, если уж у тебя есть сортировка, то тебе нужен O(1)-доступ к элементу.

Вот и смотри, кто из этих контейнеров отсортирован (и для кого это вообще имеет смысл), кто даёт O(1)-доступ, кто даёт хэш-таблицу.

кто даёт O(1)-доступ, кто даёт хэш-таблицу.

Яндекс троллит соискателей, спрашивает за O(ln n), а не O(ln n) или быстрее. К тому же, по поводу хеша, сложно сказать какая сложность гарантируется, т.к. неизвестно есть ли коллизии и как они обрабатываются.

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

прокомментируйте правильность постановки вопроса

Основной вопрос закопан тут.

Ответ: тебе нужна сортировка или что-то более сильное.

Нафига? Сбалансированного дерева хватит.

Сбалансированного дерева хватит.

это и есть «сортировка». Дерево отсортировано by design, т.к. каждый эл-т встаёт на своё место сразу.

«Сбалансированное» не нужно, главное — не вырожденное. (т.е. что-бы число уровней не росло быстрее, чем какой-нить log(N)).

Это и есть «более сильное, чем сортировка».

Ну, скажем, хэш-таблица, она тебе даст даже O(1).

О боже, о божечки. Эти нули. Ты понимаешь, что хештаблица - это массив, а хеш она лишь потому, что в массиве индекс должен быть целочисленный. Хеш даёт только индекс с равномерным распределением по твоему ключу.

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

Длину массива можно уменьшить делением массива - на этом основаны все хеш-массивы. Но деление массива покупается за ещё один поиск по подмассиву.

Т.е. это уже не O(1). Длину можно уменьшить коротким хешом, но короткий хеш это коллизии, а коллизии это тот же самый ещё один поиск.

Т.е. в реальном хеше нет единицы, так же как в бревне нет логарифма. То, о чем ты балаболишь - это перфектхеш.

Молодец, возьми с полки пирожок. В игнор ты пока не отправляешься по причине недавнозарегистрированности, но комментарий «зазнайка» ты заработал.

тычо! этож Царь!

Ты царя не признал? :)

Кого?

Царя! Ну. :)

Путина, что ли?

Эээ, ну практически. :) Только этот умеет шикарной статься на Лоре, пожалуй это и все. :)

тычо! этож Царь!

не, не царь. Царь не так говорил.

Мне реально интересно, почему нулёвая балаболка, которая меня даже под анонимусом не узнаёт, позволяет себе делать такие выводы?

Какбэ любой модератор тебе подтвердит, что я Царь по мылу. Ибо мыло у царьблогов и текущего царя составлено по одному шаблону, только там были номера меньше. А царь мыла с царьблогов нигде не светил.

Ну и обоссанный емулек - первый признак царя.

Какбэ любой модератор тебе подтвердит

что ты у модератора отсасал? Извини, я не в курсе. Я жеж не модератор, у меня отсасёшь, я тебе ещё и не то подтверждать буду.