Последовательности типа list



Последовательности типа list

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

В шаблоне класса list определены методы merge, reverse, unique, remove и remove_if, которые оптимизированы для списков. Не путайте их с одноименными шаблонами функций, которые определены в алгоритмах. В примере, который приведен ниже, обратите внимание на операции слияния как списков, так и контейнеров различной природы. При исследовании списков не забудьте вставить директиву #include <list>, а также приведенный выше набор объектов класса Man:

void main 0

{

list<Man> men;

men.push_front(zorah);

men.push_back(mela);

men.push_back(joy);

pr(men,"Man List");


//======== Поиск объекта

list<Man>::iterator p = find (men.begin(),men.end(),mela);

//======== Вставка перед элементом

p = men.insert (p,joe);

// одного объекта men.insert(p,2,joe);

// двух объектов pr(men,"After inserting 3 joes");

//======== Удаление всех вхождений joe

men.remove(j oe);

men.sort(less<Man>() ) ;

pr(men,"After removing all joes and sort");

//======== Создаем второй список

list<Man> li(3,simon);

//======== Сливаем его с первым

. men.merge (li, less<Man>'() );

pr(men,"After merging with simons list");

//==== После слияния второй список полностью исчез

cout « "\n\tAfter merging simons li.size: "

« li.size() « endl;

men.remove(s imon);

//======== Создаем очередь

deque<Man> d(men.size());

//======== Копируем в нее список

copy(men.begin(), men.end(), d.begin());

pr(d,"Deque copied from list");

//======== Создаем вектор

vector<Man> v (men. size () + d.sizeO);

//==== Соединяем список и очередь и помещаем в вектор merge(men.begin(),men.end(),d.begin(),d.end(), v.begin() ) ;

pr(v,"Vector after merging list and deque");

pr(d,"Deque after merging with list");

cout«"\n\n";

}

После слияния (merge) двух списков (men и li) размер второго списка стал нулевым, так как он полностью влился в первый. При слиянии методом list: emerge элементы не копируются, а вливаются в список-мишень операции. При слиянии с помощью алгоритма merge контейнеры операнды остаются невредимыми, так как они копируются в контейнер-мишень. Если операнды операции слияния упорядочены, то при слиянии методом list::merge упорядоченность не нарушается, чего не наблюдается при слиянии шаблоном функции merge. Приведем для ясности результат работы рассматриваемой программы:

Man List # Sequence:

1. Zoran Todorovitch, Age: 27

2. Melissa Robinson, Age: 9

3. Joy Amore, Age: 18

After inserting 3 joes # Sequence:

1. Zoran Todorovitch, Age: 27

2. Joe Doe, Age: 30

3. Joe Doe, Age: 30

4. Joe Doe, Age: 30

5. Melissa Robinson, Age: 9 6. Joy Amore, Age: 18

After removing all joes and sort # Sequence:

1. Melissa Robinson, Age: 9

2. Joy Amore, Age: 18

3. Zoran Todorovitch, Age: 27

After merging with simons list # Sequence: 1. Melissa Robinson, Age: 9

2. Simon Paul, Age: 15

3. Simon Paul, Age: 15

4. Simon Paul, Age: 15

5. Joy Amore, Age: 18

6. Zoran Todorovitch, Age: 27

After merging Simons li.size: 0 Removing simons

Deque copied from list # Sequence:

1. Melissa Robinson, Age: 9

2. Joy Amore, Age: 18

3. Zoran Todorovitch, Age: 27

Vector after merging list and deque f Sequence:

1. Melissa Robinson, Age: 9

2. Joy Amore, Age: 18

3. Melissa Robinson, Age: 9

4. Joy Amore, Age: 18

5. Zoran Todorovitch, Age: 27

6. Zoran Todorovitch, Age: 27

Deque after merging with list # Sequence:

1. Melissa Robinson, Age: 9

2. Joy Amore, Age: 18

3. Zoran Todorovitch, Age: 27

Генерирование последовательности

С помощью алгоритма generate удобно создавать последовательности, имеющие строго определенную структуру. Например, если объявлен список целых из шести элементов, то его можно заполнить значениями, сгенерированными с помощью функции generate:

//========= Создаем список целых

list<uint> 1st (6);

//========= Генерируем степенную последовательность

generate (1st.begin (), Ist.end(), pows);

pr(1st,"List of generated powers");

Здесь pows — это внешняя функция, которая при каждом обращении возвращает возрастающую степень двойки. Эффект достигается за счет того, что static-переменная г инициализируется единицей во время компиляции, а затем помнит свое предыдущее значение:

uint pows()

{

static uint r = 1;

return r <= 1;

}

Если надо добиться обратного эффекта, то есть убрать закономерность в последовательности чисел, то можно воспользоваться шаблоном функции random_shuffle, которая переставляет элементы последовательности в одно из п! состояний. Например:

vector <int> v;

for (int i = 0; i <= 6; i++ ) v.push_back(i+1);

random_shuffle(v.begin() , v.end()) ;

pr(v,"Vector of shuffled numbers");



Содержание раздела