std::list двусвязный список С++

- list это двусвязный список, элементы хранятся в произвольных областях памяти. Подключается через #include <list>;

- Список позволяет эффективно вставлять и удалять элементы в любом месте списка.

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

- list хранит указатели на начальный и конечный узлы. К узлу нельзя эффективно обратиться по номеру (для этого пришлось бы идти в цикле по списку начиная от головы). Поэтому пройтись по списку можно только с помощью range-based for или итераторов.

МетодОписаниеПримерСложность
assign(size_t size, T value) Делает список размером size и значениями value ls.assign(5, 3); O(n)
assign(iterator it_start, iterator it_stop) Делает список из диапазона итераторов другого контейнера. ls.assign(v.begin() + 2, v.end()); O(n)
assign(initializer_list<value_type> il) Делает список из значений списковой инициализации ls.assign({5, 6, 7}); O(n) C++11
back() Доступ к последнему элементу. auto i = ls.back(); O(1)
begin() Возвращает итератор на первый элемент. auto i = ls.begin(); O(1)
clear() Удаляет все элементы списка. ls.clear(); O(n)
emplace(iterator it, T value) Вставляет значение value перед итераторотом it ls.emplace(ls.begin(), 100); O(1)
ls.emplace_back(T value) Вставляет значение value в конец списка ls.emplace_back(100); O(1)
ls.emplace_begin(T value) Вставляет значение value в начало списка ls.emplace_begin(100); O(1)
empty() Возвращает пустой ли список. if(!ls.empty()); O(1)
end() Возвращает итератор на место после последнего элемента списка. auto i = ls.end(); O(1)
erase(iterator pos) Удаляет элемент(ы) из заданной позиции. ls.erase(++ls.begin());
ls.erase(++ls.begin(), --ls.end());
O(n)
front() Доступ к первому элементу. cout << ls.front(); O(1)
insert(iterator pos, T value ) Вставляет элемент(ы) в заданную позицию. ls.insert(ls.begin(), 10);
ls.insert(ls.begin() + 2, {3, 4, 5});
ls.insert(ls.begin(), ls.begin(), ls.end());
O(n)
list Конструктор без аргументов. Создает новый пустой список. list<int> ls; O(1)
list(int size) Конструктор. Создает список с заданным количеством элементов list<int> ls(10); O(n)
list(int size, int value) Конструктор. Создает список с количеством элементов size и значением value vector<int> ls(10, 3); O(n)
list(const list v) Конструктор копирования. Создает список со значениями списка ls list<int> ls1(ls); O(n)
list(iterator it_start, iterator it_stop) Конструктор. Создает список из диапазона итераторов другого контейнера. list ls(v.begin(), v.end()); O(n)
max_size() Возвращает максимально возможный размер списка. size_t msize = ls.max_size(); //384307168202282325 O(1)
merge(list& ls1) Слияние текущего списка и ls1 ls.merge(ls1); O(1)
pop_back() Удаляет элемент с конца списка. ls.pop_back(); O(1)
pop_front() Удаляет элемент с начала списка. ls.pop_front(); O(1)
push_back(const T& value) Вставляет элемент со значением value в конец списка. ls.push_back(10); O(1)
push_front(const T& value) Вставляет элемент со значением value в начало списка. ls.push_front(10); O(1)
rbegin() Возвращает реверсивный итератор на конец списка. auto i = ls.rbegin(); O(1)
remove(const T& value) Удаляет все элементы из списка с заданным значением ls.remove(2); O(n)
rend() Возвращает реверсивный итератор на начало списка. auto i = ls.rend(); O(1)
resize(size_t new_size) Изменяет количество элементов списка до new_size ls.resize(1000); O(n)
reverse() Инвертирует порядок элементов списка ls.reverse(); O(n)
size() Возвращает размер списка. size_t size = ls.size(); O(n) С++98
O(1) С++11
sort() Сортирует элементы списка по возрастанию ls.sort(); O(n*log(n))
splice(iterator it, list& ls1) Перемещает на место итератора it список ls1 ls.splice(++ls.begin(), ls1); O(1)
splice(iterator it, list& ls1, iterator its) Перемещает на место итератора it, элемент its из списка ls1 (с удалением элемента из ls1) ls.splice(ls.begin(), ls1, --ls1.end()); O(1)
splice(iterator it, list& ls1, iterator it_start, iterator it_stop) Перемещает на место итератора it, диапазон [it_start, it_stop] из списка ls1 (с удалением элементов из ls1) fl.splice(fl.begin(), ls1, ls1.begin(), --ls1.end()); O(n)
swap(list& ls) Обменивает содержимое списков ls.swap(ls2); O(1)
unique() Удаляет элементы с повторяющимися значениями из списка, если они идут подряд, предварительно нужно сортировать sort() ls.unique(); O(n)
#include <iostream> // cout
#include <list>     // list
using namespace std;

