4. Контейнер list

Основные сведения

Шаблонный класс list входит в библиотеку STL. В библиотеке STL описывается шаблонный класс list, который позволяет описывать списки переменных любого типа. Формальное определение шаблона дано ниже:

template <class Type, class Allocator = std::allocator<Type>>
class list {
  // ...
};

Для работы объектами этого класса необходимо подключить заголовочный файл:

#include <list>

Описание списка

Для описания списков предусмотрены разные конструкторы. Примеры описания списков даны ниже:

// Списки list описания и инициализация
std::list<int> l0;  // Пустой список l0
std::list<int> l1(3);  // Список с тремя элементами равными 0
std::list<int> l2(5, 2);  // Список из пяти элементов равными 2
std::list<int> l3(l2);  // Список l3 на основе списка l2
std::list<int>::iterator l3_Iter;  // Описание итератора l3_Iter
l3_Iter = l3.begin();  // Итераторные вычисления на начало
l3_Iter++;
l3_Iter++;  // Итераторные вычисления продвинуть на два объекта
std::list<int> l4(l3.begin(),
                  l3_Iter);  // Список l4 на основе первых двух элементов L3

Итерирование по списку

Функцию печати опишем следующим образом:

void lPrint(std::list<int>& l) {
  std::list<int>::iterator iter;
  int i = 0;
  if (!l.empty()) {
    for (iter = l.begin(); iter != l.end(); iter++, i++) {
      std::cout << "l[" << i << "] = " << *iter << std::endl;
    }
  } else
    std::cout << "Список пуст!" << std::endl;
}

Для описания пустого списка l (типа list) также нужно указать тип int (инстанцировать шаблонный объект):

#include <iostream>
#include <list>

void lPrint(std::list<int>& l) {
  std::list<int>::iterator iter;
  int i = 0;
  if (!l.empty()) {
    for (iter = l.begin(); iter != l.end(); iter++, i++) {
      std::cout << "l[" << i << "] = " << *iter << std::endl;
    }
  } else
    std::cout << "Список пуст!" << std::endl;
}

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::list<int> l;  // Пустой список l
  std::cout << "Добавление:" << std::endl;
  l.push_back(1);   // Добавление в конец списка
  l.push_back(2);   // Добавление в конец списка
  l.push_front(5);  // Добавление в начало списка
  lPrint(l);  // Собственная функция печати целого списка
}

В функции печати используется итератор iter, который позволяет продвигаться по списку (iter++). Для установки итератора на первый элемент используется метод begin. Остановка просмотра проверяется методом end. Для проверки пустого списка используется метод empty. Для дальнейшей демонстрации возможностей списков будем использовать эту функцию. В первом фрагменте получим результат:

Добавление:
l[0] = 5
l[1] = 1
l[2] = 2

Слияние списков

Рассмотрим еще несколько примеров использования объектов класса список и его методов. Для копирования списков может быть использован метод слияния (assign), а для очистки списка может быть использован метод удаления (erase или clear):

// Копирование и очистка
std::list<int> l20;  // Пустой список l
l20.erase(l20.begin(), l20.end());
lPrint(l20);
l20.assign(l.begin(), l.end());
std::cout << "После копирования l в l20:" << std::endl;
lPrint(l20);
l20.clear();
std::cout << "После очистки l20:" << std::endl;
lPrint(l20);

В этом фрагменте получим результат:

Список пуст!
После копирования l в l20:
l[0] = 5
l[1] = 1
l[2] = 2
После очистки l20:
Список пуст!

Определения размера списка

Получить текущую размерность списка можно методом size:

std::cout << "Число элементов в списке =  " << l.size() << std::endl;

Получим результат:

Число элементов в списке =  3

Манипулировать с содержимым списка (вставка, удаление и т.д.)

Манипулировать с содержимым списка (вставка, удаление и т.д.) можно с помощью методов (insert, remove, erase, remove_if и др.). Ниже приводиться работающий фрагмент программы, иллюстрирующий эти действия (комментарии даны в тексте программы):

#include <iostream>
#include <list>

