Контейнерные классы C++<list>
Стандартная библиотека C++ предоставляет богатый набор возможностей, среди которых<list>является очень важным контейнерным классом для хранения коллекций элементов, поддерживающим двунаправленные итераторы.
<list>является последовательным контейнером в Стандартной библиотеке шаблонов C++ (STL), который позволяет быстро вставлять и удалять элементы в любом месте контейнера. В отличие от массивов или векторов (<vector>) отличается,<list>не требует указания размера при создании и позволяет добавлять или удалять элементы в любой позиции без перераспределения памяти.
Синтаксис
Ниже приведены<list>Некоторые основные операции с контейнерами:
- Подключение заголовочного файла:
#include <list> - Объявление списка:
std::list<T> mylist;, гдеT— это тип элементов, хранящихся в списке. - Вставка элементов:
mylist.push_back(value); - Удаление элемента:
mylist.pop_back();илиmylist.erase(iterator); - Доступ к элементам:
mylist.front();иmylist.back(); - Обход списка: использование итераторов
for (auto it = mylist.begin(); it != mylist.end(); ++it)
Особенности
- Двунаправленная итерация：
<list>предоставляет двунаправленные итераторы, позволяющие обходить элементы вперёд и назад. - Динамический размер: в отличие от массивов,
<list>Размер может изменяться динамически, без необходимости предварительно выделять фиксированный объём памяти. - Быстрая вставка и удаление: элементы можно быстро вставлять или удалять в любой позиции списка, без необходимости перемещать большое количество элементов, как это было бы в случае с векторами.
Объявление и инициализация
<list>Объявление и инициализация аналогичны другим контейнерам:
#include <iostream>
#include <list>
int main() {
std::list<int> lst1; // 空的list
std::list<int> lst2(5); // 包含5个默认初始化元素的list
std::list<int> lst3(5, 10); // 包含5个元素，每个元素为10
std::list<int> lst4 = {1, 2, 3, 4}; // 使用初始化列表
return 0;
}
Пример
Ниже приведён пример использования<list>Простой пример, включающий создание списка, добавление элементов, обход списка и вывод результатов.
Пример
#include <iostream>
#include <list>
int main() {
// создать список целочисленного типа
std::list<int> numbers;
// добавить элементы в список
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// обратиться к первому элементу списка и вывести его
std::cout << "Первый элемент: " << numbers.front() << std::endl;
// обратиться к последнему элементу списка и вывести его
std::cout << "Последний элемент: " << numbers.back() << std::endl;
// пройти по списку и вывести все элементы
std::cout << "Элементы списка: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// удалить последний элемент списка
numbers.pop_back();
// снова пройти по списку и вывести все элементы
std::cout << "Элементы списка после удаления последнего элемента: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
// создать список целочисленного типа
std::list<int> numbers;
// добавить элементы в список
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// обратиться к первому элементу списка и вывести его
std::cout << "Первый элемент: " << numbers.front() << std::endl;
// обратиться к последнему элементу списка и вывести его
std::cout << "Последний элемент: " << numbers.back() << std::endl;
// пройти по списку и вывести все элементы
std::cout << "Элементы списка: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// удалить последний элемент списка
numbers.pop_back();
// снова пройти по списку и вывести все элементы
std::cout << "Элементы списка после удаления последнего элемента: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Вывод:
First element: 10 Last element: 30 List elements: 10 20 30 List elements after removing the last element: 10 20
Общие функции-члены
Ниже приведены<list>Некоторые часто используемые функции-члены:
| Функция | Описание |
|---|---|
push_back(const T& val) |
Добавить элемент в конец связного списка |
push_front(const T& val) |
Добавить элемент в начало связного списка |
pop_back() |
Удалить элемент в конце связного списка |
pop_front() |
Удалить элемент в начале связного списка |
insert(iterator pos, val) |
Вставить элемент в указанную позицию |
erase(iterator pos) |
Удалить элемент в указанной позиции |
clear() |
Очистить все элементы |
size() |
Вернуть количество элементов в связном списке |
empty() |
Проверить, пуст ли связный список |
front() |
Вернуть первый элемент связного списка |
back() |
Вернуть последний элемент связного списка |
remove(const T& val) |
Удалить все элементы, равные заданному значению |
sort() |
Отсортировать элементы в связном списке |
merge(list& other) |
Объединить с другим отсортированным связным списком |
reverse() |
Развернуть связный список |
begin() / end() |
Вернуть итераторы begin/end связного списка |
Пример
1. Основные операции
Пример
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Вставка и удаление элементов
lst.push_front(5); // Вставить 5 в начало
lst.push_back(40); // Вставить 40 в конец
lst.pop_front(); // Удалить первый элемент
lst.pop_back(); // Удалить последний элемент
// Вывести содержимое связного списка
std::cout << "Элементы списка: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Вставка и удаление элементов
lst.push_front(5); // Вставить 5 в начало
lst.push_back(40); // Вставить 40 в конец
lst.pop_front(); // Удалить первый элемент
lst.pop_back(); // Удалить последний элемент
// Вывести содержимое связного списка
std::cout << "Элементы списка: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
2. Вставка и удаление элементов в указанных позициях
Пример
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Переместить итератор к 3-му элементу (значение 3)
lst.insert(it, 10); // Вставить 10 перед 3-м элементом
lst.erase(it); // Удалить 3-й элемент
// Вывести содержимое связного списка
std::cout << "Элементы списка: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Переместить итератор к 3-му элементу (значение 3)
lst.insert(it, 10); // Вставить 10 перед 3-м элементом
lst.erase(it); // Удалить 3-й элемент
// Вывести содержимое связного списка
std::cout << "Элементы списка: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
3. Сортировка и удаление дубликатов
Пример
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Сортировать
lst.unique(); // Удалить соседние повторяющиеся элементы
// Вывести содержимое связного списка
std::cout << "Отсортированный список без дубликатов: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Сортировать
lst.unique(); // Удалить соседние повторяющиеся элементы
// Вывести содержимое связного списка
std::cout << "Отсортированный список без дубликатов: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
4. Слияние и разворот
Пример
#include <iostream>
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Объединить два отсортированных связных списка
lst1.reverse(); // Перевернуть связный список
// Вывести содержимое связного списка
std::cout << "Объединённый и перевёрнутый список: ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Объединить два отсортированных связных списка
lst1.reverse(); // Перевернуть связный список
// Вывести содержимое связного списка
std::cout << "Объединённый и перевёрнутый список: ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
Сравнение с другими контейнерами
| Особенности | std::list | std::vector | std::deque |
|---|---|---|---|
| Структура памяти | Несмежная память, двусвязный список | Непрерывная память | Сегментированная непрерывная память |
| Производительность доступа | Последовательный доступ быстрый, произвольный доступ медленный | Быстрый произвольный доступ | Доступ как к хвосту, так и к началу — быстрый |
| Производительность вставки/удаления | Вставка и удаление в любую позицию выполняются быстро | Вставка в конец выполняется быстро, а в середину — медленно | Вставка и удаление в начале и в конце выполняются быстро |
| Применимые сценарии | Частые вставки/удаления в середине | Требуется эффективный произвольный доступ | Требуется быстрая вставка/удаление в начале и в конце |
| Стабильность итераторов | Стабильны; вставка или удаление элементов не вызывает инвалидации | Вставка и удаление могут вызвать инвалидацию итераторов | Вставка и удаление могут вызвать инвалидацию итераторов |
Примечания
<list>Элементы хранятся в порядке вставки, а не сортируются по значению элемента.- Из-за
<list>Элементы хранятся в разных участках памяти, поэтому это не подходит для сценариев, требующих произвольного доступа. - По сравнению с векторами,
<list>Эффективность использования памяти низкая, потому что для каждого элемента требуется дополнительное пространство для хранения указателей на предыдущий и следующий элементы.
С помощью этого простого введения и примеров новички смогут получить базовое представление о<list>контейнере C++ и начать использовать его для решения практических задач.