C++:容器list的介绍及使用
目录
1.list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造
1.2.2 list iterator 的使用
1.2.3 list capacity 容量
1.2.4 list element access 访问list元素
1.2.5 list modifiers 修改
1.2.6 迭代器失效
1.list的介绍及使用
1.1 list的介绍
C++官网 list 介绍文档
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，是一个双向带头循环链表。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）
1.2 list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口：
1.2.1 list的构造
| 构造函数（(constructor)） | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
void TestList1()
{list<int> l1; // 构造空的l1list<int> l2(4, 100); // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3list<int> l4(l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印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;
}1.2.2 list iterator 的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。后面会模拟实现
| 函数声明 | 接口说明 |
| begin() + end() | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin() + rend() | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{// 注意这里调用的是list的 begin() const，返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 编译不通过}cout << endl;
}void TestList2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin(); // C++98中语法auto it = l.begin(); // C++11之后推荐写法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}1.2.3 list capacity 容量
| 函数声明 | 接口说明 |
| empty() | 检测list是否为空，是返回true，否则返回false |
| size() | 返回list中有效节点的个数 |
1.2.4 list element access 访问list元素
| 函数声明 | 接口说明 |
| front() | 返回list的第一个节点中值的引用 |
| back() | 返回list的最后一个节点中值的引用 |
1.2.5 list modifiers 修改
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素，即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}void TestList5()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}
另外，list还自己提供了 sort() 函数，用来排序，但是STL种算法库中已经提供了sort函数，这里为什么还要提供呢？
因为迭代器还有三种分类：单向(例如单链表),双向(例如list)和随机迭代器(例如vector)，单向只支持++，双向支持++/--，随机还支持+/-。
void test1()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);//list不支持[]list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;//iterator性质分类//单向++//双向++/--//随机++/--/+/-// list没有办法使用算法库中的sort,所以额外支持sort 因为没有办法随机存取，所以使用归并排序//sort(l.begin(), l.end());//支持的是自由访问迭代器，可以++/--/+/-，这里迭代器是双向的只能++ --l.sort(); //默认升序 for (auto e : l){cout << e << " ";}cout << endl;
}1.2.6 迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，//在下一次使用it时，必须先给其赋值l.erase(it);++it;}
}// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){it = l.erase(it); // 或者 l.erase(it++); }
}本篇结束！list更多详细介绍参考：list的文档介绍