STL List поверхностное знакомство

Что такое list в STL? Это такой контейнер (хранилище элементов одинакового типа), который представляет собой двусвязный список. Двусвязный список являет собой сущность, где каждый отдельный внутренний элемент имеет прямую связь со своими соседствующими элементами, при этом любые не соседствующие элементы друг с другом никаких связей не имеют и ничего друг о друге не знают.
На анимированном рисунке очень ограничено показана приблизительная архитектура списка. Для нас этот рисунок может быть сложен и трудно понимаем. Просто, должны же мы приблизительно понимать, о чем говорим.

Список STL

Каждый элемент списка list, за исключением первого и последнего, связан с предшествующим и последующим элементом, благодаря чему такой список можно проходить в двух направлениях: слева-направо и справа-налево. Принципиальное различие между list и vector заключается в том, что list обеспечивает вставку и удаление за постоянное время в любой позиции списка. Правда, непосредственно вставку в середину списка мы сделать не можем.

Дело в том, что чтобы вставить элемент в середину списка, нужно до этой середины дойти. Список не обладает произвольными итераторами, а те итераторы, которыми он обладает, не поддерживают операций + и . Т. е. нельзя написать l1.begin + 1;, только потому что итераторы у списка двунаправленные. Зато можно установить независимый итератор на любую позицию списка и уже используя его вставлять элемент.

В этом примере использовалась функция advance(). Это такая функция, которая наделяет возможностью смещения любого итератора. Это полезно, потому что для некоторых итераторов не определено операций += и -=. В том случае, если используется двунаправленный итератор или итератор произвольного доступа, смещение со знаком означает отодвинуть итератор назад, а со знаком + (или без знака вообще), означает отодвинуть итератор вперед.

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

Список отличий списка(list) от вектора и дека:

  • Отсутствие произвольного доступа. Быстрый доступ существует только к первому и последнему элементу списка. Оттакливаясь от первого или последнего элемента списка, можно получить доступ к любому элементу внутри. Такой обход выполняется по существующей цепочке связей внутри списка. Обход можно делать и с первого, и с последнего элемента.
  • Вставка и удаление элементов выполняется одинаково быстро (при условии, что итератор уже установлен в эту позицию). И вставка, и удаление выполняются за константное время. При вставке или удалении не требуется смещать элементы, поэтому и вставка, и удаление происходит очень быстро, а все операции сводятся к манипулированию указателями.
  • Вставка в список никогда не делает недействительными никакие итераторы, а операция удаления из списка делает невалидными только итераторы, указывающие на удаленный элемент.
  • Список поддерживает обработку исключений таким образом, что почти каждая операция либо выполняется успешно, либо не выполняется вообще. Таким образом список не может оказаться в промежуточном положении из-за незавершенной операции.
  • Списки содержат такие функции, как front(),push_front(),pop_front() и back(),push_back(),pop_back().
  • У списков нельзя получить доступ к элементу подобно массиву, используя [] и нельзя с помощью .at(), потому как списки не поддерживают произвольный доступ.
  • Списки не поддерживают операции изменения ёмкости и перераспределения памяти, потому как такие операции спискам не требуются. Каждый объект внутри списка занимает свою собственную ячейку в памяти, и та ячейка будет оставаться корректной вплоть до того момента, пока объект не будет удалён.
  • Списки содержат много функций для перемещения и удаления элементов. Эти функции выполняются быстрее чем аналогичные функции из общих алгоритмов, потому что в случае со списками функции списков всего-лишь перенаправляют указатели и никак не затрагивают сами объекты.
  • vector делает упор на быстрый произвольный доступ, a list — на быструю вставку и удаление элементов.
К спискам следует прибегать, когда по ходу работы программы требуется большое количество вставок и/или удалений во внутренних позициях и практически не требуется переходить из одной позиции в другую, весьма удаленную. Такие связные структуры часто используются вместо массивов, просто потому, что они в состоянии динамически увеличиваться;

Важно

  • При работе со списком вызвающая сторона должна гарантировать, что в списке есть хотя бы 1 элемент. Если список пуст, то любой обход списка приводит к неопределенному поведению (UB).
Вообще, со списком во многих случаях можно работать как с вектором. Например, начальный ввод данных ничем не отличается. Мой пример просто пример немного другого способа ввода данных, на самом деле можно использовать push_back() в цикле как у вектора, и наоборот: приводимый мой пример может работать и с вектором. Это Не особенность списка.
Пример заполнения списка с клавиатуры и вывода на экран (ввод в список прекращается после ввода любого значения не соответствующего типу данных, хранимых в списке)

Пример удаления из list всех элементов равных 10

Если нужно удалить только одно значение, то нужно узнать место этого значения внутри списка. Для этого используются итераторы (итераторы это наш посредник между STL и нами), так вот нужно использовать итераторы и обобщенный алгоритм find. find нам вернет итератор, который указывает на адрес такого элемента.

Если для списка list есть какой-то алгоритм, который работает эффективнее, чем обобщенный алгоритм к этому списку, то для списка определена специальная функция (например, список MyList, MyList.sort(),MyList.remove()). Если нет алгоритма, который работает эффективнее, чем аналогичный обобщенный алгоритм, то тогда для списка нет специальной функции, и если в алгоритме не требуются итераторы с произвольным доступом, то тогда такой обобщенный алгоритм применяется к списку. Такие алгоритмы, как правило, работают одинаково эффективно для разного вида контейнеров. Сейчас и был приведен пример с find. find одинакого быстр и для списка и для вектора, быстрее чем этот алгоритм для списка нету, поэтому у списка отсутствует такая функция поиска как find или search и заменяется она обычным обобщенным алгоритмом. Аналогично для всех других ситуаций. Поэтому если у списка есть какая-то одноименная функция, схожая с обобщенным алгоритмом, то лучше для списка применять именно её, а не обобщенный алгоритм, потому что она учитывает структуру списка и работает эффективнее, а вот если нету такой специальной функции, то нужно использовать либо обобщенный алгоритм, либо использовать алгоритм нельзя в силу ограничений из-за, например, итераторов, не имеющих произвольного доступа.

Ну и предлагаю решить простую задачку. Нужно создать список из 20 элементов. Заполнить этот список любыми значениями. Вставить в каждую позицию списка, кратную 3, цифру 100. Использовать цикл while

Пример:
Список: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
тут ваш код
Вывод 1,2,100,3,4,100,5,6,100,7,8,100,9,10,100,11,12,100,13,14,100,15,16,100,17,18,100,19,20

4 комментария на «“STL List поверхностное знакомство”»

  1. Junior007:

    Отличная статья, Спасибо! Первый раз пишу комменты к статьям

  2. Аноним:

    Отличная статья!

  3. Аноним:

    В пятом по счёту изображении вместо «;» стоит «ж» у using namespace!

  4. Для лучшего понимания процесса можно попросить привести пару примеров практического применения такого списка. А то и  самом деле пока «каша».

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/brayan-p-hogan/html5-i-css3-veb-razrabotka-po-standartam-novogo-pokoleniya-11643814/?lfrom=15589587

Последние комментарии

Яндекс.Метрика