C++STL(2) list container summary

C++ STL(2) list container summary

1. Overview

std::list is a doubly linked list container provided by the C++ standard library. Unlike std::vector, std::list does not store elements based on continuous memory, but links each element through pointers. This gives std::list better performance when inserting and deleting elements, but poorer performance when randomly accessing elements.

The following are some features of std::list:

Doubly linked list: The elements of std::list are stored in the form of a doubly linked list, and each element contains a pointer to the previous element and the next element.
Insertion and deletion: Due to the characteristics of linked lists, std::list is very efficient when inserting and deleting elements without moving other elements. The time complexity of insertion and deletion operations is O(1).
No memory reallocation required: Unlike std::vector, std::list does not require memory reallocation when elements are inserted and deleted because It uses pointers to link elements.
No random access: Since std::list is not based on contiguous memory, it cannot be randomly accessed through indexing like std::vector. To access the elements in std::list, you need to traverse the linked list from the beginning or the end.
Iterator stability: The iterator of std::list remains valid after insertion and deletion operations, and will not become invalid or point to invalid elements.
Usage Note: Since the elements of std::list are not stored in continuous memory, its access speed is relatively slow. In most cases, if frequent random access or insertion/deletion operations at the tail are required, std::vector may be more appropriate.

2. Detailed introduction and usage

When using C++’s std::list container, it can be initialized in a variety of ways. Here are some common ways to initialize a std::list container:

Default initialization: Create an empty std::list container.

std::list<int> myList; // The default constructor creates an empty list

Initialize with element range: Initialize the std::list container with the range of elements in other containers.

std::vector<int> vec = {<!-- -->1, 2, 3, 4};
std::list<int> myList(vec.begin(), vec.end()); // Initialize list using the range of elements in vec

Initialize with duplicate elements: Initialize the std::list container with the same element value.

std::list<int> myList(5, 42); // Initialize a list containing 5 elements with a value of 42

Initialization using initialization list: Use a brace initialization list to initialize the std::list container.

std::list<int> myList = {<!-- -->1, 2, 3, 4}; // Initialize the list using the initialization list

When using C++’s std::list container, the following is a detailed introduction to some commonly used functions:

push_back(): Insert an element at the end of the container.

std::list<int> myList;
myList.push_back(42); //Insert element 42 at the end of the container

push_front(): Insert an element at the beginning of the container.

std::list<int> myList;
myList.push_front(42); //Insert element 42 at the beginning of the container

pop_back(): Delete the element at the end of the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4};
myList.pop_back(); // Delete the element at the end of the container. At this time, the container is {1, 2, 3}

pop_front(): Delete the element at the beginning of the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4};
myList.pop_front(); // Delete the element at the beginning of the container. At this time, the container is {2, 3, 4}

size(): Returns the number of elements in the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4};
std::cout << myList.size() << std::endl; // Output: 4

empty(): Check whether the container is empty.

std::list<int> myList;
if (myList.empty()) {<!-- -->
  std::cout << "Container is empty" << std::endl;
} else {<!-- -->
  std::cout << "Container is not empty" << std::endl;
}

clear(): Empty the container and delete all elements.

std::list<int> myList = {<!-- -->1, 2, 3, 4};
myList.clear(); // Clear the container, the container is empty at this time

begin() and end(): used for the starting and ending positions of the iterator.

std::list<int> myList = {<!-- -->1, 2, 3, 4};

// Use iterator to traverse the container
for (auto it = myList.begin(); it != myList.end(); + + it) {<!-- -->
  std::cout << *it << " ";
}
std::cout << std::endl; // Output: 1 2 3 4

rbegin() and rend(): used for the starting and ending positions of reverse iterators.

std::list<int> myList = {<!-- -->1, 2, 3, 4};

// Use reverse iterator to traverse the container
for (auto it = myList.rbegin(); it != myList.rend(); + + it) {<!-- -->
  std::cout << *it << " ";
}
std::cout << std::endl; // Output: 4 3 2 1

insert(): Insert one or more elements at the specified position.

std::list<int> myList = {<!-- -->1, 2, 3, 4};
auto it = myList.begin();
 + + it; // Move the iterator to the second position

myList.insert(it, 42); //Insert element 42 at the second position, and the container is {1, 42, 2, 3, 4}

//Insert range of elements at the second position
std::vector<int> vec = {<!-- -->5, 6};
myList.insert(it, vec.begin(), vec.end()); // The container at this time is {1, 5, 6, 42, 2, 3, 4}

erase(): Remove elements at the specified position or range from the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4, 5};
auto it = myList.begin();
 + + it; // Move the iterator to the second position

myList.erase(it); // Delete the element at the second position. At this time, the container is {1, 3,4, 5}

//Delete elements in the specified range
auto first = myList.begin();
auto last = myList.end();
--last; // Move the iterator to the last position
myList.erase(first, last); // Delete the elements from the first position to the last position. At this time, there is only one element left in the container: {5}

front() and back(): Return references to the first and last elements of the container respectively .

std::list<int> myList = {<!-- -->1, 2, 3, 4};

int firstElement = myList.front(); // Get the first element, the value is 1
int lastElement = myList.back(); // Get the last element, the value is 4

