Introduction and use of list

【 Write it at the front 】

At the end of the course list, Everyone to STL The knowledge of iterators in will be further improved .list Although not much , But there are many classic things at the bottom of it , Especially its iterator .list The structure of should not be a problem for us , Because in 《 data structure 》 We have already known the linked list , Its structure is a leading two-way circular linked list , We've done it before .

about list No, reserve and resize, Because its bottom layer is not a continuous space , It uses one application and one , Release one without one . either operator[], Because it doesn't support random access . At the same time, it has a head plug 、 Head deletion 、 Tail insertion 、 Deletion at the end 、 Insertion at any position 、 Delete . because list It's a two-way circular list .

With the front string and vector The bedding of , We are here for list You can use it after a while , Because they are similar , The focus is mainly on list Deep analysis and Simulation Implementation of .

In fact, strictly speaking C++ Of list There are two ：

1. <list> It's a two-way circular list , This is what we need to learn in this chapter
2. <forward_list> It's a single chain table , It is C++11 The increase in , There are not many usage scenarios , To view the document , As you can see, it does not support tail insertion 、 Deletion at the end , Because the efficiency of single linked list is very low . And insert it anywhere 、 The deletion is after the current position , Because you have to find the previous one before the current position , Also a O(N) The implementation of the . The only advantage of a single linked list over a two-way linked list is that there is less than one pointer per node .
   

One 、list The introduction and use of

list Introduction to

list Documentation of

1. list Yes, it can be in the constant range O(1) A sequential container that can be inserted and deleted anywhere , And the container can iterate back and forth
2. list The bottom layer of is a two-way linked list structure , Each element in a two-way linked list is stored in independent nodes that are not related to each other , In a node, point to its previous element and the next element through a pointer
3. list And forward_list Very similar ： The main difference is forward_list It's a single chain table , Can only iterate forward , Has made it simpler and more efficient
4. Compared with other sequential containers (array,vector,deque),list It is usually inserted at any position 、 Remove the element Better execution efficiency
5. Compared with other containers ,list and forward_list The biggest drawback is that random access to any location is not supported , such as ： To visit list Of the 6 Elements , Must be from a known location ( Like the head or tail ) Iterate to this location , Iterating at this location requires a linear time overhead ;list Some extra space is needed , To save the associated information of each node ( For large elements with smaller storage types list This may be an important factor )

list Use

1、list Construction

constructor	Interface specification
list()	Construct empty list
list(size_type n, const value_type& val = value_type())	structure list Contained in the n The values are val The elements of
list(const list& x)	copy constructor
list(InputIterator first, InputIterator last)	use (first, last) The elements in the interval are constructed list

#include<iostream>#include<vector>#include<list>using namespace std;namespace std{	void test_list1()	{		list<int> lt1;		list<int> lt2(10, 5);		list<int> lt3(lt2.begin(), lt2.end());		// It also supports the use of iterator intervals of other containers to construct , Because it's a template , And it can support the following writing 		vector<int> v = { 1, 2, 3, 4, 5 };		list<int> lt4(v.begin(), v.end());			list<int> lt5(lt4);	}}int main(){	std::test_list1();	return 0;	}

2、list iterator Use

iterator	Interface specification
begin + end	Returns the iterator of the first element + Returns the iterator at the next position of the last element
rbegin + rend	Returns the... Of the first element reserve_iterator, namely end Location , Returns the next position of the last element reverse_iterator, namely begin Location

#include<iostream>#include<vector>#include<list>using namespace std;namespace std{	void test_list1()	{		vector<int> v = { 1, 2, 3, 4, 5 };		list<int> lt(v.begin(), v.end());				list<int>::iterator it1 = lt.begin();		// Note that for string and vector We can use less than or not equal to as the judgment condition , however list Can only use not equal as the judgment condition , At this time, because of the continuity of space in different containers 		while(it1 != lt.end())		{			cout << *it1 << " ";			++it1;			}		cout << endl;				list<int>::reverse_iterator it2 = lt.rbegin();		while(it2 != lt.rend())		{			cout << *it2 << " ";			++it2;			}		cout << endl;			//list There is no longer support for operator[]		for(auto e : lt)		{			cout << e << " ";		}		cout << endl;	}}int main(){	std::test_list1();	return 0;	}

