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

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

Как создать список
Функции списка
Удаление элементов
Итераторы на список

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

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

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

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

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

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

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

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

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

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

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

#include <list>

1	#include <list>

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

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

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

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

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

list <string> listok;

1	list <string> listok;

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

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

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

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

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

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

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

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

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

insert

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

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

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

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

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

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

copy

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

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

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

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

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

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

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

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

unique

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

myspisok.unique();

1	myspisok.unique();

merge

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

myspisok.merge(dob_spisok);

1	myspisok.merge(dob_spisok);

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

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

using namespace std;

int main() {
  list <int> mylist;
  list <int> listmerge = {7, 8, 9};

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

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

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

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

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

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

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

int main() {

list <int> mylist;

list <int> listmerge = {7, 8, 9};

for (int i = 0; i < 2; i++) {

for (int j = 1; j < 6; j++) {

mylist.push_back(i); // добавили 10 элементов

}

copy (mylist.begin(), mylist.end(), ostream_iterator(cout, " "));

cout << endl;

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

copy (mylist.begin(), mylist.end(), ostream_iterator(cout, " "));

cout << endl;

mylist.unique(); // удалили все дубликаты

list <int> :: iterator it;

for (it = mylist.begin(); it != mylist.end(); it++) {

cout << (*it) << " ";

}

mylist.merge(listmerge); // присвоили список

for (it = mylist.begin(); it != mylist.end(); it++) {

cout << (*it) << " ";

}

return 0;

}

В строках 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(<начальная позиция (от)>, <конечная позиция (до)>);
<позиция> = <список>.erase(<позиция>);  // удаляем одну ячейку

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

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

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

Вот пример:

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

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

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

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

  pos_begin = pos_end = ilist.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 = ilist.erase(pos_begin);   //    ^
  pos_end = ilist.erase(pos_end);       //            ^
  
  cout << endl <<"Список после удаления двух ячеек: ";
  copy (ilist.begin(), ilist.end(), ostream_iterator(cout, " "));
  pos_begin++;                          // 01 3 4 5 7 8 9 10
  pos_end++;                            //      ^     ^
                                        //      ^       ^
  ilist.erase(pos_begin, pos_end);      // 01 3 09 10
                                        //      ^^
  cout << endl<< "А вот что стало: ";
  for (pos_begin = ilist.begin(); pos_begin != ilist.end(); ++pos_begin)
    cout << *pos_begin << " ";
  return 0;
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

int main() {

setlocale(LC_ALL, "RUS");

list ilist;

list :: iterator pos_begin, pos_end;

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

for (int i = 1; i <= 10; i++) {

ilist.push_back(i);

cout << i << " ";

}

pos_begin = pos_end = ilist.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 = ilist.erase(pos_begin); // ^

pos_end = ilist.erase(pos_end); // ^

cout << endl <<"Список после удаления двух ячеек: ";

copy (ilist.begin(), ilist.end(), ostream_iterator(cout, " "));

pos_begin++; // 01 3 4 5 7 8 9 10

pos_end++; // ^ ^

// ^ ^

ilist.erase(pos_begin, pos_end); // 01 3 09 10

// ^^

cout << endl<< "А вот что стало: ";

for (pos_begin = ilist.begin(); pos_begin != ilist.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).

Про функцию 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

Чтобы удалить все элементы со значением 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  mylist(numbers, numbers + 7);

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

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

#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 mylist(numbers, numbers + 7);

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

// вывели элементы

mylist.remove(53); // удалили все числа

mylist.remove(113); // 53 и 113

copy(mylist.begin(), mylist.end(), ostream_iterator(cout, " "));

return 0;

}

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

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

bool number_single (const int& val) {

return val < 10;

}

int main() {

// ...

mylist.remove_if(number_single);

// ...

}

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

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

C++

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

1

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

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

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

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

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

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

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

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

it++;

}

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

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

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

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

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

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

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

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

cin >> n;

advance(it, n);

advance(t, 5); // увеличили

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

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

cin >> n;

advance(it, n);

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

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

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

Плюсы:

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

Минусы:

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

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

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

9 сентября 2017

C++, Контейнеры

Комментарии

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

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

Николай:

27.02.2018 в 08:52

Неправильная запись: unique.myspisok();
Должно быть наоборот: myspisok.unique();
Это в блоке про unique

Ответить
Николай:

27.02.2018 в 08:59

Похоже, что в 13 строке кода после merge должно быть j вместо i: mylist.push_back(j);

Ответить
- Дмитрий:
  
  04.03.2018 в 10:59
  
  Поправил!
  
  Ответить
Orazzi:

02.06.2018 в 16:58

В этом месте

ostream_iterator(cout, » «));

у меня не заработало потом я сделал

ostream_iterator(cout, » «));

потом уже сработало

Ответить
Orazzi:

02.06.2018 в 16:59

после osteam_iterator поставил int

Ответить
Никита:

20.10.2018 в 11:52

Допущена ошибка в описание advanse()

верное имя метода advanсe().

Ответить
- Дмитрий:
  
  27.10.2018 в 15:46
  
  Спасибо, исправили.
  
  Ответить
MelvinRow:

14.12.2020 в 19:21

спасибо интересное чтиво

Ответить