Как узнать, присутствует ли элемент в std :: vector?

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

if ( item_present )
   do_this();
else
   do_that();
20.02.2009 21:58:41
поиск в векторе очень медленный, так как вы должны смотреть на каждый элемент вектора, поэтому рассмотрите возможность использования карты, если вы выполняете много поисков
naumcho 20.02.2009 22:31:54
@naumcho: если вектор отсортирован, всегда есть бинарный поиск, как показано ниже. Это делает его таким же быстрым, как карта, и если вы храните только значения (а не карты ключ / значение), тогда он будет использовать намного меньше памяти.
Adam Hawes 21.02.2009 01:01:17
Карты, конечно, не лучший выбор, но использование набора может быть полезным. Если вам нужно время поиска O (1), лучше использовать hash_set.
Philipp 8.10.2010 08:58:51
Превосходный ответ присутствует на дублирующийся вопрос: stackoverflow.com/a/3451045/472647
CodeMouse92 18.06.2015 03:11:20
Если вы собираетесь искать разные числа несколько раз, хеш-таблица будет более эффективной.
NL628 25.11.2017 02:26:45
19 ОТВЕТОВ
РЕШЕНИЕ

Вы можете использовать std::findот <algorithm>:

#include <vector>
vector<int> vec; 
//can have other data types instead of int but must same datatype as item 
std::find(vec.begin(), vec.end(), item) != vec.end()

Это возвращает bool ( trueесли присутствует, в falseпротивном случае). С вашим примером:

#include <algorithm>
#include <vector>

if ( std::find(vec.begin(), vec.end(), item) != vec.end() )
   do_this();
else
   do_that();
901
4.04.2019 10:57:12
Я не понимаю, как count () может быть быстрее, чем find (), поскольку find () останавливается, как только найден один элемент, а count () всегда должен сканировать всю последовательность.
Éric Malenfant 21.02.2009 03:29:18
Не забывайте, #include <algorithm>иначе вы можете получить очень странные ошибки, такие как «не могу найти подходящую функцию в пространстве имен std»
rustyx 2.03.2012 15:46:58
Разве это никого не беспокоило, что, несмотря на то, что STL является «объектно-ориентированным», .find()он все еще не является функцией-членом std::vector, как и следовало ожидать? Интересно, это как-то является следствием шаблонов?
bobobobo 7.12.2012 02:33:56
@bobobobo: ООП не имеет ничего общего с членами или не членами. И широко распространено мнение, что если что-то не обязательно должно быть членом или когда оно не дает никаких преимуществ при реализации в качестве участника, то оно не должно быть членом; std::vector<>::find()не даст никакого преимущества, и при этом он не нужен, поэтому нет, он не должен быть членом. См. Также en.wikipedia.org/wiki/Coupling_%28computer_programming%29
Sebastian Mach 4.02.2013 13:54:50
@phresnel Я бы сказал, что «когда он не дает никаких преимуществ при реализации в качестве члена», в этом случае ложь. Преимущество заключается в упрощенном и понятном интерфейсе. Например: mvec.find(key) != mvec.cend()предпочтительнее std::find(mvec.cbegin(), mvec.cend(), key) != mvec.cend().
swalog 29.04.2015 20:09:55

Используйте find из заголовка алгоритма stl. Я проиллюстрировал его использование с типом int. Вы можете использовать любой тип, который вам нравится, если вы можете сравнить на равенство (перегрузка ==, если вам нужно для вашего пользовательского класса).

#include <algorithm>
#include <vector>

using namespace std;
int main()
{   
    typedef vector<int> IntContainer;
    typedef IntContainer::iterator IntIterator;

    IntContainer vw;

    //...

    // find 5
    IntIterator i = find(vw.begin(), vw.end(), 5);

    if (i != vw.end()) {
        // found it
    } else {
        // doesn't exist
    }

    return 0;
}
46
29.04.2017 14:37:03
В зависимости от потребностей OP, find_if () также может быть подходящим. Это позволяет искать, используя произвольный предикат вместо равенства.
Éric Malenfant 20.02.2009 22:12:29
К сожалению, ваш комментарий слишком поздно. Ответ, который я дал, также упоминает find_if.
Frank 20.02.2009 22:19:36

