Поиск и min-max (серия «114 алгоритмов C++»)

Добро пожаловать в восьмую часть серии «114 алгоритмов C++». Сегодня мы обсудим алгоритмы поиска, которые ищут конкретный элемент или подсчитывают количество совпадающих элементов, а также алгоритмы минимума и максимума.

Алгоритмы поиска и минимума и максимума, которые мы рассмотрим сегодня, работают линейно со сложностью O(n) (при работе с одним диапазоном) или O(m*n) (при работе с двумя диапазонами). Более быстрые алгоритмы поиска мы рассмотрели в статье номер три.

find, find_if, find_if_not

Алгоритм std::find обеспечивает базовый линейный поиск. Стандарт предоставляет три варианта: один поиск по значению и два варианта с использованием предиката.

Типичным примером поиска по значению является поиск разделителей:

std::string data = "John;Doe;April;1;1900;";
auto it = data.begin(), token = data.begin();
std::vector<std::string> out;

while ((token = find(it, data.end(), ';')) != data.end()) {
    out.push_back("");
    std::copy(it, token, std::back_inserter(out.back()));
    it = std::next(token);
}
// out == { "John", "Doe", "April", "1", "1900" }

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

std::string data = "   hello world!  ";
auto begin = std::find_if_not(data.begin(), data.end(), 
                              [](char c) { return isspace(c); });
if (begin == data.end()) // только пробелы
    return 0;

std::string out;
std::copy(begin, std::find_if_not(data.rbegin(), data.rend(), 
                                  [](char c) { return isspace(c); }).base(), 
          std::back_inserter(out));
// out == "hello world!"

adjacent_find, search_n

Как следует из названия, std::adjacent_find ищет соседние элементы в диапазоне.

Базовая версия ищет пару соседних элементов, используя operator== или бинарный предикат, если он предоставлен. В любом случае пара будет возвращена итератором к первому из двух элементов.

std::vector<int> data = { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9 };
auto it1 = std::adjacent_find(data.begin(), data.end());
// *it1 == 4, т.е. {4, 4}

auto it2 = std::adjacent_find(data.begin(), data.end(), 
                              [](int l, int r) { return l + r > 10; });
// *it2 == 5, т.е. {5, 6}

Если мы хотим найти более двух последовательных одинаковых элементов, мы можем использовать std::search_n.

Этот алгоритм принимает желаемое количество экземпляров и значение для сравнения. Если поиск успешен, последовательность возвращается с помощью итератора к первому элементу последовательности.

std::vector<int> data = { 1, 0, 5, 8, 3, 3, 2 };

auto it1 = std::search_n(data.begin(), data.end(), 2, 3);
// *it1 == 3, т.е. {3, 3}

auto it2 = std::search_n(data.begin(), data.end(), 3, 3, 
                         [](int l, int r) { return l % 5 == r % 5; });
// *it2 == 8, т.е. {8, 3, 3}

auto it3 = std::search_n(data.begin(), data.end(), 2, 0);
// it3 == data.end(), т.е. не найден

Обратите внимание, что поведение std::search_n не соответствует обычному именованию. Диапазон по-прежнему полностью определяется с помощью итераторов begin и end. А _n относится к количеству экземпляров.

find_first_of

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

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

std::vector<int> haystack = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::vector<int> needles = { 7, 5, 3 };
auto it = std::find_first_of(haystack.begin(), haystack.end(), 
                             needles.begin(), needles.end());
// *it == 3, т.е. haystack[2]

search, find_end

Наконец, мы приходим к алгоритмам, которые ищут подпоследовательность в последовательности.

std::search возвращает первый экземпляр подпоследовательности, а std::find_end возвращает последний экземпляр подпоследовательности.

std::string haystack = "abbabba";
std::string needle = "bba";
auto it1 = std::search(haystack.begin(), haystack.end(), 
                       needle.begin(), needle.end());
// it1..end == "bbabba"

auto it2 = std::find_end(haystack.begin(), haystack.end(), 
                         needle.begin(), needle.end());
// it2..end == "bba"

Поисковики

Начиная с C++17, мы также можем указать пользовательские поисковики для алгоритма поиска. Помимо основного, в стандарте реализованы поисковики строк Бойера-Мура и Бойера-Мура-Хорспула, которые предлагают разную сложность для наилучшего и наихудшего случаев и среднюю сложность.

std::string haystack = "abbabba";
std::string needle = "bba";

auto it1 = std::search(haystack.begin(), haystack.end(), 
                       std::default_searcher(needle.begin(), needle.end()));

auto it2 = std::search(haystack.begin(), haystack.end(), 
                       std::boyer_moore_searcher(needle.begin(), needle.end()));

auto it3 = std::search(haystack.begin(), haystack.end(), 
                       std::boyer_moore_horspool_searcher(needle.begin(), needle.end()));
// it1 == it2 == it3

count, count_if

Алгоритмы std::count и std::count_if подсчитывают количество совпадающих элементов.

Искомый элемент можно указать с помощью значения или предиката.

std::vector<int> data = { 1, 2, 3, 2, 1, 2, 3, 2, 1 };
auto one_cnt = std::count(data.begin(), data.end(), 1);
// one_cnt == 3

auto even_cnt = std::count_if(data.begin(), data.end(), 
                              [](int v) { return v % 2 == 0; });
// even_cnt == 4

equal, mismatch

В предыдущей статье мы обсуждали лексикографические сравнения с использованием std::lexicographical_compare и std::lexicographical_compare_three_way. Алгоритмы std::equal и std::mismatch обеспечивают более простое сравнение на равенство, при этом std::equal возвращает просто логическое значение, а std::mismatch возвращает пару итераторов, обозначающих несовпадающие элементы.

Для обоих алгоритмов operator== по умолчанию можно заменить бинарным предикатом.

std::vector<int> first = { 1, 2, 3, 4, 5 };
std::vector<int> second = { -1, -2, -3, -4, -5 };

assert(!std::equal(first.begin(), first.end(), second.begin()));

assert(std::equal(first.begin(), first.end(), second.begin(), 
                  [](int l, int r) { return std::abs(l) == std::abs(r); }));

Алгоритм std::mismatch возвращает пару итераторов, базовые элементы которых не совпадают.

std::vector<int> first = { 1, 2, 3, 4, 5 };
std::vector<int> second = { 1, 2, 2, 4, 5 };

auto it_pair = std::mismatch(first.begin(), first.end(), second.begin());
// *it_pair.first == 3, *it_pair.second == 2

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

std::vector<int> first = { 1, 2, 3, 4, 5 };
std::vector<int> second = { 1, 2, 3, 4, 5, 6 };

assert(std::equal(first.begin(), first.end(), 
                  second.begin()));
// Не может определить несовпадение размеров.

assert(!std::equal(first.begin(), first.end(), 
                   second.begin(), second.end()));
// Разное количество элементов -> не равны.

clamp

Алгоритм std::clamp – один из немногих алгоритмов, которые не работают с диапазонами.

Алгоритм clamp зафиксирует заданное значение между предоставленным минимумом и максимумом:

• если значение < минимум, std::clamp возвращает минимум;
• если максимум < значение, std::clamp возвращает максимальное значение;
• в противном случае std::clamp возвращает значение.

int a = std::ranges::clamp(10, 0, 20);
// a == 10 (0 < 10 && 10 < 20)

int b = std::clamp(-20, 0, 20);
// b == 0 (-20 < 0)

int c = std::clamp(30, 0, 20);
// c == 20 ( 30 > 20 )

min, max, minmax

Первая группа алгоритмов min-max также не работает с диапазонами (за исключением варианта для диапазона в C++20).

До C++14 единственные доступные варианты работали только с двумя элементами, возвращая константную ссылку. Затем в стандарте C++14 был представлен вариант, работающий со списком инициализаторов, который возвращает значение. Наконец, в C++20 появился вариант для диапазона, который работает с входными диапазонами и возвращает значение.

auto i = std::min(1, 2);
// i == 1

auto j = std::max(1, 2);
// j == 2

auto v = std::minmax({5, 3, -2, 0});
// v.first == -2, v.second == 5

std::list<int> data = {5, 3, -2, 0};
auto k = std::ranges::min(data);
// k == -2

min_element, max_element, minmax_element

Элементные версии алгоритмов min-max работают с диапазонами и вместо возврата по константной ссылке или по значению возвращают итератор к минимальному или максимальному элементам.

Для всех вариантов требуется forward_range, так как они возвращают итераторы к элементам min-max вместо значения.

std::vector<int> data = { 5, 3, -2 , 0};
auto i = std::min_element(data.begin(), data.end());
// *i == -2 (т.е. data[2])
auto j = std::max_element(data.begin(), data.end());
// *j == 5 (т.е. data[0])

auto k = std::minmax_element(data.begin(), data.end());
// *k.first == -2, *k.second == 5

Спасибо за чтение

В этой серии будет еще одна статья, посвященная функциям, которые мы можем ожидать в будущих версиях C++.

Теги