void lPrint(std::list<int>& l) {
  std::list<int>::iterator iter;
  int i = 0;
  if (!l.empty()) {
    for (iter = l.begin(); iter != l.end(); iter++, i++) {
      std::cout << "l[" << i << "] = " << *iter << std::endl;
    }
  } else
    std::cout << "Список пуст!" << std::endl;
}

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif

  std::list<int> l;  // Пустой список l
  std::cout << "Добавление:" << std::endl;
  l.push_back(1);   // Добавление в конец списка
  l.push_back(2);   // Добавление в конец списка
  l.push_front(5);  // Добавление в начало списка
  lPrint(l);  // Собственная функция печати целого списка

  // Вставка
  std::list<int>::iterator iter = l.begin();
  iter++;
  iter++;  // Вставка после второго
  std::cout << "Вставка:" << std::endl;
  l.insert(iter, 100);
  lPrint(l);
  // Удаление по числу
  l.remove(100);
  std::cout << "Удаление по числу 100:" << std::endl;
  lPrint(l);
  // Удаление по номеру
  l.erase(l.begin());  // Из головы списка
  std::cout << "Удаление по номеру 0:" << std::endl;
  lPrint(l);
  // Добавим и удалим по итератору
  l.push_back(20);
  l.push_back(31);
  std::cout << "Перед удалением:" << std::endl;
  lPrint(l);
  iter = l.begin();
  iter++;
  iter++;  // Сдвиг на два элемента
  l.erase(iter);
  std::cout << "Удаление по итератору 2 (3-й элемент):" << std::endl;
  // Удаление по условию (предикату)
  lPrint(l);
  std::list<int> l22 = l;
  std::cout << "Удаление четных чисел:" << std::endl;
  std::cout << "-> До удаления:" << std::endl;
  lPrint(l22);
  auto is_odd = [](int const elem) { return (elem % 2); };
  l22.remove_if(is_odd);
  std::cout << "-> После удаления:" << std::endl;
  lPrint(l22);
}

Результат выполнения:

Добавление:
l[0] = 5
l[1] = 1
l[2] = 2
Вставка:
l[0] = 5
l[1] = 1
l[2] = 100
l[3] = 2
Удаление по числу 100:
l[0] = 5
l[1] = 1
l[2] = 2
Удаление по номеру 0:
l[0] = 1
l[1] = 2
Перед удалением:
l[0] = 1
l[1] = 2
l[2] = 20
l[3] = 31
Удаление по итератору 2 (3-й элемент):
l[0] = 1
l[1] = 2
l[2] = 31
Удаление четных чисел:
-> До удаления:
l[0] = 1
l[1] = 2
l[2] = 31
-> После удаления:
l[0] = 2

Обратим внимание на строчки:

auto is_odd = [](int const elem) { return (elem % 2); };
l22.remove_if(is_odd);

Для определения элементов, которые подлежат удалению, используется именованное лямда-выражение. Можно также использовать экземпляр шаблонного класса, как показано ниже:

template <class T>
class is_odd : public std::unary_function<T, bool> {
 public:
  bool operator()(T& val) { return (val % 2) != 1; }
};  // Условие предиката – четное = 0

// ...
l22.remove_if(is_odd<int>());

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

Сортировка списка

Сортировка списка выполняется методом sort, при этом может быть указан параметр или не указан. Если параметр не задан, то сортировка выполняется в порядке возрастания ключевой переменной (less). При задании параметра сортировки greater сортировка выполняется в порядке убывания основной переменной списка. Примеры и результат приведены ниже.

#include <algorithm>
#include <iostream>
#include <list>

void lPrint(std::list<int>& l) {
  std::list<int>::iterator iter;
  int i = 0;
  if (!l.empty()) {
    for (iter = l.begin(); iter != l.end(); iter++, i++) {
      std::cout << "l[" << i << "] = " << *iter << std::endl;
    }
  } else
    std::cout << "Список пуст!" << std::endl;
}

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif

  std::list<int> l;  // Пустой список l
  std::cout << "Добавление:" << std::endl;
  l.push_back(1);   // Добавление в конец списка
  l.push_back(2);   // Добавление в конец списка
  l.push_front(5);  // Добавление в начало списка
  lPrint(l);  // Собственная функция печати целого списка

  // Сортировка
  std::cout << "До сортировки списка!" << std::endl;
  lPrint(l);
  l.sort(std::greater<int>());  // Сортировка по убыванию
  std::cout << "После greater сортировки списка!" << std::endl;
  lPrint(l);
  l.sort(std::less<int>());  // Явная сортировка по возрастанию
  std::cout << "После less сортировки списка!" << std::endl;
  lPrint(l);
  // Список l22
  std::list<int> l22 = l;
  std::cout << "До сортировки списка (l22)!" << std::endl;
  l22.push_front(555);  // Добавление в начало списка
  lPrint(l22);
  l22.sort();  // Сортировка по возрастанию по умолчанию ( возрастание) less
  std::cout << "После сортировки списка (по умолчанию)!" << std::endl;
  lPrint(l22);
}

