Series of articles
Naturally, you can’t bypass STL on the way to learn C ++, in this series of articles
We talked about the use of string and the simulation implementation of string, as well as the use of vector and the simulation implementation of vector.
If you are interested, you can browse through it.
Directory
series of articles
foreword
default member function
Constructor
copy construction
assignment overloading
iterator
Capacity query
data access
data modification
assign
Head plug delete tail plug tail delete
Insert and delete at specified position
iterator invalidation
exchange
other operations
splice
remove
merge
Deduplication
reverse
to sort
Foreword
list is another important container in STL, and list is actually the encapsulation of linked list. When it comes to linked lists, I believe everyone’s first reaction is single-linked lists, and the disadvantages of single-linked lists are obvious: tail insertion is too troublesome, only one-way access, etc. But in fact, the linked list encapsulated in the list is not an ordinary single linked list, but the leading two-way circular linked list mentioned before.
It can optimize most of the shortcomings of the singly linked list except random access, and it is packaged again so it is very convenient to use.
This time we will mainly talk about how to use the list, and more implementation details will be discussed in the simulation implementation.
Default member function
Remember to take the lead file before using the list, otherwise the list cannot be used.
Constructor
Same as the container learned before, the constructor of list is still the same.
- Create an empty list
- Create a linked list of n nodes whose value is val
- Construct with an iterator range
According to different writing methods, the results after initialization are also different.
int main()
{
list<int> l1; // empty list
list<int> l2(5, 3); //33333
int arr[] = { 1,2,3,4,5,6 };
list<int> l3(arr, arr + 6); //123456
return 0;
}
copy construction
If the parameter is also a list, it is naturally a copy construction. The copy is deep copy. The values inside the nodes are the same, but the addresses of the nodes are different.
Initialize a new list with an already initialized list, and the final printed results should be the same.
int main()
{
list<int> l1(5, 3);
list<int> l2(l1);
//list<int> l2 = l1; //You can also write like this
for (auto i : l2)
{
cout << i << " ";
}
cout << endl;
return 0;
}
Assignment Overload
Assignment overloading is used for assignment between two existing lists. If one of them has not been initialized, the actual call is copy construction.
Through this string of codes, we can clearly see the changes of the list before and after the assignment.
int main()
{
list<int> l1(5, 3);
list<int> l2(3, 2);
cout << "Original l1" << ": ";
for (auto i : l1) cout << i << " ";
cout << endl;
l1 = l2;
cout << "now l1" << ": ";
for (auto i : l1) cout << i << " ";
cout << endl;
return 0;
}
Iterator
Although we usually only talk about iterators, iterators are also divided into three categories according to their capabilities.
- One-way iterators: only ++ iterators such as unorder_map
- Bidirectional iterators: yes + + also — such as list iterators
- Random iterators: + + , –, + , – e.g. vector iterators
The reason why it is a bidirectional iterator is that the underlying structure of the list is a leading bidirectional circular linked list, so that each node can access its own upper and lower nodes.
By calling the begin function, we can getan iterator pointing to the first valid data in the list.
Call end again to get the iterator that marks the end of the list, and then there is a boundary, and the traversal of the list can be completed.
First build a list, then get the begin iterator, and print the value of the current node until the end. Note: This interval is left closed and right open.
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9 };
list<int> l(arr, arr + 9);
list<int>::iterator it = l.begin();
//auto it = l.begin(); //You can also write like this
while (it != l.end()) //[begin,end)
{
cout << *it << " ";
it + + ;
}
cout << endl;
return 0;
}
The use of the reverse iterator is similar, except that the function called is replaced by rbegin and rend.
It is worth noting that the iteration of the reverse iterator also uses ++. But the iteration interval is the same as [rbegin, rend).
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9 };
list<int> l(arr, arr + 9);
list<int>::reverse_iterator it = l.rbegin(); //type name change
while (it != l. rend())
{
cout << *it << " ";
it + + ;
}
cout << endl;
return 0;
}
Capacity query
Since the linked list does nothave the concept of expansion, there is no reserve function, and resize is a modification function, which is not often used.
The most commonly used functions are the above two functions. empty is used to judge whether the linked list is empty, and size is used to check the number of current valid nodes.
We can write a piece of code and use it simply.
int main()
{
list<int> l1(3, 6);
list<int> l2;
if (!l1.empty()) //l1 is not empty, print size is 3
cout << "l1 size: " << l1. size() << endl;
if (!l2.empty()) //l2 is empty, not printed
cout << "l2 size: " << l2. size() << endl;
return 0;
}
Data Access
In list, we can use front and back to access the first and last elements of the linked list.
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9 };
list<int> l(arr, arr + 9);
cout << "front is: " << l.front() << endl;
cout << "back is: " << l.back() << endl;
return 0;
}
Data modification
assign
Just like in our previous constructor, the content can be converted into n vals or an iterator range.
However,previous content will be cleared.
int main()
{
list<int> l(2, 3); // 33
l. assign(5, 6); // 66666
for (auto it : l) cout << it << " ";
cout << endl;
vector<int> v = { 2,3,5,4,2 };
l.assign(v.begin(), v.end()); // 23542
for (auto it : l) cout << it << " ";
cout << endl;
return 0;
}
Delete the head plug and delete the tail and insert the tail
Through push_front and push_back you can achieve head and tail insertion, and pop_front and pop_back can do head and tail deletion.
Just remember that front means front and back means back, push means insert and pop means delete, so you won’t be confused about how to arrange and combine afterwards.
int main()
{
vector<int> v = { 2,3,5,4,2 };
list<int> l(v.begin(), v.end());
for (auto it : l) cout << it << " "; //Original linked list
cout << endl;
l.push_front(10);
l.push_back(20);
for (auto it : l) cout << it << " "; // linked list after insertion
cout << endl;
l. pop_front();
l. pop_back();
for (auto it : l) cout << it << " "; // linked list after deletion
cout << endl;
return 0;
}
Insert and delete at specified position
We can use insert and erase to insert and delete at specified positions, but we found that there is no find function in the list. If you need to get the iterator from begin every time + +, it would be too troublesome.
It doesn’t matter. There is a find function in the algorithm library that can meet our needs. Remember to bring the header file
This way we can insert and delete at will.
int main()
{
vector<int> v = { 2,3,5,4,2 };
list<int> l(v.begin(), v.end());
list<int>::iterator pos = find(l. begin(), l. end(), 3);
l.insert(pos, 20); //insert 20 before 3
for (auto it : l) cout << it << " ";
cout << endl;
pos = find(l. begin(), l. end(), 5);
l.erase(pos); //delete 5
for (auto it : l) cout << it << " ";
cout << endl;
return 0;
}
Iterator invalid
When we use erase to delete, at this timethe iterator pointing to the deleted position becomes invalid, and using it again will cause the program to crash.
So if you want to delete multiple times, you need to use the return value of erase to update the iterator after use, so that there will be no errors in use.
int main()
{
vector<int> v = { 2,3,5,4,6 };
list<int> l(v.begin(), v.end());
list<int>::iterator pos = find(l. begin(), l. end(), 3);
for (int i = 0; i < 3; i ++ )
{
pos = l.erase(pos); //Use the return value of erase to update the iterator
}
for (auto it : l) cout << it << " ";
cout << endl;
return 0;
}
Exchange
Same as in vector and string, the internal pointers are directly exchanged without copying the nodes.
int main()
{
vector<int> v1 = { 2,3,5,4,6 };
vector<int> v2 = { 1,2,3,4,5 };
list<int> l1(v1.begin(), v1.end());
list<int> l2(v2.begin(), v2.end());
for (auto it : l1) cout << it << " "; // before exchange
cout << endl;
for (auto it : l2) cout << it << " ";
cout << endl;
cout << endl;
l1. swap(l2);
for (auto it : l1) cout << it << " "; //after exchange
cout << endl;
for (auto it : l2) cout << it << " ";
cout << endl;
return 0;
}
Other operations
In addition to the basic operations above, there are some other functions in the library, and I will pick a few to talk about.
splice
This function can help us transfer the nodes of a linked list to another linked list.
After the function ends, l2 becomes an empty linked list, and its nodes are transferred to l1.
int main()
{
int arr[] = { 1,2,3,4,5,6 };
int arr2[] = { 10,20,30 };
list<int> l1(arr, arr + 6);
list<int> l2(arr2, arr2 + 3);
for (auto i : l1) cout << i << " "; //before transfer
cout << endl;
for (auto i : l2) cout << i << " ";
cout << endl;
cout << endl;
list<int>::iterator it = l1.begin();
+ + it;
l1. splice(it, l2);
for (auto i : l1) cout << i << " "; //after transfer
cout << endl;
for (auto i : l2) cout << i << " ";
cout << endl;
return 0;
}
remove
remove is essentially find + erase, which is convenient for our actual use.
int main()
{
int arr[] = { 1,2,3,4,5,6 };
list<int> l1(arr, arr + 6);
for (auto i : l1) cout << i << " "; //before deletion
cout << endl;
l1. remove(5);
for (auto i : l1) cout << i << " "; //after deletion
cout << endl;
return 0;
}
Merge
Using merge, we canmerge two ordered linked lists, the actual operation is similar to merge sort.
int main()
{
int arr[] = { 1,2,3,4,5,6 };
int arr2[] = { 10,20,30 };
list<int> l1(arr, arr + 6);
list<int> l2(arr2, arr2 + 3);
for (auto i : l1) cout << i << " "; //before merging
cout << endl;
for (auto i : l2) cout << i << " ";
cout << endl;
cout << endl;
l1. merge(l2);
for (auto i : l1) cout << i << " "; //after merging
cout << endl;
for (auto i : l2) cout << i << " ";
cout << endl;
return 0;
}
Deduplication
Using this function can remove duplicate elements in the linked list, but the premise is that the linked list must be ordered.
int main()
{
vector<int> v = { 1,1,1,2,3,3,4,4,5 };
list<int> l1(v.begin(),v.end());
for (auto i : l1) cout << i << " "; // before deduplication
cout << endl;
cout << endl;
l1. unique();
for (auto i : l1) cout << i << " "; //After deduplication
cout << endl;
return 0;
}
Reverse
This function can reverse the linked list.
int main()
{
vector<int> v = { 1,2,3,4,5,6 };
list<int> l1(v.begin(), v.end());
for (auto i : l1) cout << i << " "; //before inversion
cout << endl;
cout << endl;
l1. reverse();
for (auto i : l1) cout << i << " "; //after inversion
cout << endl;
return 0;
}
Sort
list cannot use the sort in the algorithm library, because its iterator is not a random access iterator, so a sort is overloaded in the library.
But in fact, the efficiency of this function is not high, we can write a code to test it.
int main()
{
srand((size_t)time(NULL));
int n = 1000000;
vector<int> v;
list<int> l;
for (int i = 0; i < n; i ++ )
{
int val = rand() % 100;
v.push_back(val);
l.push_back(val);
}
int begin1 = clock(); //vector starts sorting
sort(v.begin(), v.end());
int end1 = clock(); //vector end sorting
int begin2 = clock(); //list starts sorting
l. sort();
int end2 = clock(); //list end sorting
cout << "vector: " << end1 - begin1 << endl;
cout << "list: " << end2 - begin2 << endl;
return 0;
}
When n is 1000000, the gap is very obvious.
After that, we will copy a list into the vector and sort it to see the final result.
int main()
{
srand((size_t)time(NULL));
int n = 1000000;
list<int> l1;
list<int> l2;
for (int i = 0; i < n; i ++ )
{
int val = rand() % 100;
l1.push_back(val);
l2.push_back(val);
}
int begin1 = clock();
vector<int> v;
for (auto it : l1) v.push_back(it); //Copy list into vector
sort(v.begin(), v.end()); //sort again
int end1 = clock();
int begin2 = clock();
l2. sort();
int end2 = clock();
cout << "l1: " << end1 - begin1 << endl;
cout << "l2: " << end2 - begin2 << endl;
return 0;
}
It can be seen that the gap is still very large, so in future use, Unless the value is smallIt can be used directly for the convenience of the picture, otherwise it is not as good as Copy it to vector and sort it.
Okay, this is the end of today’s list. If this article is useful to you, please leave your three consecutive comments.