список в c

Список list в С++: полный материал

Всем привет! Не давно мы прошли вектор в C++, поэтому сегодня мы решили снова затронуть тему контейнеров и подготовили материал об еще одном контейнере — list.

Как это работает Что такое список list

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

На картинке ниже показана, как это устроено:
как работает list в C++

У двусвязного списка нет индексов, но вместо их в C++ есть итераторы.

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

На примере выше в начале было два элемента, потом мы решили добавить один элемент между ними.
пример удаление элемента из списка listпример удаление элемента из списка list

А так совершается удаление.

Как это сделать Как создать список list

Сначала подключаем библиотеку — <list> .

Далее используем конструкцию ниже:

  • < тип данных > — сюда мы должны указать тип, который хотим использовать.
  • <имя контейнера> — это будет нашим именем контейнера. Лучше указывать такое имя, которое будет говорить, за что этот контейнер отвечает.

Вот пример создания списка с типом string:

 Как добавить элементы при создании списка

Чтобы сразу после создания списка присвоить ему значения нужно сделать так:

Такой способ можно использовать только в C++ 11 и выше.

Методы списка list

Вот функции которые можно применять в своей программе вместе со списком (нажмите на их имена чтобы перейти на страницу с полным руководством):

Имя функции Описание
pop_front удалить элемент в начале
pop_back удалить элемент в конце
push_front добавить элемент в начала
push_back добавить элемент в конец
front обратится к первому элементу
back обратиться к последнему элементу
insert добавить элемент в какое-то место
copy вывести все элементы списка (и не только)
unique удалить все дубликаты
merge добавление другого списка

 

Давайте с несколькими методами познакомимся подробнее.

insert

С помощью его можно добавить новый элемент в любую часть контейнера (в нашем случае для списка). Вот как он работает:

  • Первым аргументом передаем — местоположение. Оно указывается итератором, что это читайте вот здесь.
  • Вторым значение новой ячейки. Здесь может быть как переменная так и просто значение (5 например).

copy

Вообще он имеет несколько видов применения:

  • Вывод элементов.
  • Запись элементов.
  • А также копирования какого-то количества ячеек и вставка их в позицию Y.

Чтобы его использовать дополнительно нужно подключить библиотеку — <iterator>.

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

Первые два значения (myspisok.begin(), myspisok.end()) которые должны передать, — это итераторы начала и конца контейнера.

Дальше используем итератор вывода — ostream_iterator<int>(cout," "). В кавычках указывается значение между элементами (в нашем случае это пробел).

unique

Удаляет все повторяющиеся элементы (дубликаты). Использовать его очень просто:

merge

Добавляет существующему списку еще один.

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

  • В строках 8 — 9: создали два списка — mylist и и второй listmerge.
  • В строках 11 — 16: идет добавление новых элементов с использованием insert.
  • В строке 17 как и в строке 22: выводим весь список с помощью функции copy.
  • В строке 25 удалили все дубликаты.
  • Стоит отметить, что в этой программе мы создали итератор (строка 26) и вывели с его помощью (операции разыменования) весь список.
  • Ну и в строке 32 соединили два списка в один — mylist.

Результат:

methods.cpp
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Если хотите познакомится с ними то перейдите по ссылкам.

Удаление элементов

Кроме удаления в начале и в конце с помощью методов pop_front() и pop_end(), также можно удалять:

  • Диапазон ячеек.
  • Одну произвольную ячейку.
  • Удалять по какому-то условию.
  • А также удалять все ячейки с значением X.

erase

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

Все позиции, которые должны указываться в аргументах erase — должны являться итераторами.

Во второй строчке не опечатка, из-за удаление одной ячейки итератор, который на нее указывает требуется обновить вот таким способам, чтобы он стал указывать на следующую ячейку.

Вот пример:

  • В строке 21: функция advance() сдвигает конечную позицию (pos_end) на 6 ячеек.
  • В строке 22: увеличиваем на один начальную позицию (pos_begin).
  • В строках 24 — 25: удаляем ячейку pos_begin и pos_end.
  • В строках 29 — 30: увеличиваем на один pos_begin и pos_end.
  • В строке 32: удаляем промежуток (pos_begin, pos_end).

Про функцию adsense мы поговорим ниже.

erase.cpp
Вот как заполнили список: 1 2 3 4 5 6 7 8 9 10
Список после удаления двух ячеек: 1 3 4 5 6 8 9 10
А вот что стало: 1 3 9 10
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

remove

Чтобы удалить все элементы со значением нужно использовать данную конструкцию <имя списка>.remove(X) :

remove.cpp
12 34 45 23 53 68 113 53
12 34 45 23 68
Process returned 0 (0x0) execution time : 0.005 s
Press any key to continue.

remove_if

С помощью данного метода можно удалять элементы соответствующие какому-то критерию (условию). Например элементы большие 100 (return val > 100).

Вот как она работает:

  • В функции number_single нужно указать вместо типа int тип вашего списка.
  • Далее в теле функции return val < 10; заменить вашим условием. В нашем случае удаляться все элементы меньшие 10.
  • Осталось лишь вызвать данную конструкцию:

Итераторы для list

Давайте подробнее разберем как оперировать итераторами в списках. Вот, например, в контейнере вектор мы можем свободно сдвигать итератор влево и вправо безо всяких опасений. Но для итераторов списка нельзя применять арифметические операции.

Хотя имеется возможность использовать инкремент и декремент, они немного сглаживают отсутствия нормального перемещения итератора.

А вот полностью сгладить этот казус может функция — advance(). Она позволяет передвинуть итератор на то место на которое мы скажем.

В скобках указываем два значения:

  • Первое — это имя итератора.
  • Второе — число, на которое нужно сдвинуть указанный итератор.

Так, если нам нужно его сдвинуть налево, простыми словами — уменьшить, то второй аргумент должен иметь знак минуса (-).

Вам нужно знать! Функция advance не знает к какому контейнеру принадлежит итератор, поэтому если итератор выйдет за диапазон, программа никак вас не оповестит.

Плюсы и минусы использования списков

Мы узнали о списке все, чтобы сделать вывод о о нем.

Плюсы:

  • Добавление и удаление ячеек осуществляется быстро.
  • Кроме добавления и удаления в конец, мы также можем добавить и удалить элемент в начале контейнера.

Минусы:

  • Медленное обращение к элементам, находящимся в центре.

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




Комментарии к записи “Список list в С++: полный материал”

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

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