第 18.8 節
list 容器
0瀏覽次數0訪問次數--跳出率--平均停留
list container
A list is an ordered, mutable collection of items in programming, allowing duplicates and indexed access. It supports operations like adding, removing, and accessing elements by position.
Function: Chain storage of data.
Linked list is a non-contiguous storage structure in physical memory, where the logical order of data elements is achieved through pointer links within the list.
The composition of a linked list: a linked list consists of a series of nodes.
The composition of a node consists of two parts: one is the data field that stores data elements, and the other is the pointer field that stores the address of the next node.
The list in the STL is a doubly circular linked list.
Due to the non-contiguous memory storage of linked lists, iterators in a list only support moving forward and backward, making them bidirectional iterators.
Advantages of a list:
- Efficient for sequential access and iteration.
- Supports dynamic resizing (grows or shrinks as needed).
- Easy to insert or remove elements at any position (especially with linked lists).
- Provides a flexible way to store and manage collections of data.
- Uses dynamic memory allocation to prevent memory waste and overflow.
- Linked lists are very convenient for performing insertion and deletion operations, as modifying pointers is sufficient rather than needing to move a large number of elements.
Disadvantages of lists:
- Linked lists are flexible, but they come with extra overhead in space (pointer fields) and time (traversal).
An important property of list is that insert and delete operations do not invalidate existing list iterators, which is not the case with vector.
In summary, list and vector are the two most commonly used containers in STL, each with its own advantages and disadvantages.
list constructor
Description:
- Create a list container.
Function prototype:
list<T> lst;//list implemented using template classes; the default construction form of an object:list(beg,end);//The constructor copies the elements in the range [beg, end) to itself.list(n,elem);//The constructor copies n elements 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;
}
运行结果：
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 method for list is similar to other commonly used STL containers; familiarize yourself with it.
list assignment and swap
Description:
- Assigning values to a list container and swapping list containers.
Function prototype:
assign(beg, end);// Copies the data in the range [beg, end) to itself.assign(n, elem);// Copies n elements to itself.list& operator=(const list &lst);//overloading the equality operatorswap(lst);//Swap the list elements with themselves.
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;
}
运行结果：
交换前：
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: List assignment and swap operations can be used flexibly.
List Size Operations
Description:
- Perform operations on the size of the list container.
Function prototype:
size();// Returns the number of elements in the containerempty();//Determine whether the container is emptyresize(num);//Reassign the container's length to num; if the container lengthens, fill the new positions with default values.
// If the container becomes shorter, elements at the end that exceed the container length are deleted.
resize(num, elem);// Resize the container to length num, filling any new positions with the value of elem if the container expands.
// If the container becomes shorter, elements at the end that exceed the container length are deleted.
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;
}
运行结果：
L1不为空
L1的大小为： 4
10 20 30 40 0 0 0 0 0 0
10 20
Summary:
- Check if empty --- empty
- return element count --- size
- Reset the count --- resize
list insertion and deletion
Description:
- Performing data insertion and deletion on list containers
Function prototype:
- push_back(elem);//add an element at the end of the container
- pop_back();//Remove the last element from the container
- push_front(elem);// Inserts an element at the front of the container.
- pop_front(); // Remove the first element from the beginning of the container
- insert(pos,elem); // Inserts a copy of the element at the given position, returns the position of the new data.
- insert(pos,n,elem); // Inserts n copies of elem at position pos, with no return value.
- insert(pos, beg, end); // Insert data from the range [beg, end) at position pos; no return value.
- clear(); //Remove all data from the container
- erase(beg,end);//Removes elements in the range [beg,end) and returns the position of the next element.
- erase(pos);// Delete data at the specified position and return the position of the next data.
- Removes all elements from the container that match the value of 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;
}
运行结果：
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
- Pop back --- pop_back
- push_front --- 头插
- delete from front --- pop_front
- insert
- erase
- Remove
- clear
list data access
Description:
- Accessing data within 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;
}
运行结果：
第一个元素为： 10
最后一个元素为： 40
Summary:
- Data in a list container cannot be accessed via or at() methods.
- Return the first element --- front
- return the last element
list reverse and sort
Description:
- Reverse the elements in the container, and sort the data within it.
Function prototype:
reverse();// reverse a linked listsort();//linked list sorting
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;
}
运行结果：
90 30 20 70
70 20 30 90
20 30 70 90
90 70 30 20
Summary:
- reverse --- reverse
- Sort --- sort (member function)
## Sorting example
Case description: Sorting a custom Person data type, where Person has attributes: name, age, and height.
Sort by age in ascending order; if ages are the same, sort by height in descending order.
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;
}
运行结果：
姓名： 刘备 年龄： 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:
- When dealing with custom data types, it's essential to define a sorting rule; otherwise, the compiler won't know how to sort the elements.
- Advanced sorting simply adds another layer of logical rules on top of the sorting criteria, and it's not complex.