Краткий справочник по алгоритмам STL

Croessmah · 23.03.2016, 16:44 **[ТС]**

Author24 — интернет-сервис помощи студентам

Данная тема создана как справочник по алгоритмам STL и будет постепенно наполняться контентом.

Тема для обсуждения: Краткий справочник по алгоритмам STL

Данные по алгоритмам взяты из документа N4567

Принятые обозначения
Требования и условия

Не модифицирующие алгоритмы
all_of	все элементы соответствуют критерию
any_of	один из элементов соответствует критерию
none_of	ни один из элементов не соответствует критерию
for_each	обход всех элементов диапазона
find	поиск элемента в последовательности
find_if	поиск элемента удовлетворяющего критерию
find_if_not	поиск элемента не удовлетворяющего критерию
find_end	поиск последнего вхождения подпоследовательности
find_first_of	поиск значения из заданного диапазона
adjacent_find	поиск равных соседних элементов
count	количество вхождений элемента
count_if	количество элементов соответствующих критерию
mismatch	поиск различных элементов
equal	проверка равенства последовательностей
is permutation	является ли диапазон перестановкой другого диапазона
search	поиск первого вхождения подпоследовательности
search_n	поиск подпоследовательности из n элементов

Croessmah · Регистрация: 27.09.2012

Принятые обозначения.

Категории итераторов:

InputIterator/OutputIterator	итератор ввода/итератор вывода
ForwardIterator	однонаправленный итератор
BidirectionalIterator	двунаправленный итератор
RandomAccessIterator	итератор произвольного доступа

Каждая последующая категория является, по сути, расширением предыдущей,
поэтому задаются только минимальные требования для итераторов.
Соответственно, вместо итератора одной категории, может использоваться итератор другой категории, расположенный в данной таблице "ниже" заданного.
Например, если алгоритму необходим итератор категории BidirectionalIterator, то
может использоваться итератор из категорий BidirectionalIterator и RandomAccessIterator,
но не InputIterator или ForwardIterator.
Однако, в некоторых реализациях алгоритмы, требующие, например, BidirectionalIterator могут прекрасно работать и с итераторами категорий InputIterator и ForwardIterator, но их использование, возможно, сделает код не переносимым.

Обозначения для предикатов:

UnaryPredicate	унарный предикат
BinaryPredicate	бинарный предикат

Croessmah · 23.03.2016, 16:44 **[ТС]**

Требования и условия:

EqualityComparable:

Выражение	Возвращаемый тип	Требование
a == b	конвертируемый в bool	== определяет отношение эквивалентности, имеющее следующие свойства: — For all a, a == a — If a == b, then b == a. — If a == b and b == c, then a == c.

MoveConstructible:

Выражение	Постусловие
T u = rv;	u эквивалентно значению rv до конструирования
T(rv)	T(rv) эквивалентно значению rv до конструирования
rv остается в неопределенном состоянии

CopyConstructible:

Выражение	Постусловие
T u = v;	значение v не изменяется и эквивалентно значению u
T(v)	значение v не изменяется и эквивалентно значению T(v)

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.1 All of

C++

1 2	template <class InputIterator, class UnaryPredicate> bool all_of (InputIterator first, InputIterator last, UnaryPredicate pred);

Эффект: проверяет, все ли элементы последовательности соответствуют заданному критерию
Возвращаемое значение: true - если для каждого итератора i в диапазоне [first, last) вызов предиката pred(*i) возвращает true, либо если диапазон [first, last) является пустым.
false - во всех остальных случаях.
Сложность: не более last-first сравнений (обращений к предикату)

Итак, данный алгоритм вернет true, только если предикат вернет true для всех значений.
Используем это:

C++

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
 
 
bool is_odd(int x)
{
    return x&1;//нечетное?
}
 
 
int main()
{
    std::vector<int> vec1{11, 7, 9, 95, 35, 13};
    std::vector<int> vec2{11, 7, 9, 95, 32, 13};
    std::cout << std::boolalpha << std::all_of(vec1.begin(), vec1.end(), is_odd) << std::endl;
    std::cout << std::boolalpha << std::all_of(vec2.begin(), vec2.end(), is_odd) << std::endl;
}

Вывод:

true
false

Для первой последовательности вызов all_of возвращает true,
т.к. все элементы являются нечетными и для них предикат is_odd возвращает true.
Во второй же последовательности закралось четное число (32), поэтому all_of возвращает false.

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.2 Any of

