One, foreword
List container, also known as bi-directional linked list container, that is, the bottom of the container is implemented in the form of bi-directional linked list, so the elements in the list container can be scattered in the memory space, rather than must be stored in a continuous memory space. The order of the elements in a list is tied to Pointers. Each element has two Pointers, one to its previous element and one to its next. The forward pointer to the first element is always null because it has no elements before it; Similarly, the back pointer to the trailing element is always null. Advantage: Elements can be quickly inserted or deleted anywhere the sequence is known (O(1) time). It is also more efficient to move elements around in a List than in any other container. Disadvantages: You cannot access elements by subscript. You can only traverse the container starting with the first or last element in the container until you find the corresponding element. The List container takes the form of the template class List
(T is the type of the stored element) in the < List > header and is located in the STD namespace. The header file should be included when using:
#include <list>
using namespace std;Initialize the list
There are five ways to create a List container
1) STD: : list < int > listInt; (2) the STD: : list < int > listInt (10); (3) STD: : list < int > listInt (10, 5); (4) STD: : list < int > listInt2 (listInt); Int a[] = {1,2,3,4,5}; int a[] = {1,2,3,4,5}; std::list<int> listInt(a, a+5); Array <int, 5> arrInt{11,12,13,14,15}; array<int, 5> arrInt{11,12,13,14,15}; std::list<int> listInt(arrInt.begin()+2, arr.end());Create a list with 10 elements (default value = 0) and a list with 10 elements (initial value = 5). Create a list with 10 elements (initial value = 5). ⑤ We create a list by copying elements from a range specified in a container of another type (or an array). We create a list by copying elements from a range specified in a container of another type (or a plain array)
1. Member functions
Functions such as iterators, add and delete are not listed here.
| function | function |
|---|---|
| empty() | Returns true if there are any elements in the container. Otherwise, it returns false |
| size() | Returns the actual number of elements in the current container |
| max_size() | Returns the maximum number of elements that a container can contain, normally 232-1 |
| front() | Returns a reference to the first element |
| back() | Returns a reference to the last element |
| assign() | Replace the contents of the container with new elements |
| swap(x,y) | To swap elements from two containers, you must ensure that the types of the elements stored in both containers are the same |
| resize() | Resize the container |
| splice() | Inserts elements from one List into a specified location in another |
| merge() | Merges two pre-ordered Lists, and the merged Lists are still ordered |
| sort() | Sorts the elements in the container by changing their position |
| reverse() | Inverts the order of the elements in the container |
2, the instance,
1) Create a list
std::list<int> listInt; listInt.push_back(31); listInt.push_back(27); listInt.push_back(29); std::cout << " listInt size: " << listInt.size() << std::endl; int i = 0; std::list<int>::iterator listIter = listInt.begin(); for (; listIter ! = listInt.end(); listIter++) { std::cout << " listInt[" << i++ << "]=" << *listIter << std::endl; } listInt.sort(); i = 0; listIter = listInt.begin(); for (; listIter ! = listInt.end(); listIter++) { std::cout << " sort listInt[" << i++ << "]=" << *listIter << std::endl; } int nFront = listInt.front(); int nBack = listInt.back(); std::cout << " listInt front: " << nFront << " back: " << nBack << std::endl; STD: : list < int > listInt1 14,25,99 {}; listInt1.sort(); listInt.merge(listInt1); i = 0; listIter = listInt.begin(); for (; listIter ! = listInt.end(); listIter++) { std::cout << " merge listInt[" << i++ << "]=" << *listIter << std::endl; }The results are as follows:
Iterators
| function | function |
|---|---|
| begin() | Returns a bidirectional iterator to the first element in the container (forward iterator) |
| end() | Returns a bidirectional iterator that refers to the position following the position of the last element in the container. (forward iterator) |
| rbegin() | Returns a reverse bidirectional iterator to the last element |
| rend() | Returns a reverse bidirectional iterator to the position before the position of the first element |
| cbegin() | The forward iterator has the same function as begin(), except that it adds a const attribute that cannot be used to modify elements |
| cend() | The forward iterator has the same function as end(), except that it adds a const attribute that cannot be used to modify elements |
| crbegin() | The reverse iterator has the same function as rbegin(), except that it adds a const attribute that cannot be used to modify elements |
| crend() | The reverse iterator has the same function as rend(), except that it adds a const attribute that cannot be used to modify elements |
Refer to the Array container for more details. The most important difference between a list’s iterator and a vector’s iterator is that it is a bidirectional iterator instead of a random-access iterator. If p1 and p2 are bidirectional iterators, then ++p1, p1++, p1–, p1++, *p1, p1==p2, and p1! = (p2); Do not support P1 [I], P1 -= I, P1 += I, P1 + I, P1 – I, P1
1, the instance,
1) Inspect the list elements
i = 0; listIter = listInt.begin(); for (; listIter ! = listInt.end(); listIter++) { std::cout << " sort listInt[" << i++ << "]=" << *listIter << std::endl; }Other functions are similar to vector and so on, but do not specify how to use them
Note: 1, the list does not support random access, did not provide the subscript operator [] and the at () member function, also did not provide the data () member function 2, front and back () () member function, can be the first element in the list container are obtained respectively and the last element reference form, If we want to access elements elsewhere in the list, we can only use the list iterator. We can also use iterators to change the value of the specified element
Insert elements
| function | function |
|---|---|
| push_front() | Adds a new element to the list before the first element |
| push_back() | Adds a new element to the list after the last element |
| emplace_front() | Generates a new element directly before the first element in the container |
| emplace_back() | A new element is generated directly after the last element in the container |
| emplace() | Generates a new element directly at the specified location of the container |
| insert() | Inserts a new element at the specified location |
| splice() | Adds elements from other List containers to the current List at the specified location |
1. Insert method
| format | instructions |
|---|---|
| iterator insert(pos,elem) | Inserts a new element elem before the position specified by iterator pos and returns an iterator representing the position of the newly inserted element |
| iterator insert(pos,n,elem) | Inserts n elements elem before the position specified by iterator pos and returns an iterator representing the position of the first newly inserted element |
| iterator insert(pos,first,last) | Inserts all elements in the [first,last] region of other containers (such as Array, Vector, deque, etc.) before the position specified by iterator pos, and returns an iterator representing the position of the first newly inserted element |
| iterator insert(pos,initlist) | Before the position specified by iterator pos, insert all elements in the initializer list (multiple elements enclosed in braces {}, separated by commas) and return an iterator representing the position of the first newly inserted element |
2. Splice method
| format | instructions |
|---|---|
| void splice (iterator position, list& x); | Unit 2 |
| Unit 3 | Position is an iterator that indicates the insertion position; X is another list container. The splice() method in this format moves all elements stored in the X container to the position specified in the current List container |
| void splice (iterator position, list& x, iterator i); | Position is an iterator that indicates the insertion position; X is another list; I is also an iterator that refers to an element in the X container. The splice() method in this format moves the element pointed to by I in the X container to the position specified in the current container. |
| void splice (iterator position, list& x, iterator first, iterator last); | Position is an iterator that indicates the insertion position; X is another list; First and last are iterators. [fist,last] is used to specify an area of X. The splice() method in this format moves all elements in the scope of X [first, last] to the position specified in the current container. |
How the splice() member method moves elements
Remove the node that stores the element from the list at the bottom of the list and link it to the list at the bottom of the current list. When an element from the list1 container is added to the list2 container using the splice() member method, the element is removed from the list1 container.
3, the instance,
This is mainly an instance of the Splice method
1), Method 1
STD ::list<int> listInt1{16,72,100}, listInt2{9,201,94}; std::list<int>::iterator listIter = ++listInt1.begin(); **listInt1.splice(listIter, listInt2); ** int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); std::list<int>::iterator listIter2 = listInt2.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl; } for (; listIter2 ! = listInt2.end(); listIter2++) { std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl; }The results are as follows:
2) Method 2
STD ::list<int> listInt1{16,72,100}, listInt2{9,201,94}; std::list<int>::iterator listIter = ++listInt1.begin(); **listInt2.splice(listInt2.begin(), listInt1, listIter); ** int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); std::list<int>::iterator listIter2 = listInt2.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl; } for (; listIter2 ! = listInt2.end(); listIter2++) { std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl; }The results are as follows:
3) Method 3
STD ::list<int> listInt1{16,72,100}, listInt2{9,201,94}; std::list<int>::iterator listIter = ++listInt1.begin(); ** listInt2.splice(listInt2.begin(), listInt1, listInt1.begin(), listInt1.end()); ** int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); std::list<int>::iterator listIter2 = listInt2.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl; } for (; listIter2 ! = listInt2.end(); listIter2++) { std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl; }The results are as follows:
Delete elements
| function | instructions |
|---|---|
| pop_front() | Deletes an element at the top of the List |
| pop_back() | Deletes an element at the end of the List |
| erase() | This member function can delete either an element at a specified location in a List container or multiple elements within a region of the container. |
| clear() | Delete all elements from the List container |
| remove(val) | Deletes all elements in the container that are equal to val |
| unique() | Deletes adjacent duplicate elements from the container, keeping only one copy |
| remove_if() | Deletes the element in the container that meets the criteria |
1, erase,
| format | instructions |
|---|---|
| iterator erase (iterator position); | Deletes the element in the list at the position referenced by the position iterator |
| iterator erase (iterator first, iterator last); | Deletes all elements in the list that are bounded by the first and last iterators (including the elements to which first refers, but not the elements to which last refers) |
2, the unique
| format | instructions |
|---|---|
| void unique() | Remove adjacent duplicate elements from the List |
| Void Unique (BinaryPredicate) | Remove adjacent duplicate elements from a list, leaving only one copy |
3, the instance,
This is mainly the use of unique() and remove_if()
1), a unique ()
STD: : list < int > listInt1,72,72,100,72,109,203,671,109,192,671 {16}, listInt2 {9201,94,43,67,81,901}; **listInt1.unique(); ** int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl; }The results are as follows:
According to the results:
① Only two adjacent elements can be compared. It is also applicable if three or more consecutive elements have the same value
bool test(int first, int second) { return (first <= second); } STD: : list < int > listInt1 {72,73,100,72,44,48,109,92,671,15,192,671}; listInt1.unique(test); int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl; }The results are as follows:
From the results we can see that
When test returns true, the element is deleted
When false is returned, the values of the two elements to be compared are retained
Such as: step is,73,100,72,44,48,109,92,671,15,192,671 {72}
①72,73 return true, delete 73; Return true, delete 100; Returns true and removes 72
Return false; leave 72,44
Return true; drop 48; Return true, delete 109; Return true; delete ’92’; Returns true, delete 671
(4, 4,15) return false
⑤ return true, delete 192; Return true delete 671
Therefore, the data in the final list is {72.44.15}
Note:
In addition to the way predicate functions are defined above, you can also use LAMBA expressions and function objects.
2), remove_if
STD: : list < int > listInt1 {72,73,100,72,44,48,109,92,671,109,15,671}; listInt1.remove_if([](int nValue) {return nValue < 100; }); int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl; }or
Bool test(int nValue) {bool bRet = (nValue < 100); return bRet; } STD: : list < int > listInt1 {72,73,100,72,44,48,109,92,671,109,15,671}; listInt1.remove_if(test); int i = 0; std::list<int>::iterator listIter1 = listInt1.begin(); for (; listIter1 ! = listInt1.end(); listIter1++) { std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl; }The results are as follows:
Elements with values greater than or equal to 100 are preserved
