|
Контейнеры типа 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"); |
