1. Basic concept of list container

(1) The list container is actually a linked list, which is different from the vector container. The list container stores the data chain through the pointer;

(2) The linked list is composed of a series of nodes. Each node is composed of the data field for storing data and the pointer field for storing the address of the next data;

The knowledge of linked list is in the previous article** Linked storage structure of linear list (linked list).**

The linked list in the list container is a two-way circular linked list, as shown in the following figure;

(1) Advantages and disadvantages of list

excellent

1 . Dynamic storage allocation is adopted, which will not cause memory waste and overflow;
2 . It is very convenient to insert and delete the linked list. You can modify the pointer without moving a large number of elements.

lack

1 . The access of list linked list does not support random access. It can only be accessed by iterator, and the operation is complex
2 . The linked list is flexible, but the additional cost of space (pointer field) and time (traversal) is large. The traversal speed is not as fast as the array, and the occupied space is larger than the array.
3 . list has an important property. Neither insert nor delete will invalidate the original list iterator, which is not true in vector.

Well, that's all for theoretical knowledge. We mainly rely on practical examples to understand

2. Create a list container

Constructor prototype: (basically the same as vector)

list<T> lst; //list default construction form:
list(begin,end); //The constructor copies the elements in the [begin, end) interval to itself.
list(n,e); //The constructor assigns n e to itself.
list(const list &lst); //copy constructor 

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

void showList01(const list<int>& L) //The only way to print the data in the list container is because the list container can only be accessed through the iterator
{

	for (list<int>::const_iterator p = L.begin(); p != L.end(); p++) {
		cout << *p << " ";
	}
	cout << endl;
}
void testit()
{
	list<int>L1;
	for (int i = 3; i < 50; i += 10)
	{
		L1.push_back(i);
	}
	

	showList01(L1);

	list<int>L2(L1.begin(), L1.end());
	showList01(L2);

	list<int>L3(L2);
	showList01(L3);

	list<int>L4(10, 666);
	showList01(L4);
}

int main() {

	testit();

	system("pause");

	return 0;
}

Operation results

3.list container assignment and exchange

Interface function prototype (basically the same as vector)

assign(begin, end); //Assign the data in the [begin, end) interval to the container.
assign(n, t); //Assign n t copies to itself.
list& operator=(const list &lst); //Overloaded equal sign operator
swap(lst); //Swap lst with its own elements.

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

void showList01(const list<int>& L) //The only way to print the data in the list container is because the list container can only be accessed through the iterator
{

	for (list<int>::const_iterator p = L.begin(); p != L.end(); p++) {
		cout << *p << " ";
	}
	cout << endl;
}

//Assignment and exchange
void testit01()
{
	list<int>L1;
	for (int i = 3; i < 50; i += 10)
	{
		L1.push_back(i);
	}
	showList01(L1);

	//assignment
	list<int>L2;
	L2 = L1;
	showList01(L2);

	list<int>L3;
	L3.assign(L2.begin(), L2.end());
	showList01(L3);

	list<int>L4;
	L4.assign(10, 33);
	showList01(L4);

}

//exchange
void testit02()
{

	list<int>L1;
	for (int i = 3; i < 50; i += 10)
	{
		L1.push_back(i);
	}
	list<int>L2;
	L2.assign(10, 66);

	cout << "Before exchange: " << endl;
	showList01(L1);
	showList01(L2);

	cout << endl;

	L1.swap(L2);

	cout << "After exchange: " << endl;
	showList01(L1);
	showList01(L2);

}

int main() {

	testit01();

	cout << "***********Next test case**********" << endl;

	testit02();

	system("pause");

	return 0;
}

Operation results

4.list size operation

Interface function prototype (basically the same as vector)

size(); //Returns the number of elements in the container

empty(); //Determine whether the container is empty

resize(num); //Reassign the length of the container to num. if the container becomes longer, fill the new location with the default value.

​ //If the container becomes shorter, the element whose end exceeds the length of the container is deleted.

resize(num, elem); //Reassign the length of the container to num. if the container becomes longer, fill the new position with elem value. If the container becomes shorter, delete the excess

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

void showList01(const list<int>& L) //The only way to print the data in the list container is because the list container can only be accessed through the iterator
{

	for (list<int>::const_iterator p = L.begin(); p != L.end(); p++) {
		cout << *p << " ";
	}
	cout << endl;
}

//Size operation
void testit01()
{
	list<int>L1;
	for (int i = 3; i < 50; i += 10)
	{
		L1.push_back(i);
	}
	showList01(L1);

	if (L1.empty())
	{
		cout << "L1 Empty" << endl;
	}
	else
	{
		cout << "L1 Not empty" << endl;
		cout << "L1 The size of the is: " << L1.size() << endl;
	}

	//Reassign size
	L1.resize(10);
	showList01(L1);

	L1.resize(2);
	showList01(L1);
}

int main() {

	testit01();

	system("pause");

	return 0;
}

Operation results

5.list insertion and deletion

Interface function prototype (different from vector)

push_back(elem);//Add an element at the end of the container
pop_back();//Delete the last element in the container
push_front(elem);//Insert an element at the beginning of the container
pop_front();//Remove the first element from the beginning of the container
insert(pos,elem);//Insert a copy of the elem element in the pos position to return the location of the new data.
//pos is the iterator position
insert(pos,n,elem);//Insert n elem data in pos position, no return value.
//pos is the iterator position
insert(pos,beg,end);//Insert the data in the [beg,end) interval at the pos position, and there is no return value.
//pos is the iterator position
clear();//Remove all data from the container
erase(beg,end);//Delete the data in the [beg,end) interval and return the position of the next data.
//Beg and end are iterators. You can also change the interval through the iterator + +
erase(pos);//Delete the data in pos position and return the position of the next data.
remove(elem);//Delete all elements in the container that match the elem value.

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