3、list capacity

capacity	Interface specification
empty	testing list Is it empty , Is to return true, Otherwise return to false
size	return list Number of valid nodes in

4、list element access

element access	Interface specification
front	return list The reference to the median of the first node of
back	return list Reference to the value in the last node of the

5、list modifiers

modifiers	Interface specification
push_front	stay list The value inserted before the first element is val The elements of
pop_front	Delete list The first element in
push_back	stay list The tail insertion value is val The elements of
pop_back	Delete list The last element in
insert	stay list position The insertion value in position is val The elements of
erase	Delete list position The element of location
swap	Two exchanges list The elements in
clear	Empty list Valid elements in

#include<iostream>#include<algorithm>#include<vector>#include<list>#include<functional>#include<time.h>using namespace std;namespace std{	void test_list1()	{		list<int> lt;		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);			lt.push_front(10);		lt.push_front(20);		lt.push_front(30);		lt.push_front(40);			for(auto e : lt)		{			cout << e << " ";			}		cout << endl;			lt.pop_back();		lt.pop_back();		lt.pop_back();		lt.pop_back();				lt.pop_front();		lt.pop_front();		lt.pop_front();		lt.pop_front();		//lt.pop_front();//err, Pay attention to delete... In the header 、 When deleting the tail, make sure list There's data in there , Otherwise, an assertion error will be reported here 				for(auto e : lt)		{			cout << e << " ";			}	}	void test_list2()	{		list<int> lt;		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);				//list It doesn't provide find, So here we use algorithm Inside 		list<int>::iterator pos = find(lt.begin(), lt.end(), 2);		if(pos != lt.end())		{			lt.insert(pos, 20);		}		for (auto e : lt)		{			cout << e << " ";		}		cout << endl;				//clear It does not clear the head node , Here we can continue push_back		lt.clear();		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);		for(auto e : lt)		{			cout << e << " ";			}		cout << endl;	}	void test_list3()	{		list<int> lt1;		lt1.push_back(1);		lt1.push_back(2);		list<int> lt2;		lt2.push_back(2);		lt2.push_back(1);					list<int> lt3;		lt3.push_back(5);		lt3.push_back(1);		lt3.push_back(3);		lt3.push_back(3);		// about swap, stay C++98 It is recommended to use... In the container , It is not recommended to use . They have the same effect , But efficiency is different , See the following description for details 		lt1.swap(lt2);		//swap(lt1, lt2);		for(auto e : lt1)		{			cout << e << " ";			}		cout << endl;		for(auto e : lt2)		{			cout << e << " ";			}		cout << endl;			// Note that all sorts satisfy ,> It's in descending order ,< It's in ascending order , The default here is ascending 		// This is also a class template , It's an imitation function , Location head <functional> Later we will realize ,sort Location head <algorithm>		/*greater<int> g; lt3.sort(g);*/		lt3.sort(greater<int>());// ditto , It can be written directly as an anonymous object 		for(auto e : lt3)		{			cout << e << " ";			}		cout << endl;		//unique The function of is to remove the weight , Location head <algorithm>, The premise of de duplication is sorting , Ascending or descending , If you don't sort, it only goes to the adjacent data 		lt3.unique();		for(auto e : lt3)		{			cout << e << " ";			}		cout << endl;				//erase It needs to be done first find, and remove You can delete , Delete all if you have , If you don't, don't delete it , Location head <algorithm>		lt3.remove(3);		for (auto e : lt3)		{			cout << e << " ";		}		cout << endl;			//reverse The function of is reverse , The inverse of the leading two-way circular linked list is much simpler than the single linked list , Location head <algorithm>		lt3.reverse();		for (auto e : lt3)		{			cout << e << " ";		}		cout << endl;		//merge Its function is to merge 		//splice Its function is to transfer , It transfers nodes, not data , It can only be used in very special scenes , We'll learn more about LRU You may come into contact with 	}	void test_OP()	{		srand(time(0));		const int N = 10000;		list<int> lt;		vector<int> v;				v.resize(N);		for (int i = 0; i < N; i++)		{			v[i] = rand();			lt.push_back(v[i]);		}		int begin1 = clock();		sort(v.begin(), v.end());//vector Using the algorithm , Its bottom layer uses the three digit middle method of fast row 		int end1 = clock();		int begin2 = clock();		lt.sort();//list Use the... In the container 		//sort(lt.begin(), lt.end());//err, The essence sort Will subtract with two iterators , and list The iterator of does not support subtraction 		int end2 = clock();					cout << "vector sort：" << end1 - begin1 << endl;		cout << "list sort：" << end2 - begin2 << endl;	}}int main(){	std::test_list1();	std::test_list2();	std::test_list3();	std::test_OP();	return 0;	}

