Списки В STL

Списки В STLСписки — это последовательные контейнеры. Списки содержат элементы в несмежных местах.

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

Список — это контейнер, в котором преодолен этот недостаток массивов и векторных контейнеров. Но это позволяет нам вставлять элементы в любом месте списка, не вызывая большой траты времени.

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

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

Инициализация

Для реализации контейнера списка и использования всех его преимуществ нам необходимо включить в нашу программу заголовочный файл <list>:

#include <list>

Общее объявление контейнера списка:

std::list<objectType> listName;

Например, мы можем объявить список с именем «mylist» типа int следующим образом:

std::list<int> mylist;

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

Давайте посмотрим, как мы можем инициализировать список, который мы создали выше:

std::list<int> mylist = {1, 1, 2, 3, 5};

Вышеупомянутая инициализация будет размещена в памяти, как показано ниже:

Инициализация 1

Как только мы инициализируем список, мы можем получить доступ к элементам списка с помощью итератора. Функции итератора «begin» и «end» помогают нам перемещаться по элементам списка.

Кстати, итератор для списка также поддерживает другие итераторы, такие как обратные итераторы (rbegin, rend), константные итераторы (cbegin, cend) и константные обратные итераторы (crbegin, crend), и могут использоваться аналогично векторам.

Следующий пример показывает это:

Вывод данных:

List elements are: 1 1 2 3 5

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

Теперь давайте перейдем к операциям или функциям, которые предоставляет нам контейнер list в STL.

Список операций

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

insert(pos, num_elem, elem)

pos=> Позиция, в которую должны быть вставлены новые элементы.
num_elem=> Количество вставляемых элементов; по умолчанию 1.
elem=> Вставляемое фактическое значение.

Читать также:  Массивы C++ с примерами

Давайте разберемся с функцией insert на примере:

Вывод данных:

The list after inserting 1 element using insert() is : 1 1 2 3

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

Мы также можем вставить более одного элемента, указав второй параметр в функции insert. Всякий раз, когда он не указан, по умолчанию он равен 1.

  • push_back: добавляет новый элемент в конец списка.
  • push_front: добавляет новый элемент в начало списка.

Давайте посмотрим на пример, демонстрирующий использование функций push_back и push_front:

Вывод данных:

List elements are: 1            1           2               3
List contents after push_front and push_back: 0              1                 1               2              3                  5

В этом примере мы сначала создаем и перечисляем все два элемента, по одному спереди и сзади, используя функции push_front и push_back соответственно. Вывод показывает измененный список после выполнения обеих функций.

  • pop_back: удаляет последний элемент в списке, тем самым уменьшая размер списка на 1.
  • pop_front: удаляет первый элемент в списке, тем самым уменьшая размер списка на 1.

В следующем примере показано использование операций pop_back и pop_front для списка:

Вывод данных:

List elements are: 1 1 2 3 5
List contents after push_front and push_back: 1 2 3

Как описано в определении операции, каждая из операций pop_front и pop_back удаляет элемент из начала и конца списка, то есть первый и последний элемент списка соответственно, и, таким образом, каждый раз уменьшает размер списка на 1.

  • size: Возвращает размер списка, т.е. количество элементов в списке.
  • empty: Проверяет, пуст ли список.
  • erase: удаляет элемент или диапазон элементов из списка.
  • clear: Удаляет все элементы из списка, уменьшая его размер до нуля.

Ниже приведен пример, демонстрирующий использование всех вышеперечисленных функций, т. е. size, empty, erase и clear:

Читать также:  Указатели и операции с указателями в C++

Вывод данных:

List elements are: 1 1 2 3 5
size of the list: 5
List after erasing first element: 1 2 3 5
New size of the list: 4
size of the list after clear: 0

Вышеприведенная программа демонстрирует все четыре функции, связанные с емкостью списка. Мы видим, что размер списка уменьшается на 1, когда мы стираем 1 элемент списка. Когда мы вызываем операцию очистки списка, размер равен 0, что означает, что все элементы в списке удаляются.

  • front: возвращает значение первого элемента списка.
  • back: возвращает значение последнего элемента списка.
  • swap: меняет местами содержимое одного списка с содержимым другого списка того же размера и типа.
  • reverse: Алгоритм, который переворачивает список.
  • sort: сортирует данный список.

В приведенном ниже примере демонстрируется использование функций front, back, reverse, sort и swap:

Вывод данных:

List elements are: 1          1            2             3              5
Front of the list: 1
Back of the list: 5
Reversed List: 5                3              2              1              1
Contents of odd list: 1           3            5               7           9
After swapping
mylist: 1            3              5             7                9
Oddlist : 5         3             2             1                  1

В этом коде сначала мы печатаем переднее и заднее значения списка mylist. Затем этот список переворачивается и печатается перевернутый список. После этого мы определяем еще один список нечетных чисел, который не находится в любом порядке, и мы вызываем алгоритм «sort» для сортировки этого списка. Затем мы меняем два списка местами, используя функцию «swap», и печатаем обмененные списки.

  • splice: эта функция используется для переноса содержимого одного списка в другой список в указанной позиции.

Читать также:  Полиморфизм времени выполнения в C++

Помните, оба списка должны быть одного типа.

splice(position, list);

position => Позиция, в которую должно быть передано содержимое списка.
list => Список, элементы которого должны быть переданы.

Пример, приведенный ниже, показывает использование функции splice:

Вывод данных:

List elements are: 1           1               8                   13
list to be spliced:  2           3               5
List contents after splicing at position 2: 1       1          2           3            5            8            13

Пример показывает, что мы используем два списка. Сначала итератор для mylist перемещается на две позиции, а затем вызывается функция splice для переноса содержимого второго списка на третью позицию первого списка.

  • merge: данная операция напрямую объединяет два списка в один список. Для операции слияния оба списка должны быть отсортированы.

Ниже приведен пример, демонстрирующий функцию merge:

Вывод данных:

First List: 11               2                  3                   5                    8
Second List: 4           6                  7
List contents after merging two lists:
1       1        2         3          4             5             6           7           8

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

Итог

Вот мы и подошли к концу данной статьи по спискам в STL. Мы надеемся, что эта статья дала вам огромные знания о списках в STL.

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

С Уважением, МониторБанк

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