Используйте функцию поиска STL .

Имейте в виду, что есть также функция find_if , которую вы можете использовать, если ваш поиск более сложный, т.е. если вы не просто ищете элемент, но, например, хотите посмотреть, существует ли элемент, который удовлетворяет определенному условие, например, строка, которая начинается с "abc". ( find_ifдаст вам итератор, который указывает на первый такой элемент).

8
20.02.2009 22:18:34

Как уже говорили другие, используйте STL findили find_ifфункции. Но если вы ищете в очень больших векторов , и это влияет на производительность, вы можете сортировать вектор , а затем использовать binary_search, lower_boundили upper_boundалгоритмы.

112
20.10.2012 19:27:12
Хороший ответ! Найти всегда о (п). lower_bound равен o (log (n)), если используется с итераторами с произвольным доступом.
Stephen Edmonds 8.07.2009 19:54:45
Сортировка - это O (nlogn), поэтому она стоит только если вы выполняете больше, чем O (logn) поиск.
liori 15.06.2014 00:48:07
@liori Правда, это зависит от ваших моделей использования. Если вам нужно отсортировать его только один раз, а затем многократно выполнять поиск, это может спасти вас.
Brian Neal 17.06.2014 16:24:40
@ Брайан Нил, сортировка большого вектора стоит того, чтобы на нем было много элементов поиска. Сортировка будет O (nlogn) и O (n) будет лучше, если нужно найти элемент только один раз :)
Swapnil B. 11.03.2018 18:17:51

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

std :: vector является контейнером выбора, если у вас нет причины для другого, и поиск по значению может быть такой причиной.

10
20.02.2009 22:42:36
Даже при поиске по значению вектор может быть хорошим выбором, если он отсортирован и вы используете binary_search, lower_bound или upper_bound. Если содержимое контейнера изменяется между поисками, вектор не очень хорош из-за необходимости повторной сортировки.
Renze de Waal 20.02.2009 22:49:20

Вы можете попробовать этот код:

#include <algorithm>
#include <vector>

// You can use class, struct or primitive data type for Item
struct Item {
    //Some fields
};
typedef std::vector<Item> ItemVector;
typedef ItemVector::iterator ItemIterator;
//...
ItemVector vtItem;
//... (init data for vtItem)
Item itemToFind;
//...

ItemIterator itemItr;
itemItr = std::find(vtItem.begin(), vtItem.end(), itemToFind);
if (itemItr != vtItem.end()) {
    // Item found
    // doThis()
}
else {
    // Item not found
    // doThat()
}
5
28.04.2012 15:29:48

Если ваш вектор не упорядочен, используйте подход, предложенный MSN:

if(std::find(vector.begin(), vector.end(), item)!=vector.end()){
      // Found the item
}

Если ваш вектор упорядочен, используйте метод binary_search, предложенный Брайаном Нилом:

if(binary_search(vector.begin(), vector.end(), item)){
     // Found the item
}

Бинарный поиск дает O (log n) производительности в худшем случае, что намного эффективнее, чем первый подход. Чтобы использовать бинарный поиск, вы можете использовать qsort, чтобы сначала отсортировать вектор, чтобы гарантировать его упорядоченность.

39
9.07.2016 12:07:38
Ты имеешь в виду std::sort? qsortочень неэффективно для векторов .... см .: stackoverflow.com/questions/12308243/…
Jason R. Mick 16.08.2013 01:57:14
Бинарный поиск будет работать лучше для больших контейнеров, но для небольших контейнеров простой линейный поиск, вероятно, будет таким же быстрым или быстрым.
BillT 31.03.2017 14:07:02

Если вы хотите найти строку в векторе:

    struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}

    bool operator()(OIDV* l)
    {
        return l->oid == m_s;
    }

    std::string m_s;
};
struct OIDV
{
    string oid;
//else
};
VecOidv::iterator itFind=find_if(vecOidv.begin(),vecOidv.end(),isEqual(szTmp));
2
31.05.2013 13:55:53

