Jak sprawdzić, czy element jest obecny w std :: vector?

616

Wszystko, co chcę zrobić, to sprawdzić, czy element istnieje w wektorze, czy nie, więc mogę poradzić sobie z każdym przypadkiem.

if ( item_present )
   do_this();
else
   do_that();
Joan Venge
źródło
2
wyszukiwanie w wektorze jest bardzo wolne, ponieważ musisz patrzeć na każdy element wektora, więc rozważ użycie mapy, jeśli wykonujesz wiele
odnośników
7
@naumcho: Jeśli wektor jest posortowany, zawsze następuje wyszukiwanie binarne, jak podano poniżej. Dzięki temu jest tak szybki jak mapa, a jeśli przechowujesz tylko wartości (a nie mapy kluczy / wartości), zużyje o wiele mniej pamięci.
Adam Hawes
4
mapy z pewnością nie są najlepszym wyborem, ale użycie zestawu może być przydatne. Jeśli potrzebujesz czasu wyszukiwania O (1), najlepszym rozwiązaniem jest hash_set.
Philipp
Znakomita odpowiedź na zduplikowane pytanie: stackoverflow.com/a/3451045/472647
CodeMouse92,
1
Jeśli zamierzasz wielokrotnie wyszukiwać różne liczby, tablica skrótów byłaby bardziej wydajna.
NL628,

Odpowiedzi:

915

Możesz używać std::findz <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()

Zwraca bool ( truejeśli jest obecny, w falseprzeciwnym razie). Na przykład:

#include <algorithm>
#include <vector>

if ( std::find(vec.begin(), vec.end(), item) != vec.end() )
   do_this();
else
   do_that();
MSN
źródło
216
Nie rozumiem, w jaki sposób count () może być szybszy niż find (), ponieważ find () zatrzymuje się natychmiast po znalezieniu jednego elementu, podczas gdy count () zawsze musi skanować całą sekwencję.
Éric Malenfant
114
Nie zapomnij, #include <algorithm>bo mogą się pojawić bardzo dziwne błędy, takie jak „nie można znaleźć pasującej funkcji w przestrzeni nazw std”
rustyx
80
Czy nikomu nie przeszkadzało, że pomimo tego, że STL jest „obiektowe”, .find()wciąż nie jest funkcją członka std::vector, jak można się spodziewać? Zastanawiam się, czy jest to w jakiś sposób konsekwencja szablonowania.
bobobobo,
71
@bobobobo: OOP nie ma nic wspólnego z członkami vs. osobami niebędącymi członkami. I istnieje szeroko rozpowszechniona szkoła myślenia, że ​​jeśli coś nie musi być członkiem lub gdy nie daje żadnej korzyści, gdy jest wdrażane jako członek, to nie powinno być członkiem; std::vector<>::find()nie dałoby żadnej korzyści, ani też nie jest potrzebne, dlatego nie, nie powinien być członkiem. Zobacz także en.wikipedia.org/wiki/Coupling_%28computer_programming%29
Sebastian Mach
36
@phresnel Argumentowałbym, że „jeśli nie daje żadnej korzyści, gdy jest implementowany jako członek”, jest w tym przypadku fałszywe. Zaletą jest uproszczony i bardziej przejrzysty interfejs. Na przykład: mvec.find(key) != mvec.cend()lepiej niż std::find(mvec.cbegin(), mvec.cend(), key) != mvec.cend().
swalog
113

Jak powiedzieli inni, użyj STL findlub find_iffunkcji. Ale jeśli szukasz w bardzo dużych wektorów i wydajność to wpływ, może chcesz uporządkować swoje wektor a następnie użyć binary_search, lower_boundlub upper_boundalgorytmów.

