26 января 2021 года    
Вторник | 02:55    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







 

Последовательности типа 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");

 

Лента новостей


2006 (c) Copyright Hardline.ru