Лучший контейнер STL для быстрого поиска

Question

Мне нужно сохранить список целых чисел и очень быстро определить, есть ли целое число в списке.Никакие дубликаты не будут сохранены.

Я не буду вставлять или удалять любые значения, но я буду добавлять значения (которые могут быть реализованы как вставка).

Какой контейнер STL является лучшимкласс для этого?Я нашел std::multimap в Google, но мне, кажется, требуется пара ключ / значение, которой у меня нет.

Я довольно новичок в STL.Могу ли я получить некоторые рекомендации?

Answer 1

Вместо карты вы можете использовать набор, когда значение и ключ не разделены.

Вместо мультимножества / -карты вы можете использовать не мульти-версию, которая не хранит дубликаты.

Вместо набора у вас есть std::unordered_set в качестве альтернативы. Это может быть быстрее для вашего случая использования.

Существуют и другие, менее общие структуры данных, которые можно использовать для представления наборов целых чисел, и некоторые из них могут быть более эффективными в зависимости от варианта использования. Но эти другие структуры данных не обязательно предоставляются вам стандартной библиотекой.

Но мне не ясно, у кого самый быстрый поиск.

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

вряд ли превысит тысячу или около того

В этом случае асимптотическая сложность не обязательно актуальна.

Специально для таких небольших наборов отсортированный вектор может быть весьма эффективным. Учитывая, что вы «не будете вставлять или удалять какие-либо значения» , вектор также не должен иметь существенных недостатков. Стандартная библиотека не предоставляет контейнер набора, реализованный внутри с использованием отсортированного вектора, но она обеспечивает контейнер вектора, а также все необходимые алгоритмы.

Я не знаю, как контейнеры вычисляют хэши.

Вы можете предоставить хеш-функцию для неупорядоченного контейнера. По умолчанию используется std::hash. std::hash использует хеш-функцию, определенную реализацией.

Answer 2

std::unordered_set<int> - хороший выбор для отслеживания дубликатов int с, поскольку как вставка, так и поиск могут быть достигнуты в среднем за постоянное время.

---

Вставка

Вставка нового int в коллекцию может быть достигнута с помощью функции-члена insert():

std::unordered_set<int> s;
s.insert(7);

Lookup

Проверка наличия в коллекции данного int может быть выполнена с помощью функции-члена find():

bool is_present(const std::unordered_set<int>& s, int value) {
   return s.find(value) != s.end();
}