Wiki

list container

Updated 2023-10-05About 11 min read

Existing English translations were reused. 2 current source blocks remain in Simplified Chinese, without triggering paid translation.

1.list container

1.1.Basic concepts of list

**Function:** Store data in a chained manner

A linked list(list) is a non-contiguous storage structure in terms of physical storage units, and the logical order of data elements is implemented through pointer links in the linked list.

Composition of a linked list: A linked list consists of a series ofnodes.

结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

A linked list in the STL is a doubly circular linked list

说明: 2015-11-15_225145

Because the storage method of a linked list is not contiguous memory space, the iterators in a list only support forward and backward movement, belonging tobidirectional iterators

Advantages of list:

Dynamic storage allocation is used, which does not cause memory waste or overflow.
Insertion and deletion operations on a linked list are very convenient; only pointers need to be modified, without moving a large number of elements.

Disadvantages of list:

Linked lists are flexible, but they incur relatively large extra overhead in space (the pointer field) and time (traversal).

An important property of list is that neither insertion nor deletion operations invalidate existing list iterators, which does not hold for vector.

Summary: In STL,List and vector are the two most commonly used containerseach with its own advantages and disadvantages.

1.2.list constructor

Function description:

Create a list container

Function prototype:

list<T> lst; // list is implemented as a template class, with the default construction form of the object:
list(beg,end); // The constructor copies the elements in the range [beg, end) to itself.
list(n,elem); // The constructor copies n copies of elem to itself.
list(const list &lst); // Copy constructor.

Example:

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int>& L) {

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

void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	printList(L1);

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

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

	list<int>L4(10, 1000);
	printList(L4);
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

	test01();


	// 返回 0 表示程序正常结束。
	return 0;
}

Operation result:

10 20 30 40
10 20 30 40
10 20 30 40
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

Summary: The construction methods of list are the same as those of several other commonly used STL containers; proficiency can be achieved through practice.

1.3.list assignment and swapping

Function description:

Assign values to a list container, and swap list containers

Function prototype:

assign(beg, end); // Copy and assign the data in the interval [beg, end) to itself.
assign(n, elem); // Copy and assign n elements of elem to itself.
list& operator=(const list &lst); // Overload the assignment operator
swap(lst); // Swap the elements of lst with itself.

Example:

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int>& L) {

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

//赋值和交换
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);

	//赋值
	list<int>L2;
	L2 = L1;
	printList(L2);

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

	list<int>L4;
	L4.assign(10, 100);
	printList(L4);

}

//交换
void test02()
{

	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	list<int>L2;
	L2.assign(10, 100);

	cout << "交换前： " << endl;
	printList(L1);
	printList(L2);

	cout << endl;

	L1.swap(L2);

	cout << "交换后： " << endl;
	printList(L1);
	printList(L2);

}

int main() {

	//test01();

	test02();


	return 0;
}

Operation result:

交换前：
10 20 30 40
100 100 100 100 100 100 100 100 100 100

交换后：
100 100 100 100 100 100 100 100 100 100
10 20 30 40

Summary: It is sufficient to be able to flexibly apply list assignment and swapping operations.

1.4.list size operations

Function description:

Operate on the size of the list container

Function prototype:

size(); //Return 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 positions with the default value.

//If the container becomes shorter, the elements beyond the container length at the end are deleted.
resize(num, elem); //Reassign the length of the container to num. If the container becomes longer, fill the new positions with the value elem.
```
  	 	 						    //如果容器变短，则末尾超出容器长度的元素被删除。
```