C++

1 2	template <class InputIterator, class UnaryPredicate> bool any_of(InputIterator first, InputIterator last, UnaryPredicate pred);

Эффект: определяет, если в последовательности хотя бы один элемент удовлетворяющий заданному критерию
Возвращаемое значение: false - если для всех итераторов i в диапазоне [first, last) вызов предиката pred(*i) возвращает false, либо если диапазон [first, last) является пустым.
true - во всех остальных случаях.
Сложность: не более last-first сравнений

Данный алгоритм вернет true, если есть хоть один элемент, для которого предикат вернет true:

C++

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
 
 
bool is_even(int x)
{
    return !(x&1);//четное?
}
 
 
int main()
{
    std::vector<int> vec1{11, 7, 9, 95, 35, 13};
    std::vector<int> vec2{11, 7, 9, 95, 32, 13};
    std::cout << std::boolalpha << std::any_of(vec1.begin(), vec1.end(), is_even) << std::endl;
    std::cout << std::boolalpha << std::any_of(vec2.begin(), vec2.end(), is_even) << std::endl;
}

Вывод:

false
true

В первом векторе нет четных чисел, поэтому получили false.
А во втором векторе есть, как минимум одно четное число, поэтому any_of возвращает true.

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.3 None of

C++

1 2	template <class InputIterator, class UnaryPredicate> bool none_of(InputIterator first, InputIterator last, UnaryPredicate pred);

Эффект: проверяет, все ли элементы последовательности не удовлетворяют заданному критерию
Возвращаемое значение: true - если для всех итераторов i в диапазоне [first, last) вызов предиката pred(*i) возвращает false, либо если диапазон [first, last) является пустым.
false - во всех остальных случаях.
Сложность: не более last-first сравнений

Данный алгоритм вернет true, только если предикат вернет false для всех элементов.

C++

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
 
 
bool is_odd(int x)
{
    return x&1;//нечетное?
}
 
 
int main()
{
    std::vector<int> vec1{11, 7, 9, 95, 35, 13};
    std::vector<int> vec2{11, 7, 9, 95, 32, 13};
    std::vector<int> vec3{12, 6, 8, 94, 32, 16};
    std::cout << std::boolalpha << std::none_of(vec1.begin(), vec1.end(), is_odd) << std::endl;
    std::cout << std::boolalpha << std::none_of(vec2.begin(), vec2.end(), is_odd) << std::endl;
    std::cout << std::boolalpha << std::none_of(vec3.begin(), vec3.end(), is_odd) << std::endl;
}

Вывод:

false
false
true

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

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.4 For each

C++

1 2	template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);

Требования: Function должна удовлетворять требованию MoveConstructible, и может не удовлетворять требованию CopyConstructible.
Эффекты: применяет f к результату разыменования каждого итератора i в диапазоне [first, last).
Если тип first удовлетворяет требованиям изменяемого итератора, то f может изменять элементы диапазона через разыменованный итератор.
Возвращаемое значение: std::move(f)
Сложность: применяет f точно last-first раз.
Примечание: возвращаемое значение f игнорируется.

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

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.5 Find

C++

template<class InputIterator, class T>
    InputIterator find(InputIterator first, InputIterator last, const T& value);
 
template<class InputIterator, class UnaryPredicate>
    InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
 
template<class InputIterator, class UnaryPredicate>
    InputIterator find_if_not(InputIterator first, InputIterator last, UnaryPredicate pred);

Эффект: ищет соответствующий элемент в последовательности
Возвращаемое значение: возвращает первый итератор i из диапазона [first, last),
удовлетворяющий условию:

Форма	Условие
find	*i == value
find_if	pred(*i) != false
find_if_not	pred(*i) == false

Возвращает last, если значение не найдено.

Сложность: не более last-first сравнений

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.6 Find end

C++

//1
template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 find_end
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2
    );
//2
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    ForwardIterator1 find_end
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2,
        BinaryPredicate pred
    );

Эффекты: ищет последнее вхождение подпоследовательности [first2, last2) в последовательность [first1, last1).
Возвращаемое значение: последний итератор i из диапазона [first1, last1 - (last2-first2)), такой, что для любого не отрицательного n < (last2-first2) выполняются условия:

Форма	Условие
1	(i + n) == (first2 + n)
2	pred((i + n), (first2 + n)) != false

