Обобщенные алгоритмы STL Примеры алгоритмов на векторе

При изучении STL у меня получается что-то типа цепочки. Куда не сунься, везде какая-то обширная тема. Сначала был вектор, потом итератор, там в итераторах встретилось понятие алгоритм. Большая часть алгоритмов STL основывается на одном принципе. Алгоритму передается пара итераторов (точка старта и точка финиша), другими словами в алгоритм передается диапазон или можно сказать интервал. Если алгоритм осуществлял поиск, то он вернет либо итератор, указывающий на найденный элемент, либо конец интервала. Конец интервала уже не указывает на элемент контейнера.
Примеры алгоритмов для вектора. Поиск элемента в интервале.

  • алгоритм find(…)

Достаточно простой алгоритм для понимания. В алгоритм передается две точки v.begin и v.end, которые обозначают точку старта и точку финиша поиска. Между этими точками некоторый диапазон, в котором находятся разные значения. Если при своих расчетах алгоритм встречает указанный элемент (тот элемент указан третьим параметром), то выполняется некоторое условие. Хоть в самом начале и написано, что алгоритм вернет либо итератор, либо конец интервала, для алгоритма find это не актуально.

С помощью алгоритма find можно узнать индекс найденного элемента

  • Код С++ Алгоритм find

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

  • Код C++ Алгоритм find

===============================================
Следующий алгоритм, на который посмотрим это finf_if Он Находит позицию первого вхождения элемента в диапазоне, удовлетворяющем указанному условию.
Чтобы понять, смотрим пример

  • Код C++ алгоритм find_if

Разобраться не так сложно. Как и в случае с алгоритмом find можно вывести все элементы вектора на экран, предлагаю сделать это вам лично
===============================================
Более менее разобрались с первыми алгоритмами. Во всяком случае что-то увидели. Будем рассматривать следующий алгоритм. Алгоритм поиска максимального и минимального значения. Следует помнить, что индексы элементов это одно, а значения элементов другое. Иногда может понадобиться индекс элемента, а иногда значение по индексу, поэтому как и в первый раз привожу код и для индексов элементов и для значений

  • Код C++ Алгоритм max_element и Алгоритм min_element

В одном случае используется указатель, в другом указатель не используется. Код маленький и должен быстро уложиться в вашей голове. Предлагаю вам решить несложную задачу. Выведите на экран все индексы вектора, в которых лежит минимальный элемент. Т.е. например вектор содержит 0 1 0 0 1 —-> на экран 1 4 (отсчет индексов с нуля). Приблизительный код я приводил, нужно просто создать аналогию программы.

================================
Есть еще другие алгоритмы поиска. Задачи ведь могут быть разные. Одна из таких задач при поиске это поиск вхождения последовательности. Может это не совсем понятно, поэтому поясню. Вот есть два массива и нужно проверить есть ли в первом массиве второй массив (или часть второго массива), вот для поиска таких последовательностей существует алгоритм search
Что такое предикат вы, наверное, поняли. Это функция, в которой мы задаем некоторое условие. Даже если не совсем поняли, то может поймете по этому примеру поиска последовательностей. Здесь в одном примере будет два способа поиска. Один простой поиск и второй поиск с помощью предиката

  • Код C++ Алгоритм search

Вверху будет показан основной массив, в котором мы искали вхождение последовательности, ниже результаты поисков и еще ниже поясненения. Может не очень удобно, но понять можно. Думаю даже так это лучше чем ничего. Код получился не таким маленьким как хотелось бы, но это в основном из-за оформления при выводе на экран
===============================
Есть еще Бинарный поиск. Бинарный поиск в разы быстрее обычного, но выполняется он если диапазон значений, в которых ищется элемент отсортирован. Если диапазон значений не был отсортирован и значения идут вразнобой, то чтобы выполнить такой поиск, этот диапазон предварительно сортируют. Суть алгоритма и пример его реализации можно почитать в википедии При использовании STL не нужно этот алгоритм реализовывать заново, просто нужно понимать как он работает.

Алгоритм find_search предназначен для поиска элемента в диапазоне, но этот алгоритм не покажет нам где он нашел этот элемент. Чтобы показать позиции имеет смысл использовать разновидности бинарного поиска lower_bound(), upper_bound() и equal_range()

  • Код C++ Бинарный поиск find_search

  • Код C++ Бинарный поиск find_search только уже с предикатом

  • Код C++ использование разновидности алгоритма бинарного поиска
    Алгоритм lower_bound()

===============================
Вначале я уже показывал пример с поиском всех позиций. В том же примере можно было посчитать количество одинаковых элементов. Но для определения количества одинаковых элементов можно использовать алгоритм count

  • Код C++ Алгоритм count

К этой же категории поиска, как в последнем примере относится алгоритм find_if. Этот алгоритм ищет по заданному нам условию. Хороший пример его использования — расчет гласных в строке. Сразу предупрежу, что русская а и латинская а это два разных звука, так как комп их видит по своему, аналогично для всех других букв и гласных и согласных.

  • Код C++ Алгоритм count_if Посчитать число гласных в строке

Не знаю кому как, но надеюсь дал понять принцип использование и основное назначение такого алгоритма поиска

================================
На очереди еще один алгоритм. Это алгоритм сортировки sort

  • Код C++ Алгоритм sort

Как я выводил массив на экран, так можно и с вектором. Просто я как-то так шел, что перехожу от одного способа к другому. Алгоритм sort гарантирует хорошее среднее быстродействие (n*log(n)). Алгоритм сортировки активно использует арифметику на указателях, он может работать только на итераторах произвольного доступа

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

ОБОБЩЕННЫЕ АЛГОРИТМЫ

алгоритмы поиска алгоритмы сортировки и упорядочения алгоритмы удаления численные алгоритмы алгоритмы генерации и изменения последовательности алгоритмы сравнения
find() sort() unique() accumulate() generate() equal()
find_if() partial_sort() remove() partial_sum() fill() min()
search() merge() inner_product() transform() max()
binary_search() partition() adjacent_difference() copy()
count() rotate() for_each()
count_if() reverse()
random_shuffle()
Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

Один комментарий: Обобщенные алгоритмы STL Примеры алгоритмов на векторе

  • Аноним говорит:

    В Код C++ Алгоритм max_element и Алгоритм min_element небольшая ошибка: перепутани коментарии. Правильно будет так:




    0



    0

Добавить комментарий

Ваш e-mail не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/skott-mayers/effektivnoe-ispolzovanie-c-55-vernyh-sposobov-uluchshit-strukturu-i-kod-vashih-programm/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Лучше бы вместо смс ввели

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок