目录
一. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造
1.2.2 list iterator迭代器的使用
1.2.3 list size & empty 大小判空
1.2.4 list element access 头尾引用
1.2.5 list modifiers 增删查改
1.2.6 list的迭代器失效
1.2.7 list 排序的使用
二. list的模拟实现
2.1 模拟实现list
三. list与vector的对比
一. list的介绍及使用
1.1 list的介绍
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) 构造空的l1list<int> l2(4, 100); // (1) l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end()); // (4) 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3); // (3) 用l3拷贝构造l4int array[] = { 16,2,77,29 }; // (5) 以数组为迭代器区间构造l5list<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是BidirectionalIteratorPrint(l1); // 只能用BidirectionalIterator迭代器和向前兼容的迭代器支持的算法// sort函数在algorithm算法库里是RandomAccessIterator，所以list不能用vector<int> v1(array, array + sizeof(array) / sizeof(int));Print(v1);sort(v1.begin(), v1.end()); // vector是RandomAccessIteratorPrint(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的sizecout << 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之前插入55Print(l1);pos = find(l1.begin(), l1.end(), 2);l1.erase(pos); // (6) 删除指定位置的元素 删除2Print(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 }; // 以数组为迭代器区间构造l1list<int> l1(array1, array1 + sizeof(array1) / sizeof(int));int array2[] = { 4,5,6,7 }; // 以数组为迭代器区间构造l2list<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);}// 算法库中的sortint begin1 = clock();sort(v.begin(), v.end());int end1 = clock();// list自己的sortint 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拷贝回listint begin1 = clock();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();// list自带的sortint 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
【免费】C++list的模拟实现资源-CSDN文库
三. list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持下标随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低。 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
总结：
| vector | 优点 | 1.尾插尾删效率不错，支持高效下标随机访问 |
| 2.物理空间连续，所以高速缓存利用率高 | ||
| 缺点 | 1.空间需要扩容，扩容有一些代价（效率和空间浪费） | |
| 2.头部和中间插入删除效率低 | ||
| list | 优点 | 1.按需申请释放空间，不需要扩容 |
| 2.任意位置插入删除 | ||
| 缺点 | 1.不支持下标随机访问 |
