1.list的介绍及使用
list介绍 ，可以通过以下图直观的感受到 vector 和 list 的区别
Vector 插入代价高，但便于排序
List 不连续，不能加，但插入的代价特别低
如果需要频繁随机访问元素或在尾部进行插入和删除操作，可以选择Vector；
如果需要频繁在任意位置进行插入和删除操作，可以选择List
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展 的能力。以下为list中一些常见的重要接口。
1.1.list的构造
代码：
#include<iostream> #include<list> using namespace std; void test1() { list<int> l1; list<int> l2(4, 100); list<int> l3(l2.begin(), l2.end()); list<int> l4(l3); //以数组迭代器构造l5 int arr[] = { 116,2,77,29 }; list<int> l5(arr, arr + sizeof(arr) / sizeof(int)); //列表格式初始化 list<int> l6{ 1,2,3,4,5 }; //迭代器方法打印 auto it = l5.begin();//begin()不要忘记括号了 while (it != l5.end()) { cout << *it << " "; ++it; } cout << endl; //语法糖 for (auto e : l3) cout << e << " "; cout << endl; } int main() { test1(); cin.get(); return 0; }
1.2 list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
代码：
void test2() { 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. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
1.3. list capacity
list element access
1.4.list modifiers
ps: vector就没有头插和头删
void test3() { int arr[] = { 1, 2, 3 }; list<int> L(arr, arr + sizeof(arr) / sizeof(int)); print(L); //尾插4，头插0 //删除尾部和头部节点 L.push_back(4); L.push_front(0); print(L); L.pop_back(); L.pop_front(); print(L); //insert/erase //获取链表中的第二个元素 auto pos = ++L.begin(); //pos前插入4 L.insert(pos, 4); //pos前插入5个元素为5的数值 L.insert(pos, 5, 3); print(L); //在pos前插入v.begin、v.end之间的元素 vector<int> v{ 7, 8, 9 }; L.insert(pos, v.begin(), v.end()); print(L); //删除pos上的元素 L.erase(pos); print(L); //删除list中的所有元素 L.clear(); print(L); }
注意：
pos 是指向最初的第二个节点的位置的迭代器。当调用 L.erase(pos); 时，实际上是删除了 pos 所指向的节点，而不是删除 pos 这个迭代器本身。
1.5.迭代器不会受到影响。
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了。因为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 test4() { 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()) { l.erase(it++); // it = l.erase(it); //it要++指向下一个 } } int main() { //test1(); //test2(); //test3(); test4(); cin.get(); return 0; }
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：
