Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2016, 16:44     Краткий справочник по алгоритмам STL
Еще ссылки по теме:

Краткий справочник по С++ C++
C++ Разработка программ по типовым алгоритмам
Посоветуйте литературу по алгоритмам C++
Книги по алгоритмам (с примерами на С++) C++
Посоветуйте книги по генетическим алгоритмам C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #1
Данная тема создана как справочник по алгоритмам 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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
#2

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

23.03.2016, 16:44. Просмотров 514. Ответов 16
Метки нет (Все метки)

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

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

Обозначения для предикатов:
UnaryPredicateунарный предикат
BinaryPredicateбинарный предикат
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #3
Требования и условия:

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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #4
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #5
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #6
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #7
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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #8
1.5 Find
C++
1
2
3
4
5
6
7
8
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_ifpred(*i) != false
find_if_notpred(*i) == false
Возвращает last, если значение не найдено.

Сложность: не более last-first сравнений
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #9
1.6 Find end
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//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)
2pred(*(i + n), *(first2 + n)) != false
Возвращает last1 если диапазон [first2,last2) пуст или если не найдена соответствующая подпоследовательность.
Сложность: не более (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) сравнений
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #10
1.7 Find first of
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//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
2pred(*i,*j) != false
возвращает last1, если диапазон [first2,last2) пуст или соответствующий элемент не найден.
Сложность: не более (last1-first1) * (last2-first2) сравнений
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #11
1.8 Adjacent find
C++
1
2
3
4
5
6
//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)
2pred(*i, *(i + 1)) != false
Возвращает last, если элементы не найдены.

Сложность: для не пустой последовательности точно min((i - first) + 1, (last - first) - 1) сравнений, где i - итератор, возвращенный adjacent_find.
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #12
1.9 Count
C++
1
2
3
4
5
6
7
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_ifpred(*i) != false

Сложность: точно last-first сравнений
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #13
1.10 Mismatch
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//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, 4pred(*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
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #14
1.11 Equal
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//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, 4pred(*i, *(first2 + (i - first1))) != false
во всех остальных случаях возвращается false.

Сложность: если InputIterator1 и InputIterator2 удовлетворяют требованиям итератора произвольного доступа и last1 - first1 != last2 - first2, то не выполняется ни одного сравнения элементов. В остальных случаях производится не более min(last1 - first1, last2 - first2) сравнений.
Примечание: если аргумент last2 не указан, то вторая последовательность имеет диапазон [first2, first2+(last1-first1))
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #15
1.12 Is permutation
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//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, 3equal(first1, last1, begin)
2, 4equal(first1, last1, begin, pred)
то возвращается true. В ином случае возвращается false.

Сложность: если ForwardIterator1 и ForwardIterator2 удовлетворяют требованиям итератора произвольного доступа и last1 - first1 != last2 - first2, то сравнений элементов не происходит.
Если последовательности уже равны, то будет произведено ровно distance(first1, last1) сравнений.
Иначе, в худшем случае сложность будет квадратичной (O(N2)), где N == distance(first1, last1)
Примечание: если аргумент last2 не указан, то вторая последовательность имеет диапазон [first2, first2+(last1-first1))
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #16
1.13 Search
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//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)
2pred(*(i + n), *(first2 + n)) != false

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

Сложность: не более чем (last1 - first1) * (last2 - first2) сравнений
Croessmah
Модератор
Эксперт CЭксперт С++
12690 / 7164 / 799
Регистрация: 27.09.2012
Сообщений: 17,658
Записей в блоге: 2
Завершенные тесты: 1
23.03.2016, 16:44  [ТС]     Краткий справочник по алгоритмам STL #17
1.14 Search N
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//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
2pred(*(i + n),value) != false
Возвращается last если соответствующая подпоследовательность не найдена.
Сложность: не более чем last - first сравнений
Закрытая тема Создать тему
Опции темы

Текущее время: 06:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru