C++ container classes<list>
The C++ standard library provides a rich set of features, among which<list>is a very important container class for storing collections of elements, supporting bidirectional iterators.
<list>is a sequence container in the C++ Standard Template Library (STL) that allows fast insertion and deletion of elements at any position in the container. Unlike arrays or vectors (<vector>) different,<list>does not need to specify a size at creation, and can add or remove elements at any position without reallocating memory.
Syntax
The following are<list>Some basic operations of containers:
- Include header file:
#include <list> - Declare a list:
std::list<T> mylist;, whereTIs the type of elements stored in the list. - Insert elements:
mylist.push_back(value); - Delete element:
mylist.pop_back();ormylist.erase(iterator); - Access elements:
mylist.front();andmylist.back(); - Traversing the list: using iterators
for (auto it = mylist.begin(); it != mylist.end(); ++it)
Features
- Bidirectional iteration：
<list>provides bidirectional iterators, allowing elements to be traversed forward and backward. - Dynamic size: Unlike arrays,
<list>The size can change dynamically, without the need to pre-allocate a fixed amount of memory. - Fast insertion and deletion: elements can be quickly inserted or removed at any position in the list, without needing to move a large number of elements as would be the case with vectors.
Declaration and initialization
<list>The declaration and initialization are similar to other containers:
#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;
}
Example
Below is an example using<list>A simple example, including creating a list, adding elements, traversing the list, and outputting the results.
Example
#include <iostream>
#include <list>
int main() {
// create a list of integer type
std::list<int> numbers;
// add elements to the list
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// access and print the first element of the list
std::cout << "First element: " << numbers.front() << std::endl;
// access and print the last element of the list
std::cout << "Last element: " << numbers.back() << std::endl;
// Traverse the list and print all elements
std::cout << "List elements: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// Delete the last element in the list
numbers.pop_back();
// Traverse the list again and print all elements
std::cout << "List elements after removing the last element: ";
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() {
// create a list of integer type
std::list<int> numbers;
// add elements to the list
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// access and print the first element of the list
std::cout << "First element: " << numbers.front() << std::endl;
// access and print the last element of the list
std::cout << "Last element: " << numbers.back() << std::endl;
// Traverse the list and print all elements
std::cout << "List elements: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// Delete the last element in the list
numbers.pop_back();
// Traverse the list again and print all elements
std::cout << "List elements after removing the last element: ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Output:
First element: 10 Last element: 30 List elements: 10 20 30 List elements after removing the last element: 10 20
Common member functions
The following are<list>Some commonly used member functions:
| Function | Description |
|---|---|
push_back(const T& val) |
Add an element at the end of the linked list |
push_front(const T& val) |
Add an element at the head of the linked list |
pop_back() |
Remove the element at the end of the linked list |
pop_front() |
Remove the element at the head of the linked list |
insert(iterator pos, val) |
Insert an element at a specified position |
erase(iterator pos) |
Remove the element at a specified position |
clear() |
Clear all elements |
size() |
Return the number of elements in the linked list |
empty() |
Check whether the linked list is empty |
front() |
Return the first element of the linked list |
back() |
Return the last element of the linked list |
remove(const T& val) |
Remove all elements equal to a specified value |
sort() |
Sort the elements in the linked list |
merge(list& other) |
Merge another sorted linked list |
reverse() |
Reverse linked list |
begin() / end() |
Return the begin/end iterators of the linked list |
Example
1. Basic operations
Example
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Insert and delete elements
lst.push_front(5); // Insert 5 at the head
lst.push_back(40); // Insert 40 at the tail
lst.pop_front(); // Delete the head element
lst.pop_back(); // Delete the tail element
// Output the linked list contents
std::cout << "List elements: ";
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};
// Insert and delete elements
lst.push_front(5); // Insert 5 at the head
lst.push_back(40); // Insert 40 at the tail
lst.pop_front(); // Delete the head element
lst.pop_back(); // Delete the tail element
// Output the linked list contents
std::cout << "List elements: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
2. Inserting and deleting elements at specific positions
Example
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Move the iterator to the 3rd element (value 3)
lst.insert(it, 10); // Insert 10 before the 3rd element
lst.erase(it); // Delete the 3rd element
// Output the linked list contents
std::cout << "List elements: ";
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); // Move the iterator to the 3rd element (value 3)
lst.insert(it, 10); // Insert 10 before the 3rd element
lst.erase(it); // Delete the 3rd element
// Output the linked list contents
std::cout << "List elements: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
3. Sorting and deduplication
Example
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Sort
lst.unique(); // Remove adjacent duplicate elements
// Output the linked list contents
std::cout << "Sorted and unique list: ";
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(); // Sort
lst.unique(); // Remove adjacent duplicate elements
// Output the linked list contents
std::cout << "Sorted and unique list: ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
4. Merging and reversing
Example
#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); // Merge two sorted linked lists
lst1.reverse(); // Reverse linked list
// Output the linked list contents
std::cout << "Merged and reversed list: ";
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); // Merge two sorted linked lists
lst1.reverse(); // Reverse linked list
// Output the linked list contents
std::cout << "Merged and reversed list: ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
Comparison with other containers
| Features | std::list | std::vector | std::deque |
|---|---|---|---|
| Memory structure | Non-contiguous memory, doubly linked list | Contiguous memory | Segmented contiguous memory |
| Access performance | Sequential access is fast, random access is slow | Fast random access | Access at both the tail and head is fast |
| Insertion/deletion performance | Insertion and deletion at any position are fast | Insertion at the end is fast, but in the middle is slow | Insertion and deletion at head and tail are fast |
| Applicable scenarios | Frequent insertion/deletion in the middle | Requires efficient random access | Need fast insertion/deletion at the head and tail |
| Iterator stability | Stable; insertion or deletion of elements will not cause invalidation | Insertion and deletion may cause iterator invalidation | Insertion and deletion may cause iterator invalidation |
Notes
<list>The elements are stored in insertion order, not sorted by element value.- Due to
<list>The elements are stored in different memory locations, so it is not suitable for scenarios requiring random access. - Compared to vectors,
<list>Memory usage efficiency is low because each element requires extra space to store pointers to the previous and next elements.
Through this simple introduction and examples, beginners should be able to gain a basic understanding of C++'s<list>container, and begin using it to solve real-world problems.