list简介
简介：链表，是一种在物理存储单元上非连续的存储结构。
list构造函数
函数原型：
- list<T> lst; // list采用模板类实现，对象的默认构造形式
- list(beg,end);// 构造函数[beg,end)区间中的元素拷贝给本身
- list(n,elem);// 构造函数将n个elem拷贝被本身
- list(const list &list);// 拷贝构造函数
测试代码：
#inclue<iostream> using namespace std; #include<list> // 遍历容器的方法 void PrintList(const list<int>& L) { for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) { cout << *it << " "; } cout << endl; } void test01() { // Create a list container // 创建容器 list<int>L1; // Add data // 添加数据 L1.push_back(10); L1.push_back(20); L1.push_back(30); L1.push_back(40); // Traverse container // 遍历容器 cout << "L1: "; PrintList(L1); cout << endl; // Constructed in the way of interval // 以区间形式拷贝 list<int>L2(L1.begin(), L1.end()); cout << "L2: "; PrintList(L2); cout << endl; // Copy constructer // 拷贝构造方式构建 list<int>L3(L2); cout << "L3: "; PrintList(L3); cout << endl; // n elements // 构造函数将n个elem拷贝被本身 list<int>L4(10, 1000); cout << "L4: "; PrintList(L4); cout << endl; } int main() { test01(); return 0; }
运行结果：
总结：list构造方式同其他几个STL常用容器相似。
Summary: list is similar to several other STL containers.
list 赋值和交换
- assign(beg,end); // 将[beg,end)区间中的数据拷贝赋值给本身
- assign(n,elem); // 将n个elem拷贝赋值给本身
- list& operator=(const list &lst);// 重载等号操作符
- swap(lst); // 将lst与本身的元素互换
#include<iostream> #include<list> // Assignment and exchange of list container 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; } // Assignment void test01() { list<int>L1; L1.push_back(10); L1.push_back(20); L1.push_back(30); L1.push_back(40); cout << "L1: "; PrintList(L1); cout << endl; list<int>L2; L2 = L1; // list& operator = (const list & list) cout << "L2: "; PrintList(L2); cout << endl; list<int>L3; // assign(beg,end); // 将[beg,end)区间中的数据拷贝赋值给本身 L3.assign(L2.begin(), L2.end()); cout << "L3: "; PrintList(L3); cout << endl; list<int>L4; // assign(n,elem); // 将n个elem拷贝赋值给本身 L4.assign(10, 100); cout << "L4: "; PrintList(L4); cout << endl; } // Swap 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, 123); cout << "交换前：" << endl; cout << "L1: "; PrintList(L1); cout << endl; cout << "L2: "; PrintList(L2); cout << endl; cout << "交换后： " << endl; L2.swap(L1); cout << "L1: "; PrintList(L1); cout << endl; cout << "L2: "; PrintList(L2); cout << endl; } int main() { cout << "赋值：" << endl; test01(); cout << "交换：\n" << endl; test02(); system("pause"); return 0; }
运行结果：
list大小操作
功能：对list容器的大小进行操作
函数原型：
- size();// 返回容器中元素的个数
- empty();// 判断容器是否为空
- resize(num);// 重新指定容器的长度为num，若容器变长，则以默认值填充新位置
// 如果容器变短，则末尾超出容器的长度的元素被删除 - resize(num, elem);// 重新指定容器的长度num，若容器变长，则以elem值填充新位置
// 如果容器变短，则末尾超出容器长度的元素被删除
#include<iostream> #include<list> using namespace std; // List container size operation 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); cout << "L1: "; PrintList(L1); cout << endl; // Judge whether the container is empty if (L1.empty()) { cout << "L1为空" << endl; } else { cout << "L1不为空" << endl; cout << "L1的元素个数为：" << L1.size() << endl; } cout << endl; // Re size L1.resize(10, 10000); cout << "L1: "; PrintList(L1); cout << endl; L1.resize(2); // Take the first two elements of the list cout << "L1: "; PrintList(L1); cout << endl; } int main() { test01(); return 0; }
运行结果：
list插入和删除
- 尾插 — push_back();
- 尾删 — pop_back();
- 头插 — push_front();
- 头删 — pop_front();
- 插入 — insert();
- 删除 — erase();
- 移除 — remove();
- 清空 — clear();
这里要说明的是list迭代器不能跳跃移动，例如insert函数中的参数写成L.begin() + n的操作是不可以的，只能写成++L.begin(), 或者提前定义一个迭代器变量it然后++it才能访问下一个位置，因为list的指针域指向指向下一个元素，并没有指向下下个元素。
What I want to explain here is that the list iterator cannot jump. For example, the operator of writing the parameter in the insert function as L.begin() + n is not allowed. it can only be written as ++L.begin(), or define an iterator variable “it” in advance, and then ++it can access the next position, because the pointer field of the list points to the next element, not to the next next element.
#include<iostream> #include<list> // Insertion and deletion of list container 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; // push_back tail insertion // 尾插 L.push_back(10); L.push_back(20); L.push_back(30); // push_front head insertion // 头插入 L.push_front(100); L.push_front(200); L.push_front(300); // 300 200 100 10 20 30 cout << "L: "; PrintList(L); cout << endl; // pop_back tail deletion // 头插 L.pop_back(); // 300 200 100 10 20 cout << "L: "; PrintList(L); cout << endl; // pop_head head deletion // 头插 L.pop_front(); // 200 100 10 20 cout << "L: "; PrintList(L); cout << endl; // Inser Insertion // 索引为1的位置插入 L.insert(++L.begin(), 12345); // 200 12345 100 10 20 cout << "L: "; PrintList(L); cout << endl; // erase deletion // 删掉索引为1的 list<int>::const_iterator it = L.begin(); L.erase(++it); // 200 100 10 20; cout << "L: "; PrintList(L); cout << endl; // Remove by value // 尾插 L.push_back(10); // 200 100 10 20 10 L.remove(10); // 200 100 20 cout << "L: "; PrintList(L); cout << endl; } int main() { test01(); return 0; }
运行结果：
list 数据存取
功能描述：对list容器中数据进行存取
要说明的是因为链表存储不是一段连续线性的空间，list容器不支持直接用at,[],两种方式的访问元素和随机访问，list的迭代器是一个双向迭代器，只支持前移或者后移，不支持跳跃式访问，所以只有front(), back()两个接口，不过可以通过’++'运算符，多加几次找到自己想要的位置，或者自己写个函数，函数里面的原理类似打印时的那个循环，改变迭代器的位置，来达到自己想要的位置.
It should be noted that because the list storage is not a continuous linear space. the list container does not support direct access to elements and random access by at and [] methods.
The iterator of the list is a two-way iterator, which only supports forward or backward movement, and does not support skip access, so it has only two functions front() and back() are two interfaces, but you can use the '++'operator to add several times to find the position
you want, or you can write a function. The principle of the function is similar to the loop when printing, and you can change the position of the iteration to achieve the position you want.
函数原型：
- front();// 返回第一个元素
- back();// 返回最后一个元素
#include<iostream> #include<list> using namespace std; /*Data access of list container*/ 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); cout << "第一个元素为：" << L1.front() << endl; cout << "最后一个元素为：" << L1.back() << endl; // Verification iterators do not support random access list<int>::iterator it = L1.begin(); // it += 1; it += 5; It's all wrong } int main() { test01(); system("pause"); return 0; }
运行结果：
list反转和排序
功能描述：将容器中的元素翻转，以及将容器中的数据排序。
函数原型：
- reverse();// 反转链表
- sort();// 链表排序
注意：所有不支持随机访问的迭代器的容器，不可以用标准的排序算法。
不支持随机访问迭代器的容器，内部会提供对应的一些算法.
Note: all containers that do not support random access iterators cannot use standard sorting algorithm.
Containers that do not support random access iterators will provide corresponding algorithm.
#include<iostream> #include<list> #include<algorithm> using namespace std; /*Reverse and sort of list container*/ bool cmp(int v1, int v2) { return v1 > v2; } 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(20); L1.push_back(10); L1.push_back(50); L1.push_back(40); L1.push_back(0); // Reverse cout << "反转前L1: "; PrintList(L1); cout << endl; cout << "反转后L1: "; L1.reverse(); PrintList(L1); cout << endl; } void test02() { list<int>L1; L1.push_back(20); L1.push_back(10); L1.push_back(50); L1.push_back(40); L1.push_back(0); // Sort // You can't write that /* sort(L1.begin(), L1.end()); */ L1.sort(); // Default rule: ascending order, from small to large cout << "升序 排序后L1: "; PrintList(L1); cout << endl; L1.sort(cmp); // You can customize function rules cout << "降序 排序后L1: "; PrintList(L1); cout << endl; } int main() { test01(); test02(); system("pause"); return 0; }
运行结果：
