零、前言
本章主要讲解C++中的容器list的使用以及模拟实现
一、什么是list
- list的介绍：
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
list与forward_list(单链表)的操作非常相似，但单链表只能朝前迭代
优劣：
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
对于链表与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问（不是连续开辟的动态空间）
示图：
二、list的常用接口说明
注：以下为list中一些常见的重要接口
1、list对象常用构造
- 使用示例：
void test_list1() { list<int> l1; // 构造空的l1 list<int> l2(4, 100); // l2中放4个值为100的元素 list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构 list<int> l4(l3); // 用l3拷贝构造l4 // 以数组为迭代器区间构造l5 int array[] = { 16,2,77,29 }; list<int> l5(array, array + sizeof(array) / sizeof(int)); // 用迭代器方式打印list中的元素 for (list<int>::iterator it = l2.begin(); it != l2.end(); it++) cout << *it << " "; cout << endl; for (list<int>::iterator it = l4.begin(); it != l4.end(); it++) cout << *it << " "; cout << endl; // C++11范围for的方式遍历 for (auto& e : l5) cout << e << " "; cout << endl; }
2、list对象属性及迭代器使用
- 迭代器示图：
注意：
begin与end为正向迭代器，对迭代器执行**++**操作，迭代器向后移动
**rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++**操作，迭代器向前移动
list的迭代器并不是原生指针，而是经过封装的指针（后续模拟会提及）
使用示例：
void print_list(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; 编译不通过(const迭代器不能修改指向内容) } cout << endl; } void test_list2() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array + sizeof(array) / sizeof(array[0])); // 使用正向迭代器正向list中的元素 for (list<int>::iterator it = l.begin(); it != l.end(); ++it) cout << *it << " "; cout << endl; // 使用反向迭代器逆向打印list中的元素 for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it) cout << *it << " "; cout << endl; cout << l.size() << endl; cout << l.empty() << endl; cout << l.front() << endl; cout << l.back() << endl; }
3、list对象修改操作
- 使用示例：
void PrintList(list<int>& l) { for (auto& e : l) cout << e << " "; cout << endl; } void test_list3() { //push_back/pop_back/push_front/pop_front int array[] = { 1, 2, 3 }; list<int> L(array, array + sizeof(array) / sizeof(array[0])); // 在list的尾部插入4，头部插入0 L.push_back(4); L.push_front(0); PrintList(L); // 删除list尾部节点和头部节点 L.pop_back(); L.pop_front(); PrintList(L); //insert/erase int array1[] = { 4,5,6 }; list<int> L1(array1, array1 + sizeof(array1) / sizeof(array1[0])); // 获取链表中第二个节点 auto pos = ++L1.begin(); cout << *pos << endl; // 在pos前插入值为4的元素 L1.insert(pos, 4); PrintList(L1); // 在pos前插入5个值为5的元素 L1.insert(pos, 5, 5); PrintList(L1); // 在pos前插入[v.begin(), v.end)区间中的元素 vector<int> v{ 7, 8, 9 }; L1.insert(pos, v.begin(), v.end()); PrintList(L1); // 删除pos位置上的元素 L1.erase(pos); PrintList(L1); // 删除list中[begin, end)区间中的元素，即删除list中的所有元素 L1.erase(L1.begin(), L1.end()); PrintList(L1); //resize/swap/clear // 用数组来构造list int array2[] = { 7,8,9 }; list<int> l2(array1, array1 + sizeof(array1) / sizeof(array1[0])); PrintList(l2); // 交换l1和l2中的元素 L1.swap(l2); PrintList(L1); PrintList(l2); // 将l2中的元素清空 l2.clear(); cout << l2.size() << endl; }
