Алгоритм merge

10 20 30 40 50 60 70 80 90 100

10 20 30 40 80 90 100

10 20 30 40

Итераторы вставки и алгоритм сору

Обратные итераторы

Эта разновидность итераторов (reverse_iterator) очень удобна для прохода по контейнеру от конца к началу. Например, если в программе имеется контейнер vector<double> v1, то для вывода содержимого вектора в обратном порядке можно написать:

vector<double>::reverse_iterator r1;

r1 = v1.rbegin();

while (ri!= v1.rend())

cout << *r1++ << ' ';

Обратите внимание на то, что операция инкремента для такого итератора перемещает указатель на предыдущий элемент контейнера.

Мы можем использовать алгоритм сору для копирования элементов одного контейнера в другой, причем источником может быть, например, вектор, а приемником — список, как показывает следующая программа:

int main() {

int а[4] = {10, 20, 30, 40};

vector<int> v(a, a + 4);

list<int> L(4); // список из 4 элементов

copy(v.begin(), v.end(), L.begin());

print(L);

return 0;

}

Алгоритм copy при таком использовании, как в этом примере, работает в режиме замещения. Это означает, что 1 -й элемент контейнера-источника замещает 1 -й элемент контейнера-приемника.

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

Итераторы вставки front_inserter(), back_inserter(), inserter() предназначены для добавления новых элементов в начало, конец или произвольное место контейнера.

Покажем использование этих итераторов на следующем примере.

int main() {

int а[4] = {40, 30, 20, 10};

vector<int> va(a, a + 4);

int b[3] = {80, 90, 100};

vector<int> vb(b, b + 3);

int c[3] = {50, 60, 70};

vector<int> vc(c, с + 3);

list<int> L; // пустой список

copy(va.begin(), va.end(), front_inserter(L));

print(L);

copy(vb.begin(), vb.end(), back_inserter(L));

print(L);

list<int>::iterator from = L.begin();

advance(from, 4);

copy(vc.begin(), vc.end(), inserter(L, from));

print(L);

return 0;

}

Результат выполнения программы:

Обратите внимание на следующие моменты:

• Первый вызов функции сору осуществляет копирование (вставку) вектора va в список L, причем итератор вставки front_inserter обеспечивает размещение очередного элемента вектора va в начале списка — поэтому порядок элементов в списке изменяется на обратный.

• Второй вызов сору пересылает элементы вектора vb в конец списка L благодаря итератору вставки back_inserter, поэтому порядок копируемых элементов не меняется.

• Третий вызов сору копирует вектор vc в заданное итератором from место списка L, а именно после четвертого элемента списка. Чтобы определить нужное значение итератора from, мы предварительно устанавливаем его в начало списка, а затем обеспечиваем приращение на 4 — вызовом функции advance().

Алгоритм merge выполняет слияние отсортированных последовательностей для любого типа последовательного контейнера, более того — все три участника алгоритма могут представлять различные контейнерные типы. Например, вектор а и массив b могут быть слиты в список с:

int main() {

int arr[5] = {2, 3, 8, 20, 25};

vector<int> a(arr. arr + 5);

int b[6] = {7, 9, 23, 28, 30, 33};

list<int> c; // Список с сначала пуст

merge(a.begin(). a.end(), b, b + 6, back_inserter(c));

print(c);

return 0;

}

Результат выполнения программы: