Comments 32
тут нет ни намёка на то что это перевод! Имхо приоритетным размером должна быть превьюшка страницы откуда взят перевод, указан автор оригинала, и вторым приоритетом указывать переводчика. Тогда станет видно кто автор а кто переводчик.
Одна маленькая ремарка, родом из опыта. Часто бывает так, что позарез нужна отсортированная структура данных с быстрым поиском. При этом, структура создаётся один раз и не изменяется за время своего существования. Например, список лайтмапов, отсортированный по названию или идентификатору. Или просто список объектов игровой вселенной с идентификаторами.
Решение, которое большинство выносит из подобных статей это map<Id, Object>. На самом деле, при разовом заполнении и многократном использовании оптимально: vector<Object>, отсортированный по Id, и доступ по std::lower_bound. Особенно, если примерный размер структуры известен заранее. Двоичный поиск это логарифмическая оценка скорости, а хеш-таблица — линейная. Но, как правило, константа при линейной скорости хеш-таблицы делает её медленнее (чем двоичный поиск) при приложении к малым и средним структурам. То есть, если у вас нет достаточно большого (обычно порядка 2^14) объектов — сортированный вектор лучше unordered_map. Если его не нужно изменять.
Наверное хотели сказать константная? (В среднем О(1)).
Там всё несколько сложнее.
В академическом смысле, конечно, O(1), но мы тут о новичках говорим. А новичкам лучше говорить про O(n), и вот почему.
Это чисто практический подход. Не единожды в проектах встречал людей, которые мне советуют unordered_map под предлогом, что он таки O(1), а моё решение O(log(n)). Всегда предлагал тащить бенчмарк. Не проигрывал. Ситуаций, в которых это будет реальный O(1) очень мало.
Специально по этому я написал «В среднем» =)
ИМХО, новичкам в любом случае надо рассказывать всю историю, что в среднем О(1), что в худшем О(n), что константа «скрытая» в О(f(n)) может очень серьезно менять всю картину, и что на практике огромное значение может иметь то, как алгоритм размещает данные в памяти (кэш/prefetch/количество разыменований).
К слову сказать, не пытались пройтись профилировщиком, чтобы понять проигрывает ли unordered_map из-за вырождения в О(n), или же из-за каких-нить особенностей реализации? Все таки в случае не очень большого числа элементов ваш алгоритм должен быть довольно cache friendly (как мне кажется)
Некоторые языки программирования, например, C++, работают со страницами памяти. Обычно страница занимает 4 килобайта. При использовании операторы добавления и удаления, размещается целая страница памяти, даже если вам нужно использовать только один байт.
Как-то подозрительно.
Это получается в старых дос программах нельзя было использовать более 150 объектов?
На практике, думаю, под BST подразумевают сбалансированные или в среднем сбалансированные деревья.
В любом случае, использовать "голое" дерево, как минимум, странно.
О выборе структур данных для начинающих