Возвращает last1 если диапазон [first2,last2) пуст или если не найдена соответствующая подпоследовательность.
Сложность: не более (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) сравнений

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.7 Find first of

C++

//1
template<class InputIterator, class ForwardIterator>
    InputIterator find_first_of
    (
        InputIterator first1, InputIterator last1,
        ForwardIterator first2, ForwardIterator last2
    );
//2
template<class InputIterator, class ForwardIterator, class BinaryPredicate>
    InputIterator find_first_of
    (
        InputIterator first1, InputIterator last1,
        ForwardIterator first2, ForwardIterator last2,
        BinaryPredicate pred
    );

Эффекты: ищет в последовательности [first1, last1) элемент, соответствующий одному из элементов последовательности [first2, last2)
Возвращаемое значение: первый итератор i из диапазона [first1, last1) который, для итератора j из диапазона [first2, last2) удовлетворяет условию:

Форма	Услоние
1	i == j
2	pred(i,j) != false

возвращает last1, если диапазон [first2,last2) пуст или соответствующий элемент не найден.
Сложность: не более (last1-first1) * (last2-first2) сравнений

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.8 Adjacent find

C++

//1
template<class ForwardIterator>
    ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
//2
template<class ForwardIterator, class BinaryPredicate>
    ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

Эффекты: ищет пару подряд идущих равных между собой значений
Возвращаемое значение: первый итератор i из диапазона [first, last) удовлетворяющий условию

Форма	Условие
1	i == (i + 1)
2	pred(i, (i + 1)) != false

Возвращает last, если элементы не найдены.

Сложность: для не пустой последовательности точно min((i - first) + 1, (last - first) - 1) сравнений, где i - итератор, возвращенный adjacent_find.

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.9 Count

C++

template<class InputIterator, class T>
    typename iterator_traits<InputIterator>::difference_type
        count(InputIterator first, InputIterator last, const T& value);
 
template<class InputIterator, class UnaryPredicate>
    typename iterator_traits<InputIterator>::difference_type
        count_if(InputIterator first, InputIterator last, UnaryPredicate pred);

Эффекты: подсчет количества определенных элементов последовательности
Возвращаемое значение: количество итераторов i из диапазона [first, last), удовлетворяющих условию

Форма	Условие
count	*i == value
count_if	pred(*i) != false

Сложность: точно last-first сравнений

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.10 Mismatch

C++

//1
template<class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
//2
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    pair<InputIterator1, InputIterator2>
        mismatch
        (
            InputIterator1 first1, InputIterator1 last1, 
            InputIterator2 first2, BinaryPredicate pred
        );
//3
template<class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2>
        mismatch
        (
            InputIterator1 first1, InputIterator1 last1, 
            InputIterator2 first2, InputIterator2 last2
        );
//4
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
    pair<InputIterator1, InputIterator2>
        mismatch
        (
            InputIterator1 first1, InputIterator1 last1, 
            InputIterator2 first2, InputIterator2 last2,
            BinaryPredicate pred
        );

Эффекты: ищет первые различающиеся элементы последовательностей
Возвращаемое значение: пара итераторов i и j, где i принадлежит диапазону [first1, last1), j принадлежит диапазону [first2, last2), при этом j == first2 + (i-first1), для которых выполняется условие:

Форма	Условие
1, 3	!(i == (first2 + (i - first1)))
2, 4	pred(i, (first2 + (i - first1))) == false

Возвращает пару итераторов first1 + min(last1 - first1, last2 - first2) и first2 + min(last1-first1, last2 - first2) если элементы не найдены.

Сложность: не более min(last1 - first1, last2 - first2) сравнений
Примечание: если аргумент last2 не указан, то вторая последовательность имеет диапазон [first2, first2+(last1-first1))

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.11 Equal

C++

//1
template<class InputIterator1, class InputIterator2>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
//2
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    bool equal
    (
        InputIterator1 first1, InputIterator1 last1, 
        InputIterator2 first2, BinaryPredicate pred
    );
//3
template<class InputIterator1, class InputIterator2>
    bool equal
    (
        InputIterator1 first1, InputIterator1 last1,
        InputIterator2 first2, InputIterator2 last2
    );
//4
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
    bool equal
    (
        InputIterator1 first1, InputIterator1 last1,
        InputIterator2 first2, InputIterator2 last2,
        BinaryPredicate pred
    );

