А это единственная отправная точка, если ранее не был получен итератор, находящийся ближе к нужной позиции,

То есть перестановка элементов в обратном порядке, - Примем, перев.

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

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

Объекты в списке никогда не перемещаются в памяти после создания. Перемещение элемента сводится к простому изменению ссылок и не требует копирования/присваивания самих объектов. Следовательно, добавление новых элементов в список не приводит к аннулированию итераторов, в отличие от контейнера vector. В следующем примере используется список объектов Noisy:

: C07:ListStability.cpp {-bor}

Элементы списков не перемещаются в памяти

{L} Noisy

#include Noisy.h

#include <algorithm>

iinclude <iostream>

iinclude <iterator>

iinclude <1ist>

using namespace std:

int mainO ( list<Noisy> 1:

ostreamjterator<Noisy> out(cout. ); generate n(backjnserter(l), 25, NoisyGenO): cout \n Printing the list: endl: copyd .beginO. l.endO, out): cout \n Reversing the list: endl: 1 .reverseO:

copyd .beginO, l.endO, out):

cout \n Sorting the list: endl:

l.sortO:

copyd .beginO. l.endO. out):

cout \n Swapping two elements: endl:

list<Noisy>::iterator itl, it2:

itl = it2 = 1 .beginO:

++it2:

swap(*itl. *it2): cout endl:

copyd .beginO. l.endO, out):

cout \n Using generic reverseO: endl:

reversed .beginO. l.endO):

cout endl:

copyd .beginO. l.endO, out): cout \n Cleanup endl: } /:-

Даже такие внешне трудоемкие операции, как сортировка и обращение списка, не требуют копирования объектов - вместо этого достаточно изменить соответствующие ссылки. Однако следует учесть, что функции sort() и reverse() являются функциями класса list, поэтому они знают о внутреннем устройстве контейнера

и умеют переставлять элементы без копирования. С другой стороны, обобщенный алгоритм swapO ничего не знает об особенностях list, поэтому он меняет два элемента местами через присваивание. В общем случае вместо обобщенных алгоритмов рекомендуется задействовать эквивалентную функцию класса (если она существует). В частности, обобщенные алгоритмы sort() и reverse() следует использовать только с массивами, векторами и деками.

Если вы работаете с большими сложными объектами, попробуйте начать со списка, особенно если операции конструирования, уничтожения, конструирования копий и присваивания обходятся достаточно дорого, а вы собираетесь часто сортировать объекты или иным образом изменять порядок их следования.

Специальные операции со списками

Контейнер list содержит специальные функции, которые с максимальной эффективностью используют особенности его структуры. Функции reverse() и sort() уже упоминались выше. Следующий пример демонстрирует еще несколько таких функций:

: C07;ListSpec1alFunct1ons.cpp

{L} Noisy

#inc1ude <algorithm>

#1 nclude <1ostream>

#1 nclude <iterator>

#i nclude <l1st>

#include Noisy.h

#include PrintContainer.h

using namespace std:

int mainO { typedef l1st<Noisy> LN: LN 11. 12. 13. 14:

generate n(back inserter(ll), 6. NoisyGenO) generate n(back inserter(12). 6. NoisyGenO) generate n(back inserter(13). 6, NoisyGenO) generate n(back inserter(14), 6. NoisyGenO) printdl. 11 ): print(12, 12 ): pnnt(13, 13 ): print(14. 14 ): LN::iterator itl = 11.beginO: ++itl: ++itl: ++itl: ll.splice(itl. 12):

printdl. 11 after splice(itl. 12) ): print(12. 12 after splice(itl. 12) ): LN: :iterator it2 = 13.beginO: ++it2: ++it2: ++it2: ll.splicedtl. 13. it2): printdl. 11 after splice(itl, 13. it2) ): LN::1terator it3 = 14.beginO. it4 = 14.end(): ++it3; --it4:

U.spliceCitl. 14. it3, it4): printdl. 11 after splice(itl,14,it3.it4) ): Noisy n: LN 15(3, n):

generate n(back inserter(15). 4, NoisyGenO): 15.push back(n):

printd5. 15 before removed ): 15. removed 5. frontO): print(15, 15 after removeO ): U.sortO: 15.sort():

IS.mergedl):

printdS. 15 after 15.merge(ll) ): cout \n Cleanup endl: } III:-

После заполнения четырех списков объектами Noisy производятся три операции врезки. Сначала весь список 12 вставляется в список И в позиции итератора itl, причем список 12 остается пустым - врезка приводит к удалению элементов из исходного списка. Вторая операция врезки вставляет элементы списка 13, начиная с it2, в список 11, начиная с позиции itl. Третья врезка начинается с позиции itl и использует элементы списка 14 в интервале от it3 до it4. Излишнее на первый взгляд упоминание списка-источника объясняется тем, что стирание элементов из источника является частью операции их пересылки в приемник.

Результаты тестирования функции remove() показывают, что удаление всех элементов с заданным значением не требует предварительной сортировки списка.

Наконец, слияние списков функцией merge() работает разумно только в том случае, если списки были отсортированы. Тогда вы получаете отсортированный список, содержащий все элементы обоих списков (при этом источник остается пустым, то есть его элементы перемещаются в приемник).

Функция uniqueO удаляет все дубликаты из предварительно отсортированного списка:

: C07:UniqueList.cpp

Тестирование функции uniqueO контейнера list #include <iostream> #include <iterator> #include <list> using namespace std:

int a[] = ( 1. 3. 1. 4. 1, 5. 1, 6. 1 }: const int asz = sizeof a / sizeof *a:

int mainO { Для вывода:

ostream iterator<int> out(cout. ): list<int> li(a. a + asz): li .uniqueO:

Ошибка! Дубликаты остаются в контейнере: copyd i .beginO. li.endO. out): cout endl:

Список необходимо предварительно отсортировать: li.sortO:

copyd i .beginO. li.endO, out): cout endl:

Теперь функция uniqueO работает правильно: li.unique():

copyd i .beginO. li.endO, out): cout endl: } III:-

Использованный в этом примере конструктор list получает начальный и конечный итераторы из другого контейнера и копирует все элементы из заданного интервала. В данном случае контейнером является простой массив, а итераторами - указатели на элементы этого массива, но благодаря архитектуре STL конструктор list работает с массивами так же легко, как с любыми другими контейнерами.