Brian Neal
źródło
3
Dobra odpowiedź! Znajdź to zawsze o (n). dolna wartość to o (log (n)), jeśli jest używane z iteratorami o swobodnym dostępie.
Stephen Edmonds
30
Sortowanie odbywa się jednak w trybie O (nlogn), więc warto je wykonywać tylko wtedy, gdy wykonujesz więcej niż wyszukiwania O (logn).
liori
7
@liori Prawda, że ​​zależy to od twoich wzorców użytkowania. Jeśli musisz go posortować tylko raz, to wielokrotnie wykonuj wiele wyszukiwań, aby cię uratować.
Brian Neal,
1
@Brian Neal, sortowanie dużego wektora jest warte, jeśli musi być na nim wiele wyszukiwań elementów. Sortowanie będzie O (nlogn), a O (n) będzie lepsze, jeśli trzeba znaleźć element tylko raz :)
Swapnil B.
47

Użyj find z nagłówka algorytmu stl. Zilustrowałem jego użycie typem int. Możesz użyć dowolnego typu, pod warunkiem, że możesz porównać dla równości (przeciążenie ==, jeśli potrzebujesz dla swojej klasy niestandardowej).

#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;
}
m-ostre
źródło
2
W zależności od potrzeb PO odpowiednia może być również find_if (). Umożliwia wyszukiwanie przy użyciu dowolnego predykatu zamiast równości.
Éric Malenfant,
Ups, zobaczyłem twój komentarz za późno. W udzielonej przeze mnie odpowiedzi wspomina się także o find_if.
Frank
39

Jeśli twój wektor nie jest uporządkowany, użyj sugerowanego przez MSN podejścia:

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

Jeśli twój wektor jest uporządkowany, użyj metody binary_search Brian Neal zasugerował:

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

wyszukiwanie binarne daje wydajność O (log n) w najgorszym przypadku, która jest znacznie wydajniejsza niż pierwsze podejście. Aby użyć wyszukiwania binarnego, możesz użyć qsort, aby najpierw posortować wektor, aby upewnić się, że jest on uporządkowany.

spiralmoon
źródło
3
Nie masz na myśli std::sort? qsortjest bardzo nieefektywny w przypadku wektorów .... patrz: stackoverflow.com/questions/12308243/...
Jason R. Mick
1
Wyszukiwanie binarne będzie działać lepiej w przypadku większych kontenerów, ale w przypadku małych kontenerów proste wyszukiwanie liniowe może być równie szybkie lub szybsze.
BillT
21

Używam czegoś takiego ...

#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

... w ten sposób jest to właściwie jasne i czytelne. (Oczywiście możesz ponownie użyć szablonu w wielu miejscach).

Andy Krouwel
źródło
i możesz sprawić, że będzie działał dla list lub wektorów, używając 2
nazw maszynowych
@ErikAronesty możesz uciec z 1 argumentem szablonu, jeśli używasz value_typez kontenera dla typu elementu. Dodałem taką odpowiedź.
Martin Broadhurst
13

W C ++ 11 możesz używać any_of. Na przykład jeśli jest to vector<string> v;wtedy:

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

Alternatywnie użyj lambda:

if (any_of(v.begin(), v.end(), [&](const std::string& elem) { return elem == item; }))
   do_this();
else
   do_that();
Deqing
źródło
1
bind1sti bind2ndprzestarzałe od C ++ 11 i całkowicie usunięte w C ++ 17. Zamiast tego używaj bindz placeholdersi / lub lambdas.
andreee
11

Oto funkcja, która będzie działać dla każdego kontenera:

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();
}

Pamiętaj, że możesz uciec z 1 parametrem szablonu, ponieważ możesz wyodrębnić go value_typez kontenera. Potrzebujesz, typenameponieważ ponieważ Container::value_typejest to nazwa zależna .

Martin Broadhurst
źródło
5
Zauważ, że czasami jest to trochę za szerokie - działałoby to na przykład dla std :: set, ale dawało straszną wydajność w porównaniu z funkcją członka find (). Uważam, że najlepiej jest dodać specjalizację dla kontenerów z szybszym wyszukiwaniem (set / map, unordered_ *)
Andy Krouwel,
10

