Что такое контейнер C ++ с операцией «Содержит»?

Question

Я хочу использовать структуру, в которую я вставляю целые числа, а затем могу спросить

if (container.contains(3)) { /**/ }

Должно быть что-то вроде этого.

Answer 1

Вы можете использовать std::vector.

std::vector<int> myVec;
myVec.push_back(3);
if (std::find(myVec.begin(), myVec.end(), 3) != myVec.end())
{
    // do your stuff
}

Вы можете даже сделать небольшую вспомогательную функцию:

template <class T>
bool contains(const std::vector<T> &vec, const T &value)
{
    return std::find(vec.begin(), vec.end(), value) != vec.end();
}

Вот как бы вы его использовали:

if (contains(myVec, 3)) { /*...*/ }

Answer 2

Простой алгоритм:

template <typename Container>
bool contains(Container const& c, typename Container::const_reference v) {
  return std::find(c.begin(), c.end(), v) != c.end();
}

Вы можете настроить его для более эффективного поиска в некоторых известных контейнерах:

template <typename Key, typename Cmp, typename Alloc>
bool contains(std::set<Key,Cmp,Alloc> const& s, Key const& k) {
  return s.find(k) != s.end();
}

template <typename Key, typename Value, typename Cmp, typename Alloc>
bool contains(std::map<Key,Value,Cmp,Alloc> const& m, Key const& k) {
  return m.find(k) != m.end();
}

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

Answer 3

find для несортированного вектора - O (n).

std::set поддерживает O (log n) вставок и поисков и является хорошим выбором.

std::tr1::unordered_set предоставляет аналогичный интерфейс, но поддерживает поиск почти в постоянное время.Это лучший выбор, если у вас TR1 (или C ++ 0x) и вам не нужно перечислять элементы по порядку.

Answer 4

То, что вы хотите, это метод find_first_of из библиотеки алгоритмов.(или бинарный поиск, или что-нибудь в этом духе)

http://www.cplusplus.com/reference/algorithm/find_first_of/

Answer 5

Если вы хотите использовать стандартный контейнер C ++, из-за его конструкции сами контейнеры не обязательно имеют «содержит», но вы всегда можете использовать алгоритм поиска.

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

Для правильного ознакомления с контейнерами и алгоритмами в стандартной библиотеке C ++ смотрите http://www.cplusplus.com

Контейнеры , Алгоритмы

Если, как вам кажется, ваши данные состоят из уникальных элементов, для которых вы хотите связать значение, вы, вероятно, будете хорошо обслуживаться контейнером карты. Если все, что вас волнует, это «членство», тогда set - лучший выбор.