assign(): Replace the contents of the container with new elements.

std::list<int> myList = {<!-- -->1, 2, 3, 4};

// Replace the contents of the container with new elements {5, 6, 7}
myList.assign({<!-- -->5, 6, 7}); // The container becomes {5, 6, 7}

resize(): Change the size of the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4};

myList.resize(6); // Adjust the size of the container to 6. By default, 0 is used to fill the remaining positions, and the container becomes {1, 2, 3, 4, 0, 0}

myList.resize(3); // Adjust the size of the container to 3, redundant elements are deleted, and the container becomes {1, 2, 3}

remove(): Removes all elements in the container that are equal to the given value.

std::list<int> myList = {<!-- -->1, 2, 2, 3, 4, 2};

myList.remove(2); // Delete all elements with a value of 2 in the container, and the container becomes {1, 3, 4}

reverse(): Reverse the order of elements in the container.

std::list<int> myList = {<!-- -->1, 2, 3, 4};

myList.reverse(); // Reverse the order of elements in the container, the container becomes {4, 3, 2, 1}

sort(): Sort the elements in the container.

std::list<int> myList = {<!-- -->4, 2, 1, 3};

myList.sort(); // Sort the elements in the container in ascending order, and the container becomes {1, 2, 3, 4}

merge(): Merges two sorted containers into one sorted container.

std::list<int> list1 = {<!-- -->1, 3, 5};
std::list<int> list2 = {<!-- -->2, 4, 6};

list1.merge(list2); // Merge list2 into list1. Both list1 and list2 must be sorted containers. After merging, list1 becomes {1, 2, 3, 4, 5, 6} and list2 becomes empty.

splice(): Moves the elements of one container to the specified position in another container.

std::list<int> list1 = {<!-- -->1, 2, 3};
std::list<int> list2 = {<!-- -->4, 5};
auto it = list1.begin();
 + + it; // Move the iterator to the second position

list1.splice(it, list2); // Before moving all elements in list2 to the second position of list1, list1 becomes {1, 4, 5, 2, 3} and list2 becomes empty

unique(): Used to remove adjacent duplicate elements in the container, leaving only one copy. This function will modify the container in place and remove duplicate elements.

std::list<int> myList = {<!-- -->1, 1, 2, 2, 3, 3, 4, 4};

myList.unique(); // Remove adjacent duplicate elements and the container becomes {1, 2, 3, 4}
Note that the `unique()` function can only remove adjacent duplicate elements. If you want to remove all duplicate elements, you can sort the container first and then use the `unique()` function.

max_size(): Returns the maximum number of elements that the std::list container can hold. This function returns an unsigned integer representing the maximum capacity of the container.

std::list<int> myList;
std::cout << "Maximum capacity:" << myList.max_size() << std::endl;
Note that `max_size()` returns the theoretical maximum capacity, and the actual allocated capacity may be limited by system limitations or available memory.

emplace_back(): Used to construct a new element directly at the end of the container. Compared with the push_back() function, emplace_back() can construct objects directly in the container without creating temporary objects.

struct MyStruct {<!-- -->
  int value1;
  std::string value2;
  
  MyStruct(int v1, std::string v2) : value1(v1), value2(v2) {<!-- -->}
};

std::list<MyStruct> myList;

myList.emplace_back(42, "Hello"); // Construct a new element directly at the end of the container

// Equivalent to
myList.push_back(MyStruct(42, "Hello"));

Using `emplace_back()` can avoid creating temporary objects and improve efficiency.

3. Conclusion

std::list is a doubly linked list container provided by the C++ standard library. It is similar to other containers (such as std::vector, < Compared with code>std::deque), std::list has some unique features:

High efficiency of insertion and deletion operations: Since std::list is implemented based on a linked list, insertion and deletion operations are very efficient for elements at any position, regardless of the size of the container. Influence. This gives std::list an advantage in scenarios where frequent insertion and deletion operations are required.
No need for continuous memory: std::list uses a linked list structure to store elements, and does not require elements to be stored continuously in memory. This allows std::list to handle large numbers of elements or frequent changes in element size.
Stable iterators: When inserting and deleting operations on std::list, iterators that are independent of the elements being operated remain valid. This is due to the nature of the linked list. determined by characteristics. This makes std::list very useful in scenarios where insertion and deletion operations need to be performed during iteration.

However, std::list also has some limitations and disadvantages:

Low efficiency of random access: Due to the characteristics of linked lists, std::list does not support random access through indexes. If you need to frequently access elements by index, using std::vector may be more appropriate.
Extra space overhead: Compared with other containers, std::list requires additional pointers to maintain the linked list structure when storing each element, which will introduce a certain amount of space overhead.

To sum up, std::list is very useful in certain application scenarios, especially when insertion and deletion operations are frequent, random access is not required, or stable iterators are required. However, in other cases, other containers may be more suitable, and the choice depends on specific needs and performance requirements. When selecting a container, factors such as the characteristics of the data structure, complexity of operations, memory usage, and performance requirements need to be comprehensively considered.

The best container choice depends on the specific use case and needs, and no one container fits all. Therefore, it is important to be familiar with the characteristics and applicable scenarios of various containers in order to make the right choice based on specific needs.