explain

1. List item

   Why? C++98 It is recommended to use... In their respective containers swap, It is not recommended to use swap

   As you can see in the algorithm swap Of C++98 The implementation of the , Whether it's string、vector、list Using it will involve deep copy problems , And the deep copy here is very expensive , Need a deep copy 3 Time —— When lt1 and lt2 In exchange for , Here will be lt1 Make a copy of c, And then put lt2 Assigned to lt1,c Assigned to lt2, Complete the exchange .

   And if it's in a container swap, Need to swap lt1 and lt2, Just exchange the header pointer . The assumption is vector, Just put lt1 and lt2 Corresponding _start、_finish、_endofstorage In exchange . Compared with... In the algorithm C++98 Inside swap, It can be considered that there is no cost .

   So , Why don't most of us write data structures in our future work , And learn 《 data structure 》 This subject . Because if you don't implement the data structure yourself , You don't know the structure of the linked list , Let me tell you this 2 individual swap There are deep copy differences , You may not understand , I haven't learned 《 data structure 》 People can never understand why top-k It seems that the efficiency is much higher when the problem is piled up . So we go from C Language has come all the way , Various simulation implementations ( Small ones strstr、strcmp; The big one has a binary tree 、list), Not to make better wheels , But can better understand and use .
   

2. List item

   Iterators supplement

   Classification of container iterators ：

   a) The perspective of using functions can be divided into ,( positive 、 reverse ) + const

   b) The angle of container substructure can be divided into , A one-way 、 two-way 、 Random

     For example, a single linked list iterator 、 Hash table iterators are one-way , The characteristic is that it can ++, You can't --; Bidirectional linked list iterator 、map Iterators are bidirectional , The characteristic is that it can ++、–;string、vector、deque Iterators are random iterators , The characteristic is that it can ++、–、+、-, Generally, the bottom layer of random iterator is a continuous space .

   You can see in the algorithm sort、reverse Statement of , Its template parameters are not named T, Neither iterator, The naming of template parameters can be arbitrary , But its name has meaning . For example, you need to use sort This algorithm , You're going to use a random iterator ; Do you want us to use reverse This algorithm , You're going to use a two-way iterator . Random iterators can also be used reverse, Because the random iterator is a bidirectional iterator , Because it meets all the functions of bidirectional iterators ; Empathy , Bidirectional iterators are also unidirectional iterators 、 Random iterators are also one-way iterators . This means that the command of the template parameter here is a one-way iterator , Then your container can be one-way 、 two-way 、 Random ; The command for template parameters is a bidirectional iterator , Then your container can be bidirectional 、 Random ; The command for template parameters is random iterator , Then your container can be random . I learned inheritance later , You can know that they meet an inheritance relationship .
   
   So here we need to understand a relationship
   

6、list Iterator failure

As I said before , Here, we can temporarily understand the iterator as a pointer , The iterator fails, that is, the node pointed to by the iterator is invalid , That is, the node is deleted . because list The underlying structure of is a two-way circular linked list of leading nodes , So in list When inserting in, it will not lead to list The iterator of is invalid , It will be invalid only when deleted , And the only thing that fails is the iterator pointing to the deleted node , Other iterators will not be affected .

#include<iostream>#include<algorithm>#include<list>using namespace std;namespace std{	void test_list1()	{		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);		if(pos != lt.end())		{			// It won't fail 			lt.insert(pos, 45);		}		for(auto e : lt)		{			cout << e << " ";			}		cout << endl;	}	void test_list2()	{		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);		if(pos != lt.end())		{			// It will fail , You can reassign iterators pos			lt.erase(pos);			//pos = lt.erase(pos);//ok		}		cout << *pos << endl;		cout << endl;	}}int main(){	std::test_list1();	std::test_list2();	return 0;	}

explain