Example:

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int>& L) {

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

//大小操作
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	if (L1.empty())
	{
		cout << "L1为空" << endl;
	}
	else
	{
		cout << "L1不为空" << endl;
		cout << "L1的大小为： " << L1.size() << endl;
	}

	//重新指定大小
	L1.resize(10);
	printList(L1);

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

int main() {

	test01();


	return 0;
}

Operation result:

L1不为空
L1的大小为： 4
10 20 30 40 0 0 0 0 0 0
10 20

Summary:

Determine whether it is empty --- empty
Return the number of elements --- size
Re-specify the count --- resize

1.5.list insertion and deletion

Function description:

Insert and delete data in a list container

Function prototype:

push_back(elem);//Add an element at the end of the container
pop_back();//Remove 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 at position pos, and return the position of the new data.
insert(pos,n,elem);//Insert n elem data at position pos, with no return value.
insert(pos,beg,end);//Insert the data in the range [beg,end) at position pos, with no return value.
clear();//Remove all data from the container
erase(beg,end);//Delete the data in the range [beg,end), and return the position of the next data.
erase(pos);//Delete the data at position pos, and return the position of the next data.
remove(elem);//Delete all elements in the container that match the value elem.

Example:

#include <iostream>
#include <list>

using namespace std;

void printList(const list<int>& L) {

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

//插入和删除
void test01()
{
	list<int> L;
	//尾插
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	//头插
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);

	printList(L);

	//尾删
	L.pop_back();
	printList(L);

	//头删
	L.pop_front();
	printList(L);

	//插入
	list<int>::iterator it = L.begin();
	L.insert(++it, 1000);
	printList(L);

	//删除
	it = L.begin();
	L.erase(++it);
	printList(L);

	//移除
	L.push_back(10000);
	L.push_back(10000);
	L.push_back(10000);
	printList(L);
	L.remove(10000);
	printList(L);
    
    //清空
	L.clear();
	printList(L);
}

int main() {

	test01();


	return 0;
}

Operation result:

300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 1000 100 10 20
200 100 10 20
200 100 10 20 10000 10000 10000
200 100 10 20

Summary:

tail insertion --- push_back
tail deletion --- pop_back
head insertion --- push_front
head deletion --- pop_front
insert --- insert
delete --- erase
remove --- remove
clear --- clear

1.6.list data access

Function description:

Access data in a list container

Function prototype:

front(); // Return the first element.
back(); // Return the last element.

Example:

#include <iostream>
#include <list>

using namespace std;

//数据存取
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	
	//cout << L1.at(0) << endl;//错误 不支持at访问数据
	//cout << L1[0] << endl; //错误  不支持[]方式访问数据
	cout << "第一个元素为： " << L1.front() << endl;
	cout << "最后一个元素为： " << L1.back() << endl;

	//list容器的迭代器是双向迭代器，不支持随机访问
	list<int>::iterator it = L1.begin();
	//it = it + 1;//错误，不可以跳跃访问，即使是+1
}

int main() {

	test01();


	return 0;
}

Operation result:

第一个元素为： 10
最后一个元素为： 40

Summary:

list容器中不可以通过[]或者at方式访问数据
返回第一个元素 --- front
返回最后一个元素 --- back

1.7.List reversal and sorting

Function description:

Reverse the elements in the container and sort the data in the container.

Function prototype:

reverse(); // Reverse linked list
sort(); // Sort linked list

Example:

#include <iostream>

using namespace std;

void printList(const list<int>& L) {

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

bool myCompare(int val1 , int val2)
{
	return val1 > val2;
}

//反转和排序
void test01()
{
	list<int> L;
	L.push_back(90);
	L.push_back(30);
	L.push_back(20);
	L.push_back(70);
	printList(L);

	//反转容器的元素
	L.reverse();
	printList(L);

	//排序
	L.sort(); //默认的排序规则 从小到大
	printList(L);

	L.sort(myCompare); //指定规则，从大到小
	printList(L);
}

int main() {

	test01();


	return 0;
}

Operation result:

90 30 20 70
70 20 30 90
20 30 70 90
90 70 30 20

Summary:

reverse --- reverse
sort --- sort (member function)

1.8.Sorting example

Case description: Sort the custom data type Person, where the attributes in Person include name, age, and height

Sorting rules: sort in ascending order by age, and if ages are the same, sort in descending order by height

Example:

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Person {
public:
	Person(string name, int age , int height) {
		m_Name = name;
		m_Age = age;
		m_Height = height;
	}

public:
	string m_Name;  //姓名
	int m_Age;      //年龄
	int m_Height;   //身高
};

bool ComparePerson(Person& p1, Person& p2) {

	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height  > p2.m_Height;
	}
	else
	{
		return  p1.m_Age < p2.m_Age;
	}

}

void test01() {

	list<Person> L;

	Person p1("刘备", 35 , 175);
	Person p2("曹操", 45 , 180);
	Person p3("孙权", 40 , 170);
	Person p4("赵云", 25 , 190);
	Person p5("张飞", 35 , 160);
	Person p6("关羽", 35 , 200);

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

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}

	cout << "---------------------------------" << endl;
	L.sort(ComparePerson); //排序

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
		cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age 
              << " 身高： " << it->m_Height << endl;
	}
}

int main() {

	test01();


	return 0;
}

Operation result:

姓名： 刘备 年龄： 35 身高： 175
姓名： 曹操 年龄： 45 身高： 180
姓名： 孙权 年龄： 40 身高： 170
姓名： 赵云 年龄： 25 身高： 190
姓名： 张飞 年龄： 35 身高： 160
姓名： 关羽 年龄： 35 身高： 200
---------------------------------
姓名： 赵云 年龄： 25 身高： 190
姓名： 关羽 年龄： 35 身高： 200
姓名： 刘备 年龄： 35 身高： 175
姓名： 张飞 年龄： 35 身高： 160
姓名： 孙权 年龄： 40 身高： 170
姓名： 曹操 年龄： 45 身高： 180

Summary:

For custom data types, a sorting rule must be specified; otherwise, the compiler does not know how to sort them.
Advanced sorting merely applies an additional logical rule on top of the sorting rule, and it is not complex.