DNK_C_C++_Go_Rust

#390_Cpp_PkS_STL

Как реализован std::list в С++?

Класс std::list в C++ — двусвязный список, который является частью STL.
В отличие от std::vector, список не хранит свои элементы в непрерывной области памяти, а использует узлы, связанные друг с другом через указатели.

Основные характеристики std::list:
Двусвязная структура — каждый узел содержит ссылки на предыдущий и следующий узлы, что позволяет легко перемещаться вперед и назад по списку.
Постоянное время вставки и удаления — рперации вставки и удаления элементов имеют сложность O(1), независимо от положения элемента в списке.
Отсутствие случайного доступа — поскольку элементы списка не располагаются в непрерывной памяти, доступ к произвольному элементу возможен только последовательным перебором узлов, что делает такую операцию медленной (O(n)).
Нет перераспределения памяти — в отличие от вектора, список не нуждается в перераспределении памяти при изменении своего размера, так как каждый узел выделяется отдельно.

Реализация основных методов.

Конструкторы:

/* По умолчанию создаёт пустой список */
std::list<T>::list();

/* Создает список с n элементами, инициализируя их значением value */
std::list<T>::list(size_type n, const T& value);

/* Создает список из диапазона [first, last) */
template<typename InputIterator>
std::list<T>::list(InputIterator first, InputIterator last);

// Копирующий конструктор
std::list<T>::list(const std::list<T>& other);

// Перемещающий конструктор
std::list<T>::list(std::list<T>&& other);

Деструктор:

std::list<T>::~list();

Деструктор освобождает всю выделенную память и уничтожает все элементы списка.

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

/* Добавляет элемент в начало списка */
void std::list<T>::push_front(const T& value);

/* Добавляет элемент в конец списка */
void std::list<T>::push_back(const T& value);

// Удаляет первый элемент
void std::list<T>::pop_front();

// Удаляет последний элемент
void std::list<T>::pop_back();

/* Вставляет элемент перед позицией pos */
iterator std::list<T>::insert(const_iterator pos, const T& value);

/* Удаляет элемент по позиции pos */
iterator std::list<T>::erase(const_iterator pos);

Методы сортировки и слияния:

// Сортирует элементы списка
void std::list<T>::sort();

/* Объединяет два отсортированных списка */
void std::list<T>::merge(std::list<T>& other);

/* Разделяет список на две части по предикату */
void std::list<T>::splice(const_iterator pos, std::list<T>& other);

Внутреннее устройство:

Каждый узел списка состоит из трех частей:
— данные элемента;
— указатель на следующий узел;
— указатель на предыдущий узел.

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

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

#include <iostream>
#include <list>

int main() {
  // Создание пустого списка
  std::list<int> lst;

  // Добавляем элементы
  lst.push_back(1);
  lst.push_back(2);
  lst.push_back(3);

  // Выводим элементы
  for (auto& x : lst) {
    std::cout << x << ' ';
  }
  std::cout << std::endl;

  // Удаляем первый элемент
  lst.pop_front();

  // Проверяем размер списка
  std::cout << "Size: " << lst.size() << std::endl;

  return 0;
}

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

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

3 viewsПавел "barracol", edited 15:36