Эффекты: проверяет равенство последовательностей
Возвращаемое значение: если last1 - first1 != last2 - first2, то возвращается false, иначе возвращается true, если для каждого итератора i в диапазоне [first1, last1) выполняется условие:

Форма	Условие
1, 3	i == (first2 + (i - first1))
2, 4	pred(i, (first2 + (i - first1))) != false

во всех остальных случаях возвращается false.

Сложность: если InputIterator1 и InputIterator2 удовлетворяют требованиям итератора произвольного доступа и last1 - first1 != last2 - first2, то не выполняется ни одного сравнения элементов. В остальных случаях производится не более min(last1 - first1, last2 - first2) сравнений.
Примечание: если аргумент last2 не указан, то вторая последовательность имеет диапазон [first2, first2+(last1-first1))

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.12 Is permutation

C++

//1
template<class ForwardIterator1, class ForwardIterator2>
    bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
//2
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    bool is_permutation
    (
        ForwardIterator1 first1, ForwardIterator1 last1, 
        ForwardIterator2 first2, BinaryPredicate pred
    );
//3
template<class ForwardIterator1, class ForwardIterator2>
    bool is_permutation
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2
    );
//4
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    bool is_permutation
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2,
        BinaryPredicate pred
    );

Эффекты: проверяет, является ли последовательность заданная итераторами [first1, last1) перестановкой элементов последовательности, заданной итераторами [first2, last2)
Требования: ForwardIterator1 и ForwardIterator2 должны иметь одинаковые типы значений (value_type). Функция сравнения должна определять отношение эквивалентности(equivalence relation).
Возвращаемое значение: если last1 - first1 != last2 - first2, то возвращается false. Возвращается true, если одна из перестановок элементов диапазона [first2,first2 + (last1 - first1)), начинающаяся с некоторого итератора begin соответствует условию:

Форма	Условие
1, 3	equal(first1, last1, begin)
2, 4	equal(first1, last1, begin, pred)

то возвращается true. В ином случае возвращается false.

Сложность: если ForwardIterator1 и ForwardIterator2 удовлетворяют требованиям итератора произвольного доступа и last1 - first1 != last2 - first2, то сравнений элементов не происходит.
Если последовательности уже равны, то будет произведено ровно distance(first1, last1) сравнений.
Иначе, в худшем случае сложность будет квадратичной (O(N²)), где N == distance(first1, last1)
Примечание: если аргумент last2 не указан, то вторая последовательность имеет диапазон [first2, first2+(last1-first1))

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.13 Search

C++

//1
template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 search
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2
    );
//2
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    ForwardIterator1 search
    (
        ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2,
        BinaryPredicate pred
    );

Эффекты: ищет вхождение подпоследовательности [first2, last2) в последовательность [first1, last1).
Возвращаемое значение: первый итератор i из диапазона [first1,last1 - (last2-first2)), такой, что для любого не отрицательного n, меньшего чем last2 - first2, выполняется условие:

Форма	Условие
1	(i + n) == (first2 + n)
2	pred((i + n), (first2 + n)) != false

Возвращается first1 если диапазон [first2,last2) пустой, иначе возвращается last1 если соответствующая подпоследовательность не найдена.

Сложность: не более чем (last1 - first1) * (last2 - first2) сравнений

Croessmah · 23.03.2016, 16:44 **[ТС]**

1.14 Search N

C++

//1
template<class ForwardIterator, class Size, class T>
    ForwardIterator search_n
    (
        ForwardIterator first, ForwardIterator last, 
        Size count, const T& value
    );
//2
template<class ForwardIterator, class Size, class T, class BinaryPredicate>
    ForwardIterator search_n
    (
        ForwardIterator first, ForwardIterator last, 
        Size count, const T& value, 
        BinaryPredicate pred
    );

Требования: Size должен быть конвертируемым в целочисленный тип
Эффекты: ищет первую подпоследовательность из n элементов удовлетворяющих условию
Возвращаемое значение: первый итератор i из диапазона [first,last - count), такой, что для любого не отрицательного n, меньшего чем count, выполняется условие:

Форма	Условие
1	*(i + n) == value
2	pred(*(i + n),value) != false

Возвращается last если соответствующая подпоследовательность не найдена.
Сложность: не более чем last - first сравнений

	23.03.2016, 16:44