C++之STL——list类

• list简介
• list的使用
• • list的构造函数
  • list的迭代器
  • list的capacity
  • list的元素提取
  • list的插入和删除
• list的迭代器失效

1、list的插入和删除的时间复杂度是在常数范围内的序列式容器，并且由于list的底层是用双链表实现的，该容器支持双向迭代。
2、与其他序列式容器相比(array，vector，deque)，list在任意位置进行插入和删除的效率更高。
3、list最大的缺陷就是不支持任意位置的随机访问。

在vector中，由于vector的底层是用连续空间进行存储的，因此原生指针就可以作为迭代器使用；但是list的底层是非连续空间，原生指针无法再作为迭代器，因此list的迭代器是通过模板封装实现的，这部分的底层原理放在下一篇博客模拟实现时进行详细解释。

从图中可以看出，begin()是指向头节点的下一个节点，end()是指向头节点的。

由于list的空间不是连续的，在使用时即插即用，因此list的底层没有改变空间和改变有效长度的函数reserve和resize。

list v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  v1.push_back(5);
  v1.push_back(6);
  cout << "push_back(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;
  v1.push_front(10);
  v1.push_front(12);
  v1.push_front(13);
  cout << "push_front(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;
  v1.pop_back();
  v1.pop_back();
  cout << "pop_back(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;
  v1.pop_front();
  v1.pop_front();
  cout << "pop_front(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;
  list::iterator pos = find(v1.begin(), v1.end(), 3);
  v1.insert(pos, 100);

  cout << "insert(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;

  
  pos = find(v1.begin(), v1.end(), 4);
  v1.erase(pos);

  cout << "erase(): ";
  for(auto e : v1)
    cout << e << " ";
  cout << endl;

在前面的stl容器中已经介绍过了迭代器失效的问题，这里的迭代器可以理解为指针，迭代器失效指的是迭代器所指向的节点无效，即该节点所指向的空间被释放了或者已经无意义了，如果此时还在该节点的迭代器进行操作就会出现错误。list的底层是带头节点的双向循环链表，因此在list中进行插入的时候不会导致迭代器的失效，只有在删除的时候才会失效，因为list的删除是释放该节点，此时对应的迭代器指向的空间是无效的。
这里还要注意一点，失效的只是被删除节点的迭代器，不会影响其他节点的迭代器。

例如上面这段代码，目的是像想删除list中的所有元素，但是在删除之前没有保留当前元素的下一个节点的位置，在删除之后进行加一就会导致野指针的访问，这是典型的迭代器失效。
因此想要防止迭代器失效，就需要在删除节点之前，将该节点的下一个位置保存下来，及时更新迭代器。