Практикум по спецкурсу Стандартная библиотека C++

Задание 1. Обобщенные алгоритмы

Реализовать следующие алгоритмы. Привести примеры их работы с вектором и списком.

1.

template<typename FwdIt, typename Pred>
FwdIt adjacent_find(FwdIt first, FwdIt last, BinPred pr);

Ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first , last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Равенство понимается в смысле выполнения бинарного предиката BinPred pr.

2.

template<typename FwdIt1, typename FwdIt2>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);

Bозвращает итератор, указывающий на первую позицию в диапазоне [first1, last1), начиная с которой второй диапазон входит как подпоследовательность.

3.

template<typename FwdIt1, typename FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);

Возвращает итератор, указывающий на первое вхождение любого элемента последовательности [first2, last2) в последовательности, ограниченной итераторами [first1, last1).

4.

template<typename InIt, typename OutIt, typename Unop>
OutIt transform(InIt first, InIt last, OutIt x, Unop uop);

Генерирует новую последовательность, применяя операцию uop к каждому элементу из диапазона [first1 , last1). Bозвращает итератор за концом скопированных данных во второй последовательности.

5.

template<typename InIt, typename OutIt, typename T>
OutIt replace_copy(InIt first, InIt last, OutIt x, const T& vold, const T& vnew);

Заменяет в диапазоне [first, last) все элементы со значением vold на vnew , копируя результат в новую последовательность. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным.

6.

template<typename FwdIt, typename Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);

Удаляет из диапазона [first , last) все элементы, для которых значение предиката pr равно true. Удаленные элементы сдвигаются в конец контейнера. Возвращает итератор на первый удаленный элемент.

7.

template<typename InIt, typename OutIt, typename T>
OutIt remove_copy(InIt first, InIt last, OutIt x, const T& val);

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

8.

template<typename InIt, typename OutIt, typename Pred>
OutIt remove_copy_if(InIt first, InIt last, OutIt x, Pred pr);

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

9.

template<typename FwdIt>
FwdIt unique(FwdIt first, FwdIt last);

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

10.

template<typename RanIt>
void random_shuffle(RanIt first, RanIt last);

Переставляет элементы из диапазона [first, last) в случайном порядке.

11.

template<typename BidIt, typename Pred>
void partition(BidIt first, BidIt last, Pred pr);

Переупорядочивает элементы в диапазоне [first, last). Все элементы, для которых предикат pr равен true, помещаются перед элементами, для которых он равен false.

12.

template<typename InIt1, typename InIt2, typename OutIt>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

Объединяет две отсортированные последовательности в одну. Возвращает итератор, который указывает на элемент, расположенный за последним скопированным.

13.

template<typename InIt1, typename InIt2>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

Определяет, содержится ли множество [first1, last1) во множестве [first2, last2).

14.

template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

Записывает начиная с итератора x результат объединения множеств [first1, last1) и [first2, last2).

15.

template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x);

Записывает начиная с итератора x результат пересечения множеств [first1, last1) и [first2, last2).

16.

template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

Записывает начиная с итератора x результат разности множеств [first1, last1) и [first2, last2).

17.

template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

Записывает начиная с итератора x результат симметрической разности множеств [first1, last1) и [first2, last2).

18.

template<typename InIt1, typename InIt2>
bool lexicographical_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

Осуществляет лексикографическое сравнение последовательностей множеств [first1, last1) и [first2, last2) на <.