Как найти в векторе определенный элемент

В этом посте будет обсуждаться, как проверить, присутствует ли элемент в векторе на C++.

1. Использование std::find

Эффективным решением является использование стандартного алгоритма std::find чтобы найти значение в указанном диапазоне. Он определен в <algorithm> заголовок. Преимущество использования std::find заключается в том, что он прекращает поиск, как только найдено совпадение.

Скачать  Выполнить код

2. Использование std::find_if

The std::find_if Алгоритм возвращает итератор к первому элементу в указанном диапазоне, для которого предикат возвращает значение true. Чтобы проверить, присутствует ли элемент в векторе, предикат должен сопоставить текущий элемент с целевым, как показано ниже:

Скачать  Выполнить код

3. Использование std::binary_search

Если vector отсортирован, используйте std::binary_search алгоритм, который возвращает логическое значение в зависимости от того, найден ли элемент в указанном диапазоне или нет. Преимущество использования std::binary_search в том, что он работает всего за O(log(n)) время.

Скачать  Выполнить код

4. Использование std::any_of функция

The std::any_of Алгоритм возвращает true, если предикат возвращает true для любого из элементов в указанном диапазоне. Чтобы проверить, присутствует ли элемент в векторе, предикат должен найти совпадение с целью. Например,

Скачать  Выполнить код

5. Использование std::count

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

Скачать  Выполнить код

6. Использование библиотеки Boost

Если вы используете библиотеку Boost в своем проекте, вы можете использовать boost::algorithm::any_of_equal функция из заголовочного файла <boost/algorithm/cxx11/any_of.hpp>. Он возвращается true если любой из элементов в диапазоне равен указанному значению. Это показано ниже:

Скачать код

7. Использование диапазонов C++20

C++ 20 ranges library предоставляет компоненты для работы с диапазонами элементов, включая различные адаптеры представления. std::views::filter создает представление по диапазону элементов, соответствующих предикату.

В следующем примере кода показан вызов этой функции:

Скачать код

 
До C++20 вам нужно было сделать что-то вроде ниже, чтобы создать контейнер с совпадениями:

Скачать  Выполнить код

Это все о проверке наличия элемента в векторе в C++.

Something like this, I think. find_if_counted.hpp:

#ifndef FIND_IF_COUNTED_HPP
#define FIND_IF_COUNTED_HPP

#include <algorithm>

namespace find_if_counted_impl
{
    template <typename Func>
    struct func_counter
    {
        explicit func_counter(Func& func, unsigned &count) :
        _func(func),
        _count(count)
        {
        }

        template <typename T>
        bool operator()(const T& t)
        {
            ++_count;

            return _func(t);
        }

    private:
        Func& _func;
        unsigned& _count;
    };
}

// generic find_if_counted,
// returns the index of the found element, otherwise returns find_if_not_found
const size_t find_if_not_found = static_cast<size_t>(-1);

template <typename InputIterator, typename Func>
size_t find_if_counted(InputIterator start, InputIterator finish, Func func)
{
    unsigned count = 0;
    find_if_counted_impl::func_counter<Func> f(func, count);

    InputIterator result = find_if(start, finish, f);

    if (result == finish)
    {
        return find_if_not_found;
    }
    else
    {
        return count - 1;
    }
}

#endif

Example:

#include "find_if_counted.hpp"
#include <cstdlib>
#include <iostream>
#include <vector>

typedef std::vector<int> container;

int rand_number(void)
{
    return rand()  % 20;
}

bool is_even(int i)
{
    return i % 2 == 0;
}

int main(void)
{
    container vec1(10);
    container vec2(10);

    std::generate(vec1.begin(), vec1.end(), rand_number);
    std::generate(vec2.begin(), vec2.end(), rand_number);

    unsigned index = find_if_counted(vec1.begin(), vec1.end(), is_even);

    if (index == find_if_not_found)
    {
        std::cout << "vec1 has no even numbers." << std::endl;
    }
    else
    {
        std::cout << "vec1 had an even number at index: " << index <<
            " vec2's corresponding number is: " << vec2[index] << std::endl;
    }
}

Though I feel like I’m doing something silly… :X Any corrections are welcome, of course.

Вектор C ++ не имеет функции-члена поиска. Однако в библиотеке алгоритмов есть функции find () разных типов, которые можно использовать для поиска чего-либо в векторе C ++. В библиотеке алгоритмов есть четыре группы функций find (), которые можно классифицировать как «Найти», «Найти конец», «Найти сначала» и «Найти по соседству».