Я использую что-то вроде этого ...

#include <algorithm>


template <typename T> 
const bool Contains( std::vector<T>& Vec, const T& Element ) 
{
    if (std::find(Vec.begin(), Vec.end(), Element) != Vec.end())
        return true;

    return false;
}

if (Contains(vector,item))
   blah
else
   blah

... так оно и есть на самом деле понятно и читаемо. (Очевидно, вы можете повторно использовать шаблон в нескольких местах).

21
9.01.2014 23:11:10
и вы можете заставить его работать для списков или векторов, используя 2 typenames
Erik Aronesty 3.03.2015 15:36:52
@ErikAronesty вы можете обойтись без 1 аргумента шаблона, если вы используете value_typeиз контейнера для типа элемента. Я добавил ответ как этот.
Martin Broadhurst 11.02.2016 21:40:34
template <typename T> bool IsInVector(T what, std::vector<T> * vec)
{
    if(std::find(vec->begin(),vec->end(),what)!=vec->end())
        return true;
    return false;
}
1
26.01.2014 17:55:40

Вы можете использовать findфункцию, найденную в stdпространстве имен, то есть std::find. Вы передаете std::findфункцию, beginи endитератор из вектора вы хотите найти, наряду с элементом вы ищете и сравнить полученный итератор к концу вектора , чтобы увидеть , если они совпадают или нет.

std::find(vector.begin(), vector.end(), item) != vector.end()

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

3
15.06.2014 00:36:20

Вы можете использовать счет тоже. Он вернет количество элементов, присутствующих в векторе.

int t=count(vec.begin(),vec.end(),item);
3
17.04.2015 06:18:37
findбыстрее, чем count, потому что он не продолжает считать после первого матча.
Camille Goudeseune 16.08.2015 20:27:27

В C ++ 11 вы можете использовать any_of. Например, если это vector<string> v;тогда:

if (any_of(v.begin(), v.end(), bind(equal_to<string>(), _1, item)))
   do_this();
else
   do_that();

В качестве альтернативы используйте лямбду:

if (any_of(v.begin(), v.end(), [&](const std::string& elem) { return elem == item; }))
   do_this();
else
   do_that();
13
1.02.2020 14:47:00
bind1stи bind2ndявляются устаревшими , так как C ++ 11 и полностью удал ли в C ++ 17. Используйте bindс placeholdersи / или лямбды вместо этого.
andreee 30.04.2019 07:50:23

Вот функция, которая будет работать для любого контейнера:

template <class Container> 
const bool contains(const Container& container, const typename Container::value_type& element) 
{
    return std::find(container.begin(), container.end(), element) != container.end();
}

Обратите внимание, что вы можете обойтись без 1 параметра шаблона, потому что вы можете извлечь его value_typeиз контейнера. Вам нужно, typenameпотому что Container::value_typeэто зависимое имя .

11
28.02.2018 20:56:22
Обратите внимание, что это иногда слишком много - например, это работает для std :: set, но дает ужасную производительность по сравнению с функцией-членом find (). Я нашел, что лучше всего добавить специализацию для контейнеров с более быстрым поиском (set / map, unordered_ *)
Andy Krouwel 2.11.2016 12:01:34

Еще один пример с использованием операторов C ++.

#include <vector>
#include <algorithm>
#include <stdexcept>

template<typename T>
inline static bool operator ==(const std::vector<T>& v, const T& elem)
{
  return (std::find(v.begin(), v.end(), elem) != v.end());
}

template<typename T>
inline static bool operator !=(const std::vector<T>& v, const T& elem)
{
  return (std::find(v.begin(), v.end(), elem) == v.end());
}

enum CODEC_ID {
  CODEC_ID_AAC,
  CODEC_ID_AC3,
  CODEC_ID_H262,
  CODEC_ID_H263,
  CODEC_ID_H264,
  CODEC_ID_H265,
  CODEC_ID_MAX
};