Pamiętaj, że jeśli będziesz przeprowadzać wiele przeglądów, lepiej nadają się pojemniki STL. Nie wiem, jaka jest twoja aplikacja, ale warto rozważyć kontenery asocjacyjne, takie jak std :: map.

std :: vector jest pojemnikiem z wyboru, chyba że masz powód innego, a wyszukiwania według wartości mogą być takim powodem.

David Thornley
źródło
Nawet w przypadku wyszukiwania według wartości wektor może być dobrym wyborem, o ile jest on posortowany i używasz wyszukiwania binarnego, dolnego lub górnego. Jeśli zawartość kontenera zmienia się między przeglądami, wektor nie jest zbyt dobry z powodu konieczności ponownego sortowania.
Renze de Waal
8

Użyj funkcji wyszukiwania STL .

Należy pamiętać, że istnieje również funkcja find_if , z której można skorzystać, jeśli wyszukiwanie jest bardziej złożone, tj. Jeśli nie szukasz tylko elementu, ale na przykład chcesz sprawdzić, czy element spełnia określony warunek, na przykład ciąg rozpoczynający się od „abc”. ( find_ifdałby ci iterator, który wskazuje na pierwszy taki element).

Szczery
źródło
7

Dzięki doładowaniu możesz użyć any_of_equal:

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

bool item_present = boost::algorithm::any_of_equal(vector, element);
Michaił
źródło
5

Możesz wypróbować ten kod:

#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()
}
TrungTN
źródło
3

Możesz użyć findfunkcji znajdującej się w stdprzestrzeni nazw, tj std::find. Przekazujesz std::findfunkcję begini enditerator z wektora, który chcesz wyszukać, wraz z szukanym elementem i porównujesz wynikowy iterator z końcem wektora, aby sprawdzić, czy są one zgodne.

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

Możesz także wyłuskać ten iterator i używać go normalnie, jak każdego innego iteratora.

TankorSmash
źródło
3

Możesz też użyć count. Zwróci liczbę elementów obecnych w wektorze.

int t=count(vec.begin(),vec.end(),item);
Aditya
źródło
11
findjest szybszy niż count, ponieważ nie liczy się po pierwszym meczu.
Camille Goudeseune,
2

Jeśli chcesz znaleźć ciąg w wektorze:

    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));
Gank
źródło
2

Kolejny przykład wykorzystujący operatory 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!");
  }
}
Valdemar_Rudolfovich
źródło
4
Nie polecałbym nadużywania operatora w taki sposób.
Leon
2
Leon, zgadzam się z tobą, semantycznie to nie jest poprawne. Używam go, aby wyraźniej przeprowadzić testy jednostkowe.
Valdemar_Rudolfovich
1
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;
}
użytkownik3157855
źródło
1

(C ++ 17 i wyżej):

można std::searchrównież użyć

Jest to również przydatne do wyszukiwania sekwencji elementów.

#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;
}

Istnieje również elastyczność przekazywania niektórych algorytmów wyszukiwania. Zobacz tutaj.

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

Pavan Chandaka
źródło
1

Ostatnio osobiście używałem szablonów do obsługi wielu rodzajów pojemników jednocześnie, zamiast zajmować się tylko wektorami. Znalazłem podobny przykład online (nie pamiętam, gdzie), więc uznanie należy się każdemu, z kogo go ukradłem. Ten szczególny wzór wydaje się również obsługiwać surowe tablice.

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);
}
Pascal Laferrière
źródło
-4

Korzystanie z Newton C ++ jest łatwiejsze, samo-udokumentowane i szybsze niż w przypadku std :: find, ponieważ zwraca bool bezpośrednio.

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

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

Myślę, że to oczywiste, co robią te funkcje.

include <newton/algorithm/algorithm.hpp>

if ( newton::exists_linear(first, last, value) )
   do_this();
else
   do_that();
Moises Rojo
źródło