C ++ контейнер для проверки наличия упорядоченных данных в коллекции

Question

У меня есть данные, которые представляют собой набор упорядоченных целочисленных значений

[0] = 12345 [1] = 12346 [2] = 12454 и т.д.

Мне нужно проверить, есть ли значение в коллекции в C ++, какой контейнер будет иметь наименьшую сложность при извлечении? В этом случае данные не растут после инициализации. В C # я бы использовал словарь, в C ++ я мог бы использовать hash_map или set. Если бы данные были неупорядоченными, я бы использовал неупорядоченные коллекции boost. Тем не менее, у меня есть лучшие варианты, так как данные упорядочены? Спасибо

РЕДАКТИРОВАТЬ: размер коллекции составляет пару сотен предметов

Answer 1

Просто немного подробнее о том, что уже было сказано.

Сортированные контейнеры

Здесь неизменность очень важна: std::map и std::set обычно реализуются в виде двоичных деревьев (красно-черные деревья для моих нескольких версий STL) из-за требований к операции вставки, извлечения и удаления ( и особенно из-за признания недействительными требований итераторов).

Однако из-за неизменности, как вы и подозревали, есть и другие кандидаты, не в последнюю очередь из них контейнеры, похожие на массивы. У них здесь есть несколько преимуществ:

• минимальные накладные расходы (в плане памяти)
• смежность памяти и, следовательно, локальность кэша

Несколько «Контейнеров произвольного доступа» доступны здесь:

• Boost.Array
• std::vector
• std::deque

Таким образом, единственное, что вам действительно нужно сделать, может быть разбито за 2 шага:

• поместите все ваши значения в выбранный вами контейнер, затем (после того, как все будет вставлено) используйте std::sort для него.
• поиск значения с использованием std::binary_search со сложностью O (log (n))

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

Если вы не хотите изобретать велосипед, вы также можете проверить [AssocVector][1] у Александреску. Александреску в основном портировал интерфейсы std::set и std::map через std::vector:

• потому что быстрее для небольших наборов данных
• потому что это может быть быстрее для замороженных наборов данных

Несортированные контейнеры

На самом деле, если вы действительно не заботитесь о порядке и ваша коллекция довольно большая, тогда unordered_set будет быстрее, особенно потому, что целые числа так тривиальны для хеша size_t hash_method(int i) { return i; }.

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

Заключение

Просто попробуйте отсортированный std::vector подход и boost::unordered_set подход с "реальным" набором данных (и всеми оптимизациями на нем) и выберите тот, который даст вам лучший результат.

К сожалению, мы не можем больше помочь, потому что это сильно зависит от размера набора данных и перераспределения его элементов

Answer 2

Если данные находятся в упорядоченном контейнере с произвольным доступом (например, std::vector, std::deque или в виде простого массива), то std::binary_search определит, существует ли значение в логарифмическом времени. Если вам нужно найти, где это, используйте std::lower_bound (также логарифмический).

Answer 3

Используйте sort ed std :: vector и используйте std :: binary_search для его поиска.

Другими опциями будут hash_map (не в стандарте C ++ , но , но есть и другие варианты, например, hash_map SGI и boost :: unordered_map ) или std :: map .

Если вы никогда не добавляете в свою коллекцию, отсортированный вектор с binary_search, скорее всего, будет иметь лучшую производительность, чем карта.

Answer 4

Я бы предложил использовать std :: vector для их хранения и std :: binary_search или std :: lower_bound для их получения.

И std :: unordered_set, и std :: set увеличивают значительную нагрузку на память - и хотя unordered_set обеспечивает поиск O (1), двоичный поиск O (logn), вероятно, превзойдет его, учитывая, что данные хранятся непрерывно (нет указатель следует, меньше вероятность ошибки страницы и т. д.) и вам не нужно вычислять хеш-функцию.

Answer 5

Если у вас уже есть упорядоченный массив или std::vector<int> или аналогичный контейнер данных, вы можете просто использовать std::binary_search для проверки каждого значения. Время настройки не задано, но каждому датчику потребуется O (log n), где n - это количество упорядоченных целых чисел, которые вы получили.

В качестве альтернативы, вы можете использовать некоторый тип хеша, например boost::unordered_set<int>. Для этого потребуется некоторое время на настройку и, возможно, больше места, но каждый зонд в среднем займет O (1) времени. (Для малых n это O (1) может быть больше, чем предыдущее O (log n). Конечно, для малых n время в любом случае пренебрежимо мало.)

Нет никакого смысла смотреть на что-то вроде std::set или std::map, поскольку они не дают никаких преимуществ по сравнению с двоичным поиском, учитывая, что список совпадающих чисел не изменится после инициализации.

Итак, вопросы - это приблизительное значение n и сколько раз вы намереваетесь исследовать таблицу. Если вы не собираетесь проверять много значений, чтобы увидеть, находятся ли они в предоставленных целых числах, тогда время установки очень важно, и std::binary_search в отсортированном контейнере - путь. Если вы собираетесь проверять множество значений, возможно, стоит настроить хеш-таблицу. Если n большое, хеш-таблица будет быстрее проверять, чем бинарный поиск, и если много проб, это основная стоимость.

Итак, если число сравниваемых чисел достаточно мало или число значений зондов мало, перейдите к двоичному поиску. Если число ints велико, а число зондов велико, используйте хеш-таблицу.