void main()
{
  CODEC_ID codec = CODEC_ID_H264;
  std::vector<CODEC_ID> codec_list;

  codec_list.reserve(CODEC_ID_MAX);
  codec_list.push_back(CODEC_ID_AAC);
  codec_list.push_back(CODEC_ID_AC3);
  codec_list.push_back(CODEC_ID_H262);
  codec_list.push_back(CODEC_ID_H263);
  codec_list.push_back(CODEC_ID_H264);
  codec_list.push_back(CODEC_ID_H265);

  if (codec_list != codec)
  {
    throw std::runtime_error("codec not found!");
  }

  if (codec_list == codec)
  {
    throw std::logic_error("codec has been found!");
  }
}
2
13.05.2016 08:57:50
Я бы не рекомендовал злоупотреблять перегрузкой операторов таким способом.
Leon 8.06.2016 16:13:01
Леон, я согласен с тобой, семантически это не правильно. Я использую его, чтобы сделать модульные тесты более четкими.
Valdemar_Rudolfovich 10.06.2016 12:34:20

С надстройкой вы можете использовать any_of_equal:

#include <boost/algorithm/cxx11/any_of.hpp>

bool item_present = boost::algorithm::any_of_equal(vector, element);
7
27.09.2016 16:02:37

Используя Newton C ++, это проще, самодокументировано и быстрее, чем с std :: find, потому что возвращает bool напрямую.

bool exists_linear( INPUT_ITERATOR first, INPUT_ITERATOR last, const T& value )

bool exists_binary( INPUT_ITERATOR first, INPUT_ITERATOR last, const T& value )

Я думаю, что очевидно, что делают функции.

include <newton/algorithm/algorithm.hpp>

if ( newton::exists_linear(first, last, value) )
   do_this();
else
   do_that();
-3
11.04.2018 12:10:35

(C ++ 17 и выше):

можно использовать std::searchтакже

Это также полезно для поиска последовательности элементов.

#include <algorithm>
#include <iostream>
#include <vector>

template <typename Container>
bool search_vector(const Container& vec, const Container& searchvec)
{
    return std::search(vec.begin(), vec.end(), searchvec.begin(), searchvec.end()) != vec.end();
}

int main()
{
     std::vector<int> v = {2,4,6,8};

     //THIS WORKS. SEARCHING ONLY ONE ELEMENT.
     std::vector<int> searchVector1 = {2};
     if(search_vector(v,searchVector1))
         std::cout<<"searchVector1 found"<<std::endl;
     else
         std::cout<<"searchVector1 not found"<<std::endl;

     //THIS WORKS, AS THE ELEMENTS ARE SEQUENTIAL.
     std::vector<int> searchVector2 = {6,8};
     if(search_vector(v,searchVector2))
         std::cout<<"searchVector2 found"<<std::endl;
     else
         std::cout<<"searchVector2 not found"<<std::endl;

     //THIS WILL NOT WORK, AS THE ELEMENTS ARE NOT SEQUENTIAL.
     std::vector<int> searchVector3 = {8,6};
     if(search_vector(v,searchVector3))
         std::cout<<"searchVector3 found"<<std::endl;
     else
         std::cout<<"searchVector3 not found"<<std::endl;
}

Также есть гибкость прохождения некоторых поисковых алгоритмов. Обратитесь сюда.

https://en.cppreference.com/w/cpp/algorithm/search

1
26.03.2019 19:23:26

В последнее время я лично использовал шаблоны для обработки нескольких типов контейнеров, а не только для работы с векторами. Я нашел аналогичный пример в Интернете (не помню, где), так что заслуга принадлежит тому, от кого я это украл. Этот конкретный шаблон, похоже, также обрабатывает необработанные массивы.

template <typename Container, typename T = typename std::decay<decltype(*std::begin(std::declval<Container>()))>::type>
bool contains(Container && c, T v)
{
    return std::find(std::begin(c), std::end(c), v) != std::end(c);
}
1
28.10.2019 15:41:58