Чтобы использовать библиотеки векторов и алгоритмов, программа на C ++ должна начинаться с:

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

В этом руководстве приведены основы поиска значения в векторе C ++. Весь код в этом руководстве находится в функции main (), если не указано иное. Если вектор состоит из строк, используйте строковый класс; и не используйте «const char *». В этом случае также должен быть включен строковый класс, например:

Find

InputIterator find (сначала InputIterator, последним InputIterator, const T & value);

Следующий код использует эту функцию, чтобы узнать, входит ли цветок «Василек» в векторный список цветов:

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

int main()
{
vectorvtr = {«Dog Rose», «Honeysuckle», «Enchanter’s nightshade», «Columbine», «Kingcup», «Cornflower», «Water avens», «Forget-me-not»};

vector::iterator it = find(vtr.begin(), vtr.end(), «Cornflower»);

if (it == vtr.end())
cout<< «Flower was not found!» <<endl;
else
cout<< «Flower found at index: « << it — vtr.begin() <<endl;

return 0;
}

Результат:

Целый список вектора был целью поиска. Судя по синтаксису функции find (), «first» — это vtr.begin () в коде, а «last» — это vtr.end () в коде. Значение, которое нужно искать в синтаксисе функции find (), обозначенное как const-T & -value, в коде имеет значение «Василек».

Функция find () просматривает список векторов с самого начала. Если он не видит искомого значения, он достигнет конца вектора. Конец вектора — это официально vtr.end (), который находится сразу за последним элементом. Если он не видит искомого значения, он вернет итератор, указывающий на vtr.end ().

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

Каждое значение в векторе имеет индекс. Первое значение имеет индекс 0, соответствующий vtr.begin (). Второе значение имеет индекс 1, соответствующий vtr.begin () + 1. Третье значение имеет индекс 2, соответствующий vtr.begin () + 2. Четвертое значение имеет индекс 3, соответствующий vtr.begin () + 3. ; и так далее. Итак, индекс первого найденного значения определяется как:

Чувствительность к регистру

Поиск в векторе чувствителен к регистру. Если бы значение, которое нужно было найти, было «CORNFLOWER» для указанной выше программы, оно не было бы найдено и была бы возвращена vtr.end ().

Range Within Limits

Диапазон не обязательно должен составлять весь вектор. Для приведенной выше программы диапазон мог быть от индекса 1 до индекса 4. То есть от «vtr.begin () + 1» до «vtr.end () — 4». «Vtr.end () — 4» получается вычитанием из обратного с учетом того, что vtr.end () находится сразу за самым последним элементом.

Когда весь список векторов является диапазоном, проверка того, является ли итератор возврата vtr.end (), показывает, было ли значение найдено или нет. Если итератором возврата является vtr.end (), это означает, что значение не было найдено. Теперь, когда диапазон меньше, если итератор возврата является последним элементом выбранного диапазона, это означает, что значение либо не было найдено, либо это последнее значение диапазона.

Примечание. Поиск останавливается на последнем элементе выбранного (меньшего) диапазона, если значение не было найдено в этом диапазоне или если найденное значение является последним элементом выбранного диапазона. Если найденное значение было этим последним элементом, будет возвращен итератор, указывающий на него. Если значение было найдено раньше, поиск остановится на этом элементе перед последним элементом выбранного диапазона. Итератор этого элемента будет возвращен.

Следующий код иллюстрирует эту схему:

  #include <algorithm>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

int main()
{
vectorvtr = {«Dog Rose», «Honeysuckle», «Enchanter’s nightshade», «Columbine», «Kingcup», «Cornflower», «Water avens», «Forget-me-not»};

vector::iterator it = find(vtr.begin() + 1, vtr.end() — 4, «Cornflower»);

if (it == vtr.end())
cout<< «Flower was not found!» <<endl;
else if (it — vtr.begin() == 4) {    //last element in chosen range
if (*it == string(«Cornflower»))
cout<< «Flower found at index: « << it — vtr.begin() <<endl;
else
cout<< «Flower was not found in range!» <<endl;
}
else {
cout<< «Flower found at index: « << it — vtr.begin() <<endl;
}

return 0;
}

Результат:

Flower was not found in range!

