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