list<int>: :iterator i = L.beginO;

++i; ++i;

copy(v.begin(), v.end О, inserter(L, i));

for (i=L.begin() ; i != L.endO; + + i) cout « *i « " ",-

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 иллюстрирует операцию объединения:


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

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

// merge.cpp: Объединение вектора и массива в список. #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> с; // Список с сначала пуст

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

list<int>::iterator i;

for (i=c.begin(); i != c.endt); ++i) cout « *i « " " ;

cout « endl;

return 0; }

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

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

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

2  3   7   8  9  20  23  25  28  30  33

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

2-858


<< назад вперед >>