Получим результат:

Добавление:
l[0] = 5
l[1] = 1
l[2] = 2
До сортировки списка!
l[0] = 5
l[1] = 1
l[2] = 2
После greater сортировки списка!
l[0] = 5
l[1] = 2
l[2] = 1
После less сортировки списка!
l[0] = 1
l[1] = 2
l[2] = 5
До сортировки списка (l22)!
l[0] = 555
l[1] = 1
l[2] = 2
l[3] = 5
После сортировки списка (по умолчанию)!
l[0] = 1
l[1] = 2
l[2] = 5
l[3] = 555

Переупорядочение списка, изменение порядка на обратный, выполняется методом reverse. Пример:

// ...
std::cout << "До сортировки списка!" << std::endl;
lPrint(l);
std::cout << "После reverse сортировки списка!" << std::endl;
l.reverse();
lPrint(l);

Получим результат:

До сортировки списка!
l[0] = 5
l[1] = 1
l[2] = 2
После reverse сортировки списка!
l[0] = 2
l[1] = 1
l[2] = 5

Очистка списка

Очистка списка (clear):

// ...
l.clear();
std::cout << "После очистки списка!" << std::endl;
lPrint(l);

Получим результат:

После очистки списка!
Пустой список!

Использование класса list для включения пользовательских объектов

При выполнении индивидуальных заданий необходимо продемонстрировать использование методов класса список - list для простых объектов класса, который определяется вариантом задания. Отличие заключается в том, что здесь используются нестандартные переменные (нестандартный тип int)

Определение класса

Использование своего класса в качестве содержимого списка имеет ряд особенностей. На примере простого класса Point рассмотрим их. Заголовочный файл данного класса:

// point.h
#ifndef POINT_H
#define POINT_H
#include <iostream>
#include <list>

class Point {
 public:
  int x;
  int y;
  Point();
  Point(int a, int b);
  Point(const Point& p);
  Point& operator=(const Point& p);
  friend std::ostream& operator<<(std::ostream& out, Point& obj);
  friend bool operator==(const Point& p1, const Point& p2);
  friend bool operator>(const Point& p1, const Point& p2);
  friend bool operator<(const Point& p1, const Point& p2);
};

template <class T>
void lPPrint(std::list<T>& l) {
  typedef typename std::list<T>::iterator iterator;

  iterator iter;
  int i = 0;
  if (!l.empty()) {
    for (iter = l.begin(); iter != l.end(); iter++, i++) {
      std::cout << "list[" << i << "] = " << *iter << std::endl;
    }
  } else
    std::cout << "Список пуст!" << std::endl;
}
#endif  // POINT_H

Реализация данного класса:

// point.cpp
#include "point.h"

Point::Point() {
  x = 0;
  y = 0;
};

Point::Point(int a, int b) {
  x = a;
  y = b;
};

Point::Point(const Point& p) {
  x = p.x;
  y = p.y;
};

Point& Point::operator=(const Point& p) {
  x = p.x;
  y = p.y;
  return *this;
};

// Перегурузка операции для сортировки
bool operator<(const Point& p1, const Point& p2) { return (p1.x < p2.x); };

// Перегурузка операции для сортировки
bool operator>(const Point& p1, const Point& p2) { return (p1.x > p2.x); };

// Перегурузка операции сравнения для удаления по объекту
bool operator==(const Point& p1, const Point& p2) {
  return ((p1.x == p2.x) && (p1.y == p2.y));
};

// Перегурузка операции для увывода объекта
std::ostream& operator<<(std::ostream& out, Point& obj) {
  out << "{ x = " << obj.x << " y = " << obj.y << " } ";
  return out;
};

Инстанцирование списка и его итераторы

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

#include "point.h"

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::list<Point> lP;
  std::list<Point>::iterator PIter;
  Point P1(11, 22);
  Point P2(51, 52);
  std::cout << "КЛАСС POINT!!!" << std::endl;
  lP.push_back(P1);
  lP.push_back(P2);
  lP.push_front(*new Point(31, 32));
  lPPrint<Point>(lP);
}

