Структура данных STL List в C++: реализация и применение

std::list - это класс шаблонной библиотеки STL (Standard Template Library) языка программирования C++, который реализует связанный список, то есть список элементов, каждый из которых содержит указатель на следующий элемент.

Пример создания std::list:

cpp
#include 
#include 
int main()
{
  std::list lst {1, 2, 3, 4, 5};
  
  // выводим элементы списка
  for (auto const& i : lst)
    std::cout << i << " "; // выводит "1 2 3 4 5"
  
  return 0;
}

Для добавления элементов в список можно использовать методы push_front, push_back:

cpp
std::list lst {1, 2, 3};
lst.push_front(0); // список станет {0, 1, 2, 3}
lst.push_back(4); // список станет {0, 1, 2, 3, 4}

Для удаления последнего и первого элементов используют методы pop_back и pop_front соответственно:

cpp
std::list lst {1, 2, 3};
lst.pop_back(); // список станет {1, 2}
lst.pop_front(); // список станет {2}

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

cpp
std::list lst {1, 2, 3};
if (!lst.empty())
{
  // список не пуст
}

Для доступа к первому и последнему элементу списка можно использовать методы front и back:

cpp
std::list lst {1, 2, 3};
int first = lst.front(); // first равно 1
int last = lst.back(); // last равно 3

Также в std::list реализованы операторы сравнения == и !=, метод size для получения размера списка, методы insert и erase для добавления и удаления элементов на определенной позиции, а также методы sort и reverse для сортировки и обращения списка соответственно.

Использование std::list позволяет эффективно выполнять операции добавления и удаления элементов, однако для доступа к произвольному элементу списка (не только к первому и последнему) может потребоваться проход по всем предшествующим элементам списка.