void showList01(const list<int>& L) //The only way to print the data in the list container is because the list container can only be accessed through the iterator
{

	for (list<int>::const_iterator p = L.begin(); p != L.end(); p++) {
		cout << *p << " ";
	}
	cout << endl;
}


//Insert and delete
void testit01()
{
	list<int> L;
	//Tail insertion fa
	L.push_back(11);
	L.push_back(22);
	L.push_back(33);
	//Head insert af
	L.push_front(150);
	L.push_front(250);
	L.push_front(350);

	showList01(L);

	//Tail deletion fa
	L.pop_back();
	showList01(L);

	//Header deletion fa
	L.pop_front();
	showList01(L);

	//Insert fa
	list<int>::iterator p = L.begin();
	L.insert(++p, 888);
	showList01(L);

	//Delete af
	p = L.begin();
	L.erase(++p);
	showList01(L);

	//Remove fa
	L.push_back(9999);
	L.push_back(9999);
	L.push_back(999);
	showList01(L);
	L.remove(9999);
	showList01(L);

	//Empty fa
	L.clear();
	showList01(L);
}

int main() {

	testit01();

	system("pause");

	return 0;
}

Operation results

6.list data access

Interface function prototype:

front()//Return first data
back()//Return the second data
//Can only be accessed through iterators

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

//data access 
void testit01()
{
	list<int>L1;
	for (int i = 3; i < 50; i += 10)
	{
		L1.push_back(i);
	}

	//list does not support at access to data and [] access to data
	//Can only be accessed through iterators
	cout << "The first element is: " << L1.front() << endl;
	cout << "The last element is: " << L1.back() << endl;

	//The iterator of the list container is a bidirectional iterator and does not support random access

	list<int>::iterator it = L1.begin();

	//it = it + 1;// Error, cannot skip access, even + 1

	it++;
	cout << "The second element is: " << *it << endl;
	it++;
	cout << "The third element is: " << *it << endl;
}

int main() {

	testit01();

	system("pause");

	return 0;
}

7.list inversion and sorting

Interface function prototype

reverse(); //Reverse linked list
sort(); //Linked list sorting
//Neither of them is an algorithm function in STL, but an interface function in the list container, and their usage is not the same

Example

#include<iostream>
using namespace std;
#Include < list > / / the container in C + + must contain the corresponding header file before use

void showList01(const list<int>& L) //The only way to print the data in the list container is because the list container can only be accessed through the iterator
{

	for (list<int>::const_iterator p = L.begin(); p != L.end(); p++) {
		cout << *p << " ";
	}
	cout << endl;
}


bool My_sortway(int a, int b)
{
	return a > b;
}

//Reverse and sort
void test01()
{
	list<int> L;
	L.push_back(99);
	L.push_back(33);
	L.push_back(22);
	L.push_back(77);
	showList01(L);

	//Invert the elements of the container
	L.reverse();
	cout << "After reversal:";
	showList01(L);

	//sort
	L.sort(); //The default collation is from small to large
	cout << "After sorting from small to large:";
	showList01(L);

	L.sort(My_sortway); //Specify rules, from large to small
	cout << "After sorting from large to small:";
	showList01(L);
}

int main() {

	test01();

	system("pause");

	return 0;
}

Operation results

list actual combat (student achievement management system)

Title Requirements:
1 . Make a student transcript management system
2 . Sort the student user-defined data types. The attributes in student include name, age, Chinese score, math score and English score
Sorting rule: descending by total score sum. If the total score sum is the same, descending by Chinese score

source code

#include<iostream>
using namespace std;
#include <list>
#include <string>

class Student {
public:
	Student(string name, int ch, int ma,int e) {
		m_Name = name;
		chinese = ch;
		math = ma;
		English = e;
		sum = ch + ma + e;
	}

public:
	string m_Name;  //full name
	int chinese;      //grade scores of Chinese
	int math;   //Mathematics achievement
	int English;//English achievement
	int sum;//Total score

};


bool ComparePerson(Student& p1, Student& p2)//Define sort sort from large to small
{

	if (p1.sum == p2.sum) {
		return p1.sum < p2.sum;
	}
	else
	{
		return  p1.chinese < p2.chinese;
	}

}

void test() {

	list<Student> k;

	Student p1("Du Wenfei", 88,77,95);
	Student p2("Du Weifen", 67,58,26);
	Student p3("Li Baba", 95,77,88);
	Student p4("Zhao Erdan",86,75,68);
	Student p5("Wang Xiaoniu", 86,46,86);
	Student p6("Zhang xiaoha",89,57,68);

	k.push_back(p1);
	k.push_back(p2);
	k.push_back(p3);
	k.push_back(p4);
	k.push_back(p5);
	k.push_back(p6);

	for (list<Student>::iterator it = k.begin(); it != k.end(); it++) {
		cout << "full name: " << it->m_Name << " chinese: " << it->chinese
			<< " mathematics: " << it->math << " English: " << it->English<< "  Total score: " << it->sum<<  endl;
	}

	cout << "---------------------------------" << endl;
	k.sort(ComparePerson); //sort
	cout << "After sorting" << endl;
	for (list<Student>::iterator it = k.begin(); it != k.end(); it++) {
		cout << "full name: " << it->m_Name << " chinese: " << it->chinese
			<< " mathematics: " << it->math << " English: " << it->English << "  Total score: " << it->sum << endl;
	}
}

int main() {

	test();

	system("pause");

	return 0;
}

Operation results