Kaidzu.com
Таймеры
Си
C++
Python
Миландр- 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} Перемещаем элементы внутри списка
}
