cout endl; return 0;

Начальное содержимое списка L таково:

123 123 123 123 123

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

inserter(L, i)

которое вычисляется при вызове алгоритма сору. В результате третий элемент списка и оба элемента, следующие за ним, сдвигаются на четыре позиции вправо, а на место третьего элемента вставляются значения 10, 20, 30 и 40. Это объясняет следующий результат работы данной программы:

123 123 10 20 30 40 123 123 123 Ввод и вывод

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

1.7. Алгоритм merge

Рисунок 1.3 иллюстрирует операцию объединения:

Контейнер а 2 3 8 20 25

Результирующий контейнер с

2 3 7 8 9 20 23 25 28 30 33

Контейнер b

7 9 23 28 30 33

Рисунок 1.3. Объединение а и b в с

Алгоритм объединения merge может быть использован для каждого из четырех типов последовательных контейнеров (массивы, векторы, двусторонние очереди и списки). Удивительно, что три участника алгоритма (а,Ьяс на рисунке 1.3) не обязаны принадлежать к одному и тому же контейнерному типу. Чтобы продемонстрировать этот факт, давайте объединим вектор а и массив b в список с:

merge.срр: Объединение вектора и массива в список. #include <iostream> #include <vector> #include <list> #include <algorithm>

using namespace std;

int main()

{ vector<int> a(5);

a[0] = 2; a[l] = 3; a[2] = 8;

a[3] = 20; a[4] = 25;

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

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

merge (а. begin О , a.endO, b, b+6,

inserter (с, c.beginO)); list<int>::iterator i; for (i=c.begin() ; i != c.endO; + + i)

cout *i ; cout endl; return 0;

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

list<int> с(11); принимаем 5 + 6 = 11 элементов merge (а. begin О , a.endO, b, b+6, c.beginO);

выделив достаточно места при определении принимающего списка с. Сам по себе алгоритм merge работает в режиме замещения, то есть не создает новых элементов контейнера, а помещает значения в существующие. Чтобы вставлять новые элементы при объединении, мы должны использовать вставляющий итератор, как показано в полной программе. В любом случае результат работы программы следующий:

2 3 7 8 9 20 23 25 28 30 33

Как и в разделе 1.4, мы использовали операцию доступа по индексу, написав, например, а[0], хотя а является вектором, а не массивом. Такое же обозначение доступа к элементу используется для двусторонних очередей, но не для списков. Напомним, что списки отличаются от массивов, векторов и двусторонних очередей тем, что мы не можем использовать их вместе с алгоритмом сортировки. К этому вопросу мы вернемся в разделе 1.9.

2-858

1.8. Типы, определенные пользователем

До сих пор все контейнеры, которые мы использовали, содержали элементы типа int. Кроме стандартных типов, таких как int, в контейнерах STL можно хранить типы, определенные пользователем. Так как вызов merge{...) в программе merge.cpp основан на операции сравнения меньше чем <, такой вызов для новых типов возможен, только если мы для этих типов определяем operator. Покажем это на простом примере:

merge2.срр: Объединяем записи, используя имена в качестве ключей.

#include <iostream> #include <string> #include <algorithm> using namespace std;

struct entry { long nr; char name[30];

bool operator<(const entry &b)const { return strcmp(name, b.name) < 0; }

int mainO

{ entry a[3] = {{10, Betty }, {11, James }, {80, Jim }}, b[2] = {{16, Fred },

{20, William }}, c[5], *p; merge(a, a+3, b, b+2, c); for (p=c; p != c+5; p++)

cout p->nr << p->name endl; cout endl; return 0;

Для работы программы существенно, что имена в каждом из массивов аиЬ располагаются в алфавитном порядке. Программа объединяет а и 6 в с (в соответствии с алфавитным порядком имен), как показывает результат программы:

10 Betty 16 Fred

11 James 80 Jim

20 William