int main() {
    list<int> list1;                // Создание пустого списка
    list<int> list2(5);             // Создание пустого списка из 5 чисел, каждый элемент имеет значение по умолчанию
    std::list<int> list3(5, 2);     // Создание пустого списка из 5 чисел, каждое число равно 2
    list<int> list4{1, 2, 3};       //{1, 2, 3} Создание списка целочисленных значений
    list<int> list5 = {1, 2, 3};    //{1, 2, 3} То же самое
    list<int> list6(list4);         //{1, 2, 3} list6 - копия списка list4
    list<int> list7 = list4;        //{1, 2, 3} list7 - копия списка list4

    list4.push_front(0);    //{0, 1, 2, 3} Добавление в начало списка элемента со значением 0
    list4.push_back(4);     //{0, 1, 2, 3, 4} Добавление в конец списка элемента со значением 4
    list4.pop_front();      //{0, 1, 2, 3} Удаление первого элемента (0)
    list4.pop_back();       //{1, 2, 3} Удаление последнего элемента (3)
    int i = list4.front();  //i = 1 Взятие значения первого элемента списка
    i = list4.back();       //i = 3 Взятие значения последнего элемента списка
    size_t size = list4.size(); //size = 3 Размер списка (количество элементов)

    list4.resize(5);        //{1, 2, 3, 0, 0} Изменение размера списка в большую сторону было {1, 2, 3}
    list4.resize(2);        //{1, 2} Изменение размера списка в меньшую сторону
    list4.resize(4, 10);    //{1, 2, 10, 10} Изменение размера списка в большую сторону с инициализацией значением
    list4.resize(3, 10);    //{1, 2, 10} Изменение размера списка в меньшую сторону с инициализацией значением (не используется)

    for (int x : list4) {   // Перебор в цикле
        cout << x << " ";  //1 2 10
    }
    cout << endl;

    for(auto it = list4.begin(); it != list4.end(); it++){ // Перебор с помощью итераторов
        cout << *it << " "; //1 2 10  Взятие значения элемента с помощью итератора как с помощью указателя
    }
}
#include <iostream> // cout
#include <list>     // list
using namespace std;

int main() {
    list<int> lst{0, 1, 2, 3};       //{0, 1, 2, 3} Создание списка целочисленных значений
    lst.assign({6, 7});       //{6, 7} Замена содержимого списка
    lst.assign(5, 10);       //{10, 10, 10, 10, 10} Замена содержимого списка assign(кол-во элементов, значение)
    lst.assign({5, 6, 7, 8});       //{5, 6, 7, 8} Замена содержимого списка
    lst.assign(++lst.begin(), lst.end()); //{6, 7, 8} Замена содержимого списка через итераторы (от начального, до конечного)

    list<int> list1{1, 3};  // Создали еще один список
    swap(lst, list1);   //lst={1, 3},  list1 = {6, 7, 8} Обмен списков значениями

    lst.emplace_back(5); //lst={1, 3, 5} Добавить элемент в конец списка
    auto it = lst.insert(lst.begin(), 0); //lst={0, 1, 3, 5} Добавить элемент в начало списка
    auto it1 = lst.insert(++it, 3, 9); //lst={0 9 9 9 1 3 5} Вставить после первого элемента три девятки. Возвращает итератор на первую вставленную
    auto it2 = lst.insert(it1, {8, 6, 4}); //lst={0 8 6 4 9 9 9 1 3 5} Вставить после первого элемента три элемента

    lst.erase(lst.begin()); //lst={8 6 4 9 9 9 1 3 5} Удалить элемент на который указывает итератор
    lst.erase(++it2, --lst.end()); //lst={8 5} Удалить элемент от итератора до итератора
    lst.clear();   // Удалить все элементы списка
}
#include <iostream> // cout
#include <list>     // list
using namespace std;

int main() {
    list<int> list1{0, 1, 2, 3, 4}; // Список 1
    list<int> list2;                // Список 2

    auto it = list1.begin();        // Итератор на начало первого списка
    advance(it, 2);                 // Смещаем итератор на третий элемент первого списка
    list2.splice(list2.begin(), list1, it, --list1.end()); //list1 = {0, 1, 4} list2 = {2, 3} Переносим с третьего по предпоследний элемент из списка 1 в 2

    list1.insert(--list1.end(), {2, 3}); //list1 = {0, 1, 2, 3, 4} вставили элементы 2 и 3 перед концом

    it = list1.end();        // Итератор на конец списка
    advance(it, -2);         // Смещаем итератор на предпоследний элемент списка
    list1.splice(list1.begin(), list1, it, list1.end()); //list1 = {3, 4, 0, 1, 2} Перемещаем элементы внутри списка
}

2023-12-15



Понравилась страница?
Добавить в закладки
Или поделиться!

Связанные темы

array - статический массив (после создания размер не изменяется). Быстрее вектора.
Выбор контейнера из стандартной библиотеки С++.
deque - двусторонняя очередь (дек). Эффективное вставка-удаление по концам очереди.
forward_list - односвязный список с эффективной вставкой/удалением в начало списка.
list - двусвязный список с эффективной вставкой/удалением в любом месте списка.
map - словарь сортированных уникальных пар ключ-значение.
multimap - словарь сортированных неуникальных пар ключ-значение.
multiset - множество сортированных неуникальных элементов.
priority_queue - очередь с приоритетом (с сортировкой значений).
queue - очередь FIFO first in, first out "первый пришел - первый ушел".
set - множество сортированных уникальных элементов.
stack - стек LIFO last in, first out "последний пришел - первый ушел".
unordered_map - словарь несортированных уникальных пар ключ-значение.
unordered_multimap - словарь несортированных неуникальных пар ключ-значение.
unordered_multiset - множество несортированных неуникальных значений.
unordered_set - множество несортированных уникальных значений.
vector - вектор (массив) значений с изменяемым размером.