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

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

Один комментарий: STL List поверхностное знакомство

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

Ваш e-mail не будет опубликован.

Поиск

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

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок