目录
1.2.4 list element access 头尾引用
一. list的介绍及使用
1.1 list的介绍
1.2 list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
1.2.1 list的构造
| 构造函数constructor | 接口说明 | |
| (1) | list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| (2) | list() | 构造空的list |
| (3) | list (const list& x) | 拷贝构造函数 |
| (4) | list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
#include<iostream>
#include<list>
using namespace std;
// list的构造
void test_list1()
{
list<int> l1; // (2) 构造空的l1
list<int> l2(4, 100); // (1) l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // (4) 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l4(l3); // (3) 用l3拷贝构造l4
int array[] = { 16,2,77,29 }; // (5) 以数组为迭代器区间构造l5
list<int> l5(array, array + sizeof(array) / sizeof(int));
list<int> l6{ 1,2,3,4,5 }; // (6) 列表格式初始化C++11
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " ";
cout << endl;
}
int main()
{
test_list1();
return 0;
}1.2.2 list iterator迭代器的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
示例：
#include<algorithm>
#include<iostream>
#include<list>
#include<vector>
using namespace std;
// 打印函数
template<typename T>
void Print(T ls)
{
for (auto a : ls)
cout << a << " ";
cout << endl;
}
void test_list4()
{
int array[] = { 16,2,77,29 }; // 以数组为迭代器区间构造
list<int> l1(array, array + sizeof(array) / sizeof(int));
Print(l1);
//sort(l1.begin(), l1.end()); //报错：不定义该运算符或到预定义运算符可接收的类型的转换
reverse(l1.begin(), l1.end()); // list是BidirectionalIterator
Print(l1); // 只能用BidirectionalIterator迭代器和向前兼容的迭代器支持的算法
// sort函数在algorithm算法库里是RandomAccessIterator，所以list不能用
vector<int> v1(array, array + sizeof(array) / sizeof(int));
Print(v1);
sort(v1.begin(), v1.end()); // vector是RandomAccessIterator
Print(v1); // 能用RandomAccessIterator迭代器和向前兼容的迭代器支持的算法
reverse(v1.begin(), v1.end()); // sort函数vector迭代器本来就支持
Print(v1); // reverse函数是RandomAccessIterator迭代器向前兼容的迭代器支持的算法
// 但是list库里自己定义了sort函数
cout << endl;
l1.sort();
Print(l1);
}
int main()
{
test_list4();
return 0;
}| 函数声明 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin+rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
【注意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
1.2.3 list size & empty 大小判空
| 函数声明 | 接口说明 | |
| (1) | empty | 检测list是否为空，是返回true，否则返回false |
| (2) | size | 返回list中有效节点的个数 |
1.2.4 list element access 头尾引用
| 函数声明 | 接口说明 | |
| (1) | front | 返回list的第一个节点中值的引用& |
| (2) | back | 返回list的最后一个节点中值的引用& |
示例：1.2.3、1.2.4
#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(list<T> ls)
{
for (auto a : ls)
cout << a << " ";
cout << endl;
}
void test_list2()
{
int array[] = { 16,2,77,29 }; // 以数组为迭代器区间构造
list<int> l1(array, array + sizeof(array) / sizeof(int));
Print(l1);
cout << l1.size() << endl; // (1) 返回l1的size
cout << l1.empty() << endl; // (2) 返回l1是否为空
cout << l1.front() << endl; // (3) 返回l1首元素的引用
cout << l1.back() << endl; // (4) 返回l1最后一个元素的引用
}
int main()
{
test_list2();
return 0;
}1.2.5 list modifiers 增删查改
| 函数声明 | 接口说明 | |
| (1) | push_front | 在list首元素前插入值为val的元素 |
| (2) | pop_front | 删除list中第一个元素 |
| (3) | push_back | 在list尾部插入值为val的元素 |
| (4) | pop_back | 删除list中最后一个元素 |
| (5) | insert | 在list position 位置中插入值为val的元素 |
| (6) | erase | 删除list position位置的元素 |
| (7) | swap | 交换两个list中的元素 |
| (8) | clear | 清空list中的有效元素 |
| (9) | splice | 在L1的position前插入另一个链表L2的元素，内存上相当于move，插入后L2的元素就clear了 |
list中还有一些操作，需要用到时大家可参阅list的文档说明。
示例1：（1）~（8）
#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(list<T> ls)
{
for (auto a : ls)
cout << a << " ";
cout << endl;
}
void test_list3()
{
int array[] = { 16,2,77,29 }; // 以数组为迭代器区间构造
list<int> l1(array, array + sizeof(array) / sizeof(int));
Print(l1);
l1.push_front(100); // (1) 头插
Print(l1);
l1.pop_front(); // (2) 头删
Print(l1);
l1.push_back(99); // (3) 尾插
Print(l1);
l1.pop_back(); // (4) 尾删
Print(l1);
cout << endl;
list<int>::iterator pos = find(l1.begin(),l1.end(),77);
l1.insert(pos, 55); // (5) 指定位置之前插入 在77之前插入55
Print(l1);
pos = find(l1.begin(), l1.end(), 2);
l1.erase(pos); // (6) 删除指定位置的元素 删除2
Print(l1);
cout << endl;
list<int> l2(3, 100);
swap(l1, l2); // (7) 交换两个列表的元素，大小可以不同
Print(l1);
Print(l2);
l1.clear();
Print(l1); // (8) 清空列表的元素
cout << "clear" << endl;
}
int main()
{
test_list3();
return 0;
}
示例2：（9）
move链表 (1) void splice (iterator position, list& x);
// 把 x 的所有元素移到 position 前面
move链表的某个迭代器指向的元素(2) void splice (iterator position, list& x, iterator i);
// 把 x 的 i 迭代器指向的元素移到 position 前
move链表的一段区间的元素 (3) void splice (iterator position, list& x, iterator first, iterator last);
// 把 x 的从 [first, last) 迭代器之间的元素移到 position 前
注意，splice可以移动其他链表的元素，也可以移动自身链表的元素。
#include<iostream>
#include<list>
using namespace std;
// 打印函数
template<typename T>
void Print(T ls)
{
for (auto a : ls)
cout << a << " ";
cout << endl;
}
void test_list5()
{
int array1[] = {1,2,3,8,9,10 }; // 以数组为迭代器区间构造l1
list<int> l1(array1, array1 + sizeof(array1) / sizeof(int));
int array2[] = { 4,5,6,7 }; // 以数组为迭代器区间构造l2
list<int> l2(array2, array2 + sizeof(array2) / sizeof(int));
list<int>::iterator it = find(l1.begin(), l1.end(), 3);
++it;
l1.splice(it, l2); // (1) 将l2的所有元素移到l1的3元素之后
Print(l1);
Print(l2);
cout << "splice" << endl;
l1.splice(l1.begin(), l1, --l1.end());
Print(l1); // (2) 将l1的最后一个元素移动到第一个元素之前
l1.splice(l1.end(), l1, l1.begin());
Print(l1); // (2) 将l1的第一个元素移动到最后一个元素的位置
it = find(l1.begin(), l1.end(), 5);
l1.splice(l1.begin(), l1, ++it, l1.end());
Print(l1); // (3) 将l1的从5后面到最后一个元素启动到第一个元素之前
}
int main()
{
test_list5();
return 0;
}
1.2.6 list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
1.2.7 list 排序的使用
list自带的sort排序效果较差，不如list拷贝到vector调用算法库排序在拷贝回list效果好。
注意：排序测试不要用Debug，用Release测试出的才是真实水平。
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
void test_op1()
{
srand(time(0));
const int N = 1000000;
list<int> lt1;
vector<int> v;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
lt1.push_back(e);
v.push_back(e);
}
// 算法库中的sort
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
// list自己的sort
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
void test_op2()
{
srand(time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
lt1.push_back(e);
lt2.push_back(e);
}
// list拷贝给vector，用算法库将vector排序，在把vector拷贝回list
int begin1 = clock();
// 拷贝vector
vector<int> v(lt2.begin(), lt2.end());
// 排序
sort(v.begin(), v.end());
// 拷贝回lt2
lt2.assign(v.begin(), v.end());
int end1 = clock();
// list自带的sort
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
int main()
{
test_op1(); // vector调用库函数sort排序，和list自带排序对比
cout << endl;
test_op2(); // list拷贝到vector排完序再拷贝回list，和list自带排序对比
return 0; //总结：list自带的排序效果差
}二. list的模拟实现
2.1 模拟实现list
三. list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持下标随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低。 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
总结：
| vector | 优点 | 1.尾插尾删效率不错，支持高效下标随机访问 |
| 2.物理空间连续，所以高速缓存利用率高 | ||
| 缺点 | 1.空间需要扩容，扩容有一些代价（效率和空间浪费） | |
| 2.头部和中间插入删除效率低 | ||
| list | 优点 | 1.按需申请释放空间，不需要扩容 |
| 2.任意位置插入删除 | ||
| 缺点 | 1.不支持下标随机访问 |