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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое список list

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

На картинке ниже показана, как это устроено:

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

i_am_list[2] = 8;  // ошибка!

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

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

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

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

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

#include <list>

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

list < тип данных > <имя контейнера>;

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

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

list <string> listok;

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

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

list <int> this_list = {4, 6, 3, 2};

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

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

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

insert

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

insert (<позиция>, <значение>);

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

string cpp = "Это легко";
insert (it, cpp);

copy

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

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

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

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

copy(my_list.begin(), my_list.end(), ostream_iterator<int>(cout," "));

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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

unique

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

my_list.unique();

merge

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

my_list.merge(dob_spisok);

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

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main() {
  list <int> my_list;
  list <int> list_merge = {7, 8, 9};

  for (int i = 0; i < 2; i++) {
    for (int j = 1; j < 6; j++) {
      my_list.push_back(i); // добавили 10 элементов
    }
  }

  copy (my_list.begin(), my_list.end(), ostream_iterator(cout, " ")); 
  cout << endl;                                                

  my_list.insert(my_list.end(), 6);  // добавили новый элемент

  copy (my_list.begin(), my_list.end(), ostream_iterator(cout, " "));  
  cout << endl;
  
  my_list.unique();  // удалили все дубликаты
  list <int> :: iterator it; 

  for (it = my_list.begin(); it != my_list.end(); it++) { 
    cout << (*it) << " ";
  }

  my_list.merge(list_merge);  // присвоили список 
  for (it = my_list.begin(); it != my_list.end(); it++) {
    cout << (*it) << " ";  
  }
  return 0;
}

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

Результат:

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.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

erase

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

<список>.erase(<начальная позиция (от)>, <конечная позиция (до)>);
<позиция> = <список>.erase(<позиция>);  // удаляем одну ячейку

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

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

Вот пример:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
  setlocale(LC_ALL, "RUS");
  list my_list;
  list::iterator pos_begin, pos_end;

  cout << "Вот как заполнили список: ";

  for (int i = 1; i <= 10; i++) {
    my_list.push_back(i);
    cout << i << " ";
  }

  pos_begin = pos_end = my_list.begin();  // 01 2 3 4 5 6 7 8 9 10
                                          // ^^
                                          // 01 2 3 4 5 6 7 8 9 10
  advance(pos_end, 6);                    // ^            ^
  pos_begin++;                            //    ^         ^
                                          // 01 3 4 5 7 8 9 10
  pos_begin = my_list.erase(pos_begin);   //    ^
  pos_end = my_list.erase(pos_end);       //            ^
  
  cout << endl <<"Список после удаления двух ячеек: ";
  copy (my_list.begin(), my_list.end(), ostream_iterator(cout, " "));
  pos_begin++;                          // 01 3 4 5 7 8 9 10
  pos_end++;                            //      ^     ^
                                        //      ^       ^
  my_list.erase(pos_begin, pos_end);    // 01 3 09 10
                                        //      ^^
  cout << endl<< "А вот что стало: ";
  for (pos_begin = my_list.begin(); pos_begin != my_list.end(); ++pos_begin) {
    cout << *pos_begin << " ";
  }

  return 0;
}

• В строке 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).

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

Вот как заполнили список: 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

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

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
  setlocale(LC_ALL, "RUS");
  int numbers[] = {12, 34, 45, 23, 53, 68, 113, 53};

  list  my_list(numbers, numbers + 7);

  copy(my_list.begin(), my_list.end(), ostream_iterator(cout, " "));
  cout << endl;
                                             // вывели элементы
  my_list.remove(53);  // удалили все числа 
  my_list.remove(113); // 53 и 113

  copy(my_list.begin(), my_list.end(), ostream_iterator(cout, " "));
  return 0;
}

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).

bool number_single (const int& val) { 
  return val < 10;
}
int main() {
  // ...
  my_list.remove_if(number_single);
  // ...
}

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

• В функции number_single нужно указать вместо типа int тип вашего списка.

• Далее в теле функции return val < 10; заменить вашим условием. В нашем случае удаляться все элементы меньшие 10.

• Осталось лишь вызвать данную конструкцию:

  <имя вашего списка>.remove_if(<название функции>);

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

it -= 13; // ошибка!

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

for (int i = 0; i < 13; i++) {
  it++; 
}

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

advance(<итератор>, <значение>);

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

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

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

advance(t, 5);  // увеличили
advance(t, -5); // вернули в исходную позиции

list <int> :: iterator it = l.begin();

cin >> n;

advance(it, n);

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

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

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

Плюсы:

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

Минусы:

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

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

Итераторы в C++ »