Use of list

One 、list Introduction to

1.1 list Introduction to

1. list You can use O(1) Time complexity of A sequential container that can be inserted and deleted anywhere , And the container can iterate back and forth .
2. list Of The bottom layer 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 、 Removing elements is more efficient .
5. Compared with other sequential containers ,list and forward_list The biggest flaw is 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 )

Two 、list Use

2.1 list Constructor for

Constructors	Interface specification
list()	Empty structure
list (size_type n, const value_type& val = value_type())	The initialization of the list Contained in the n individual val value
list (const list& x)	copy constructor
list (InputIterator first, InputIterator last)	Using iterator intervals [first,last) structure list

void test_list1()
{
    
	//  Empty structure 
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	for (int e: l1)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  The initialization of the list Contained in the n individual val value 
	list<int> l2(4,10);
	for (int e : l2)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  copy constructor 
	list<int> l3(l1);
	for (int e : l3)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  Using iterator intervals [first,last) structure list
	list<int> l4(l3.begin(), l3.end());
	for (int e : l4)
	{
    
		cout << e << " ";
	}
}

2.2 list The use of iterators

Function declaration	Interface specification
begin+end	Returns the iterator of the first element + return The iterator at the next position of the last element
rbegin+rend	return end Location + return begin Location

//  just \ reverse iterator 
void test_list2()
{
    
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	//  Forward iterator 
	list<int>::iterator it = lt.begin();
	while (it!=lt.end())
	{
    
		cout << *it << " ";
		++it;
	}
	cout << endl;
	
	//  reverse iterator 
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit!=lt.rend())
	{
    
		cout << *rit << " ";
		++rit;
	}
}

2.3 list Related capacity size related function

Function declaration	Interface specification
empty	testing list Is it empty , Is to return true, No return false
size	return list Number of valid nodes in

void test_list3()
{
    
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);

	cout << l1.size() << endl; // 4
	cout << l1.empty() << endl;// 0
}

2.4 list Data access related functions

Function declaration	Interface specification
front	return list Reference to the first node value in
back	return list Reference to the last node value in

void test_list4()
{
    
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);

	cout << l1.front() << endl; // 1
	cout << l1.back() << endl;  // 4
}

2.5 list Data adjustment related functions

Function declaration	Interface specification
push_front	Insert element before first element
pop_front	Delete first element
push_back	Tail insertion
pop_back	Deletion at the end
insert	stay pos Position insertion value
erase	Delete pos The value of the location
swap	Two exchanges list The value in
clear	Empty list Valid elements in

void test_list5()
{
    
	list<int> l;
	l.push_back(1);
	l.push_front(2);
	
	list<int>::iterator it = l.begin();
	++it;
	l.insert(it, 20);
	
	for (int e : l)
	{
    
		cout << e << " ";
	}
	cout << endl;
	cout << "------" << endl;
	l.clear();
	for (int e : l)
	{
    
		cout << e << " ";
	}
}

2.6 list Other function operations in

Function declaration	Interface specification
sort	Sort
reverse	Inversion
unique	duplicate removal ( Generally, you need to sort before de duplication )
remove	Delete a given value

void test_list6()
{
    
	list<int> l1;
	l1.push_back(1);
	l1.push_back(7);
	l1.push_back(3);
	l1.push_back(3);
	l1.push_back(3);
	l1.push_back(4);

	//  Sort 
	l1.sort();
	for (int e : l1)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  Inversion 
	l1.reverse();
	for (int e : l1)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  duplicate removal 
	l1.unique();
	for (int e : l1)
	{
    
		cout << e << " ";
	}
	cout << endl;

	//  Delete a given value 
	l1.remove(7);
	for (int e : l1)
	{
    
		cout << e << " ";
	}
	cout << endl;
}