Теперь «Василек» имеет индекс 5, а «Kingcup» — индекс 4. Последний элемент в небольшом диапазоне, выбранном для поиска, — «Kingcup». Итак, соответствующее условие теста — «it — vtr.begin () == 4». Обратите внимание, что выражения «vtr.end () — 4» и «it — vtr.begin () == 4», каждое из которых имеет 4, являются просто совпадением.

Чтобы «Василек» был в малом диапазоне поиска, соответствующее условие проверки должно быть «it — vtr.begin () == 5». Следующий код иллюстрирует это:

    #include <algorithm>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

int main()
{
vectorvtr = {«Dog Rose», «Honeysuckle», «Enchanter’s nightshade», «Columbine», «Kingcup», «Cornflower», «Water avens», «Forget-me-not»};

vector::iterator it = find(vtr.begin() + 1, vtr.end() — 3, «Cornflower»);

if (it == vtr.end())
cout<< «Flower was not found!» <<endl;
else if (it — vtr.begin() == 5) {
if (*it == string(«Cornflower»))
cout<< «Flower found at index: « << it — vtr.begin() <<endl;
else
cout<< «Flower was not found in range!» <<endl;
}
else {
cout<< «Flower found at index: « << it — vtr.begin() <<endl;
}

return 0;
}

Результат:

More Than One Occurrence

В следующей программе «Василек» встречается более чем в одном месте. Чтобы найти все индексы вхождений, используйте цикл while для продолжения поиска после предыдущего вхождения до конца (vtr.end ()) вектора. Программа:

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>

using namespace std;

int main()
{
vectorvtr = {«Dog Rose», «Cornflower», «Enchanter’s nightshade», «Columbine», «Kingcup», «Cornflower», «Water avens», «Cornflower»};

vector::iterator it = find(vtr.begin(), vtr.end(), «Cornflower»);
while (it != vtr.end()) {
if (*it == string(«Cornflower»))
cout<< «Flower found at index: « << it — vtr.begin() <<endl;
it++;
}

return 0;
}

Результат:

Flower found at index: 1

Flower found at index: 5

Flower found at index: 7

Finding Integer

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

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

int main()
{
vectorvtr = {1, 2, 3, 1, 2, 3, 1, 2, 3};

vector::iterator it = find(vtr.begin(), vtr.end(), 3);

if (it == vtr.end())
cout<< «Number was not found!» <<endl;
else
cout<< «Number found at index: « << it — vtr.begin() <<endl;

return 0;
}

Результат:

Number found at index: 2

for the first occurrence of the value, 3.

Predicate

InputIterator find_if (сначала InputIterator, затем — InputIterator, предикат предиката);

Здесь используется функция find_if (), а не просто find (). Pred — это имя функции, которая дает критерии поиска. Этот третий аргумент принимает только имя функции, без аргументов и без скобок. Если функция-предикат принимает аргумент, тогда в определении функции указываются параметры для аргументов. Следующая программа иллюстрирует это, ища первое четное число в списке векторов:

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

bool fn(int n) {
if ((n % 2) == 0)
return true;
else
return false;
}

int main()
{
vectorvtr = {1, 3, 5, 7, 8, 9, 10, 11, 12};

vector::iterator it = find_if(vtr.begin(), vtr.end(), fn);

if (it == vtr.end())
cout<< «Number was not found!» <<endl;
else
cout<< «Number found at index: « << it — vtr.begin() <<endl;

return 0;
}

Результат:

Обратите внимание, что был выполнен поиск по всему вектору с диапазоном «vtr.begin (), vtr.end ()».

Имя функции-предиката здесь — fn. Требуется один аргумент — целое число. Когда функция find_if () начинает сканирование вектора с первого элемента, она вызывает функцию предиката с каждым числом в векторе в качестве аргумента. Сканирование останавливается, когда он достигает первого элемента в векторе, для которого предикат возвращает истину.

Заключение

Функция find () в библиотеке алгоритмов существует в четырех категориях: «Найти», «Найти конец», «Найти сначала» и «Найти по соседству». Только категория «Найти» была объяснена выше, и в значительной степени. Приведенное выше объяснение является основой для всех функций find () в библиотеке алгоритмов. Функции Find () имеют дело с итераторами напрямую и косвенно с индексами. Программист должен знать, как преобразовать итератор в индексную и общую арифметику итератора, как показано выше.