-
头文件：#include
-
Lists将元素按顺序储存在链表中。与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。
-
list的特点：
(1)不使用连续的内存空间这样可以随意地进行动态操作；
(2)可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop。
(3)不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
(4)相对于verctor占用更多的内存。
1、 list中的构造函数
- list() 声明一个空列表；
- list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的，元素默认值为：0，即
n个0；
- list(n,val) 声明一个由
n个val元素的列表;
- list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素；
- list (const list &);拷贝构造函数,要求类型一致；
- list data4(data3.begin(),data3.end()); √
list data4(data3.begin(),data3.begin()+3); ×
报错：没有“+”运算符重载
- for (; itor4 !=
data4.end()-8; ++itor4) { // 报错：没有“-”运算符重载
cout << *itor4 << " ";
}
for (; itor4 != data4.end(); ++itor4) { √
cout << *itor4 << " "; // k k k k k k
}
#include <iostream>
#include <list>
using namespace std;
int main() {
//------------------ 1. list() 声明一个空列表
list<int> data1;
cout << data1.size() << endl; // 0
//------------------ 2. list(n) 声明一个有n个元素的列表.值为0
list<int> data(10);
list<int>::iterator itor = data.begin(); // 遍历
for (; itor != data.end(); ++itor) {
cout << *itor << " "; // 0 0 0 0 0 0 0 0 0 0
}
//------------------3. list(n, val)
list<int> data2(5, 10);
list<int>::iterator itor2 = data2.begin(); // 遍历
for (; itor2 != data2.end(); ++itor2) {
cout << *itor2 << " "; // 10 10 10 10 10
}
//------------------4. list(first, last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素
list<char> data3(6,'k');
list<char> data4(data3.begin(),data3.end());
list<char>::iterator itor4 = data4.begin(); // 遍历
for (; itor4 != data4.end(); ++itor4) {
cout << *itor4 << " "; // k k k k k k
}
//------------------5. list(const list &); 拷贝构造函数
list<char> data5(6, 'g');
list<char> data6(data5);
list<char>::iterator itor6 = data6.begin(); // 遍历
for (; itor6 != data6.end(); ++itor6) {
cout << *itor6 << " "; // g g g g g g
}
return 0;
}
2、 begin()和end()——list 容器的iterator
- 通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator；
- 可以调用list容器的
end()函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。
3、 增
3.1 push_back() 末端插入
3.2 push_front() 头部插入
3.3 insert() 在指定位置插入n个元素
- l1.insert(l1.begin(),100); // 在l1的开始位置插入100。
- l1.insert(l1.begin(),2,200); // 在l1的开始位置插入2个100。
- l1.insert(l1.begin(),l2.begin(),l2.end()); // 在l1的开始位置插入l2的从开始到结束的所有位置的元素。
代码演示
int main() {
//------------------ insert() 在指定位置插入n个元素
list<int> data1;
data1.push_back(1);
data1.push_back(1);
data1.push_back(1);
data1.push_front(2);
data1.push_front(2);
data1.push_front(2);
list<int>::iterator itor1 = data1.begin(); // 遍历
for (; itor1 != data1.end(); ++itor1) {
cout << *itor1 << " "; // 2 2 2 1 1 1
}
//******** 1.在某个位置插入1个x
data1.insert(data1.begin(), 9);
data1.insert(data1.begin(), 10);
list<int>::iterator itor2 = data1.begin(); // 遍历
for (; itor2 != data1.end(); ++itor2) {
cout << *itor2 << " "; // 10 9 2 2 2 1 1 1
}
//******** 2.在某个位置插入n个x
list<int> data2;
data2.push_back(1);
data2.push_back(1);
data2.push_back(1);
data2.insert(data2.begin(), 5, 4); // 头插
data2.insert(data2.begin(), 2, 7);
data2.insert(data2.end(), 5, 4); // 尾插
data2.insert(data2.end(), 2, 7);
for (list<int>::iterator itor3 = data2.begin(); itor3 != data2.end(); ++itor3) { // 遍历
cout << *itor3 << " "; // 7 7 4 4 4 4 4 1 1 1 4 4 4 4 4 7 7
}
//******** 3.在某个位置插入[begin,end）元素
list<int> data3;
data3.push_back(1);
data3.push_back(1);
data3.push_back(1);
list<int> data4;
data4.push_back(2);
data4.push_back(2);
data4.push_back(2);
cout << endl;
data3.insert(data3.begin(), data4.begin(),data4.end()); // 头插
for (auto itor3 = data3.begin(); itor3 != data3.end(); ++itor3) { // 遍历
cout << *itor3 << " "; // 2 2 2 1 1 1
}
return 0;
}
4、删
- 通过pop_back()删除最后一个元素，通过pop_front()删除第一个元素；
- 序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。
4.1 pop_back() 删尾
4.2 pop_front() 删头
4.3 erase() 删除n个元素
- l1.erase(l1.begin()); 将l1的第一个元素删除。
- l1.erase(l1.begin(),l1.end()); 将l1的从begin()到end()之间的元素删除。
【注意】：
data2.end() 表示指向4后面的位置，该位置不存在元素，因此：
auto itor2 = data2.erase(–data2.end()); ✔ 删除的是4，剩下为 2 3
auto itor2 = data2.erase(data2.end()); ❌ 删除的元素不存在，报错
4.4 clear() 清空
代码演示
#include <iostream>
#include <list>
using namespace std;
int main() {
//------------------ pop_back 删尾和 pop_front() 删头
list<int> data1;
data1.push_back(1);
data1.push_back(2);
data1.push_back(3);
data1.pop_back(); // 删尾
for (auto it = data1.begin(); it != data1.end(); ++it) {
cout << *it << " "; // 1 2
}
data1.pop_front(); // 删头
for (auto it = data1.begin(); it != data1.end(); ++it) {
cout << *it << " "; // 2
}
//------------------ erase() 删除n个元素
// ******* 1. erase(iterator it)
list<int> data2;
data2.push_back(1);
data2.push_back(2);
data2.push_back(3);
data2.push_back(4);
//==== 1.1 erase(data2.begin())
auto itor1= data2.erase(data2.begin());
cout <<"删除后的下一个元素为："<< *itor1 << endl; // 2
for (auto it = data2.begin(); it != data2.end(); ++it) {
cout << *it << " "; // 2 3 4
}
//==== 1.2 erase(--data2.end())
/*原列表元素：2 3 4;
data2.end() 表示指向4后面的位置，该位置不存在元素，因此：
auto itor2 = data2.erase(--data2.end()); ✔删除的是4，剩下为 2 3
auto itor2 = data2.erase(data2.end()); ❌ 删除的元素不存在，报错 */
auto itor2 = data2.erase(--data2.end());
for (auto it = data2.begin(); it != data2.end(); ++it) {
cout << *it << " "; // 2 3
}
// ******* 2. erase(iterator first,iterator last);删除当前列表[first,last)之间的元素
list<int> data3;
data3.push_back(1);
data3.push_back(2);
data3.push_back(3);
data3.push_back(4);
auto it3 = data3.erase(++data3.begin(), --data3.end());
for (auto it = data3.begin(); it != data3.end(); ++it) {
cout << *it << " "; // 1 4
}
//------------------ clear() 清空
list<int> data4;
data4.push_back(1);
data4.push_back(2);
data4.push_back(3);
data4.push_back(4);
data4.clear();
for (auto it = data4.begin(); it != data4.end(); ++it) {
cout << "data4="<< *it << " "; // (空)
}
return 0;
}
5、改
5.1 assign() 替换/赋值
- l1.assign(n,val); // 将当前列表中所有元素替换为n个T类型的val
- l1.assign(l2.begin(),l2.end()); // 将12列表中的从l2.begin()到l2.end()之间的数值赋值给当前列表l1
5.2 swap() 交换
交换两个链表(两个重载)语法：（都可能完成连个链表的交换）
（1） l1.swap(l2);
（2）swap(l1,l2)；
5.3 reverse() 逆置
5.4 merge() 合并
合并两个链表并使之默认升序(也可改)：
l1.merge(l2，greater());
- 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，升序。
- 其实默认是升序，greater()可以省略。
- 另外greater()是可以变的，也可以不按升序排列，例如：less()是降序排列。
代码演示
#include <iostream>
#include <list>
#include <functional>
using namespace std;
int main() {
//------------------ 1. assign() 赋值/替换
// ***** 1.1 assign(n,val) 将列表中所有元素替换为n个T类型的val
list<int> data1;
data1.push_back(1);
data1.push_back(2);
data1.push_back(3);
data1.assign(2, 9);
for (auto it = data1.begin(); it != data1.end(); ++it) {
cout << "data1="<< *it << " "; // data1=9 data1=9
}
// ***** 1.2 l1.assign(l2.begin(), l2.end()); 将12列表中的从l2.begin()到l2.end()之间的数值赋值给当前列表l1
list<int> data1_2;
data1_2.push_back(1);
data1_2.push_back(1);
data1_2.push_back(1);
list<int> data1_3;
data1_3.push_back(2);
data1_3.push_back(2);
data1_3.push_back(2);
data1_2.assign(++data1_3.begin(), data1_3.end());
for (auto it = data1_2.begin(); it != data1_2.end(); ++it) {
cout << "data1_2 = " << *it << " "; // data1_2 = 2 data1_2 = 2
}
//------------------ 2. swap() 交换
// ***** 2.1 l1.swap(l2);
list<int> data2_1;
data2_1.push_back(1);
data2_1.push_back(1);
data2_1.push_back(1);
list<int> data2_2;
data2_2.push_back(2);
data2_2.push_back(2);
data2_2.push_back(2);
data2_1.swap(data2_2); // 交换
for (auto it = data2_1.begin(); it != data2_1.end(); ++it) {
cout << "data2_1 = " << *it << " "; // ata2_1 = 2 data2_1 = 2 data2_1 = 2
}
for (auto it = data2_2.begin(); it != data2_2.end(); ++it) {
cout << "data2_2 = " << *it << " "; // data2_2 = 1 data2_2 = 1 data2_2 = 1
}
cout << endl;
//***** 2.2 swap(l1,l2)；
swap(data2_1, data2_2);
for (auto it = data2_1.begin(); it != data2_1.end(); ++it) {
cout << "data2_1 = " << *it << " "; // data2_1 = 1 data2_1 = 1 data2_1 = 1
}
cout << endl;
for (auto it = data2_2.begin(); it != data2_2.end(); ++it) {
cout << "data2_2 = " << *it << " "; // data2_2 = 2 data2_2 = 2 data2_2 = 2
}
//------------------ 3. reverse() 逆置
list<int> data3;
data3.push_back(1);
data3.push_back(2);
data3.push_back(3);
data3.reverse();
for (auto it = data3.begin(); it != data3.end(); ++it) {
cout << *it << " "; // 3 2 1
}
//------------------ 4. merge() 合并
//**** 合并后降序排列
//**** 合并后升序排列
return 0;
}
6、查
6.1 front() 获取头部元素
- 通过front()可以获得list容器中的头部元素，通过back()可以获得list容器的最后一个元素。
- 但是有一点要注意，就是list中元素是空的时候，这时候调用front()和back()会发生什么呢？实际上会发生不能正常读取数据的情况，但是这并不报错，那我们编程序时就要注意了，个人觉得在使用之前最好先调用empty()函数判断list是否为空。
6.2 back() 获取尾部元素
6.3 遍历（不支持 [] 和“<<”）
int main() {
//------------------1. front() 获取头部元素 和 back() 获取尾部元素
list<char> data1 = {'a','b','c'};
cout << data1.front()<<endl; // a
cout<< data1.back() << endl; // c
// -----------------2. 遍历
//******* 法1：
list<char>::iterator itor;
for (itor = data1.begin(); itor != data1.end(); ++itor) {
cout << *itor << " "; // a b c
}
//******* 法2：
for (list<char>::iterator itor = data1.begin(); itor != data1.end(); ++itor) {
cout << *itor << " "; // a b c
}
//******* 法3：
for (auto it = data1.begin(); it != data1.end(); ++it) {
cout << *it << " ";
}
return 0;
}
7、empty() 判空
8、resize() 修改list容器容量
-
resize(n)将list的长度改为n；
（1）超出的元素将被删除；
（2）不足部分：
① 类型 默认补‘空格’
② 类型 默认补0
-
resize(n,val)，将list的长度改为n;
（1）超出的元素将被删除；
（2）不足部分：补val