Тогда получим следующий результат:

КЛАСС POINT!!!
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 }

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

// ...
std::list<Point> lp;  // Пустой список lp0
std::list<Point> lp1(3);  // Список с тремя элементами равными 0
std::list<Point> lp2(5, P2);  // Список из пяти элементов равными P2
std::list<Point> lp3(lp2);  // Список l3 на основе списка l2
std::list<Point>::iterator lp3_Iter;
lp3_Iter = lp3.begin();
lp3_Iter++;
lp3_Iter++;
std::list<Point> lp4(
    lp3.begin(),
    lp3_Iter);  // Новый список lp4 на основе первых двух элементов lp3
std::cout << "КОНСТРУКТОРЫ:  КЛАСС POINT!!!" << std::endl;
std::cout << "lp:" << std::endl;
lPPrint(lp);
std::cout << "lp1:" << std::endl;
lPPrint(lp1);
std::cout << "lp2:" << std::endl;
lPPrint(lp2);
std::cout << "lp3:" << std::endl;
lPPrint(lp3);
std::cout << "lp4:" << std::endl;
lPPrint(lp4);

Получим после выполнения этого фрагмента программы:

КОНСТРУКТОРЫ:  КЛАСС POINT!!!
lp:
Список пуст!
lp1:
list[0] = { x = 0 y = 0 } 
list[1] = { x = 0 y = 0 } 
list[2] = { x = 0 y = 0 } 
lp2:
list[0] = { x = 51 y = 52 } 
list[1] = { x = 51 y = 52 } 
list[2] = { x = 51 y = 52 } 
list[3] = { x = 51 y = 52 } 
list[4] = { x = 51 y = 52 } 
lp3:
list[0] = { x = 51 y = 52 } 
list[1] = { x = 51 y = 52 } 
list[2] = { x = 51 y = 52 } 
list[3] = { x = 51 y = 52 } 
list[4] = { x = 51 y = 52 } 
lp4:
list[0] = { x = 51 y = 52 } 
list[1] = { x = 51 y = 52 } 

Манипулирование содержимым списка

Все другие методы класса list из STL также можно использовать для построения списков на основе класса Point. Рассмотрим и другие примеры. Метод позволяет assign добавить в новый список элементы из другого списка, а метод clear, очистить список:

// ...
// Копирование и очистка
// list <Point> lp20; // - Можно и так описать список lp20
typedef std::list<Point>
    ListPoint;  // Зададим новый тип - ListPoint список точек
ListPoint lp20;
std::cout << "Исходный список lP:" << std::endl;
lPPrint(lP);  // см. выше пример
lPPrint(lp20);
lp20.assign(lP.begin(),
            --lP.end());  // копируем без последнего элемента списка
std::cout << "После копирования lP в lp20:" << std::endl;
lPPrint(lp20);
lp20.clear();
std::cout << "После очистки lp20:" << std::endl;
lPPrint(lp20);

Получим результат, при копировании всего списка без последнего элемента (--lP.end()):

Исходный список lP:
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 } 
Список пуст!
После копирования lP в lp20:
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
После очистки lp20:
Список пуст!

Манипулировать с содержимым списка (вставка, удаление и т.д.) можно с помощью методов, рассмотренных выше для стандартных типов: insert, erase, remove_if и др. Примеры:

// ...
// Копирование и очистка
// list <Point> lp20; // - Можно и так описать список lp20
// Вставка по итератору
PIter = lP.begin();
PIter++;
PIter++;  // итератор переместим на 2 элемента
std::cout << "Вставка: до вставки 2-го:" << std::endl;
lPPrint(lP);
std::cout << "Вставка: после вставки 2-го:" << std::endl;
lP.insert(PIter, P1);  // 11-22
lPPrint(lP);
// Удаление по итератору
lP.erase(lP.begin());
lP.push_back(*new Point(20, 62));
std::cout << "Удаление по итератору (0 - первого):" << std::endl;
lPPrint(lP);
// Удаление по простой предикат для удаления х = 20
lP.remove_if(std::function<bool(Point)>(
    [](Point val) { return val.x == 20; }));  // Работает!!!
