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