std::cout << "После удаления x = 20 списка!" << std::endl;
lPPrint(lP);

В результате выполнения данного фрагмента программы получим:

Вставка: до вставки 2-го:
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 } 
Вставка: после вставки 2-го:
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 11 y = 22 } 
list[3] = { x = 51 y = 52 } 
Удаление по итератору (0 - первого):
list[0] = { x = 11 y = 22 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 } 
list[3] = { x = 20 y = 62 } 
После удаления x = 20 списка!
list[0] = { x = 11 y = 22 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 } 

Функция remove (удалить по объекту) требует описания перегруженной операции равенства, присваивания и явных конструкторов копирования (см. реализацию выше). Тогда можно выполнить следующий фрагмент текста с функцией remove:

// ...
// Вставка по итератору
PIter = lP.begin();
PIter++;
PIter++;  // итератор переместим на 2 элемента
std::cout << "Вставка: до вставки 2-го:" << std::endl;
lPPrint(lP);
std::cout << "Вставка: после вставки 2-го (P1):" << std::endl;
lP.insert(PIter, P1);  // <11,22>
lPPrint(lP);
std::cout << "Размер списка:" << lP.size() << std::endl;  // Размер списка
lP.insert(PIter, P2);
lP.insert(PIter, *new Point(51, 61));
std::cout << "Вставка: после вставки 2-го(P2 вставка 2-x):" << std::endl;
lPPrint(lP);
lP.remove(P2);
std::cout << "Удаление по объекту P2 = <51,52> (после):" << std::endl;
lPPrint(lP);

В результате выполнения данного фрагмента программы получим (удаляются точки с координатами <51,52>):

Вставка: до вставки 2-го:
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 51 y = 52 } 
Вставка: после вставки 2-го (P1):
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 11 y = 22 } 
list[3] = { x = 51 y = 52 } 
Размер списка:4
Вставка: после вставки 2-го(P2 вставка 2-x):
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 11 y = 22 } 
list[3] = { x = 51 y = 52 } 
list[4] = { x = 51 y = 61 } 
list[5] = { x = 51 y = 52 } 
Удаление по объекту P2 = <51,52> (после):
list[0] = { x = 31 y = 32 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 11 y = 22 } 
list[3] = { x = 51 y = 61 } 

Функции sort требуют описания перегруженных операций сравнения (>,<) для объекта типа Point. Для упрощения предиката зададим сортировку только по параметру класса x (см. реализацию выше).

Пример использования метода sort показан ниже. Используемый ниже метод reverse позволяет изменить порядок расположения объектов на обратный порядок. После этого можно выполнить следующий фрагмент программы:

// ...
// Сортировка
lP.push_front(*new Point(20, 32));
std::cout << "Обратный порядок (до):" << std::endl;
lPPrint(lP);
lP.reverse();  // Изменение порядка на обратный
std::cout << "Обратный порядок (после):" << std::endl;
lPPrint(lP);
std::cout << "Сортировка по возрастанию х:" << std::endl;
lP.sort();  // По умолчанию less - сортировкапо возрастанию
lPPrint(lP);
std::cout << "Сортировка по убыванию х:" << std::endl;
lP.sort(std::greater<Point>());
lPPrint(lP);

Получим в результате:

Обратный порядок (до):
list[0] = { x = 20 y = 32 } 
list[1] = { x = 31 y = 32 } 
list[2] = { x = 11 y = 22 } 
list[3] = { x = 51 y = 52 } 
Обратный порядок (после):
list[0] = { x = 51 y = 52 } 
list[1] = { x = 11 y = 22 } 
list[2] = { x = 31 y = 32 } 
list[3] = { x = 20 y = 32 } 
Сортировка по возрастанию х:
list[0] = { x = 11 y = 22 } 
list[1] = { x = 20 y = 32 } 
list[2] = { x = 31 y = 32 } 
list[3] = { x = 51 y = 52 } 
Сортировка по убыванию х:
list[0] = { x = 51 y = 52 } 
list[1] = { x = 31 y = 32 } 
list[2] = { x = 20 y = 32 } 
list[3] = { x = 11 y = 22 } 

С использованием других предикатов предлагается разобраться самостоятельно. Особенностью использования собственных объектов является необходимость перегрузки операций вывода. Другой особенностью класса list является автоматическое корректное удаление динамических объектов, созданных в программе и включенных в массив.