STL—容器—list【list的介绍和基本使用】【list的迭代器失效问题】

STL—容器—list

list的使用并不难，有了之前使用string和vector的基础后，学习起来并不难。因此这里不在详细的讲解如何使用，而是大致的将其基本接口都熟悉一下

1.list介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。其实就是双向循环链表
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素。

2.list的使用

ist中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，从而达到可扩展的能力。以下为list中一些常见的重要接口

2.1list的构造

1. list (size_type n, const value_type& val = value_type()) ，构造n个值val的元素的list
2. list() ，构造空的list
3. list (const list& x) ，拷贝构造
4. list (InputIterator first, InputIterator last)，迭代器构造

四个构造函数的使用代码：

void test1()
{// list (size_type n, const value_type& val = value_t)list<int> l1(5, 1);list<int>::iterator it1 = l1.begin();while (it1 != l1.end()){cout << *it1 << " ";++it1;}cout << endl;//list (const list& x)list<int> l2(l1);list<int>::iterator it2 = l2.begin();while (it2 != l2.end()){cout << *it2 << " ";++it2;}cout << endl;//list()list<int> l3;l3.push_back(2);l3.push_back(3);l3.push_back(4);list<int>::iterator it3 = l3.begin();while (it3 != l3.end()){cout << *it3 << " ";it3++;}cout << endl;// list(InputIterator first, InputIterator last)list<int> l4(l3.begin(), l3.end());list<int>::iterator it4 = l4.begin();while (it4 != l4.end()){cout << *it4 << " ";it4++;}cout << endl;}

2.2 list 迭代器的使用

list是一个双向迭代器，因为其结构是双向链表，如果是list_forword就是单向迭代器。vector是随机迭代器——支持begin + n的操作，可以随机访问。

正向迭代器，反向迭代器，带const的正向迭代器，带const的反向迭代器

正向迭代器用begin()和end()，反向的用rbegin() 和 rend()

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

使用代码如下：

// 带const迭代器的使用
void print_list(const list<int>& l)
{list<int>::const_iterator cit = l.begin();while (cit != l.end()){cout << *cit << " ";cit++;}cout << endl;
}// 带const的反向迭代器的使用
void print_reverse_list(const list<int>& l)
{list<int>::const_reverse_iterator rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}// 迭代器的使用
void test2()
{list<int> l;l.push_back(1);l.push_back(1);l.push_back(1);l.push_back(1);l.push_front(0);l.push_front(-1);l.pop_back();l.pop_back();list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;print_list(l);list<int>::reverse_iterator rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";rit++;}cout << endl;print_reverse_list(l);}

要注意：

只要支持迭代器的容器就支持范围for循环、

// 范围for循环，只要支持迭代器的容器就支持范围for循环、
void test4()
{list<string> ls;ls.push_back("aaa");ls.push_back("bbb");ls.push_back("ccc");for (auto e : ls){cout << e << " ";}cout << endl;
}

2.3赋值运算符的使用

这个就和之前的赋值运算符一样用就行，比较简单。

// 赋值运算符
void test3()
{list<int> l1;l1.push_back(1);l1.push_back(2);list<int> l2;l2 = l1;print_list(l2);
}

2.4 list capacity()

在list容器中，不太存在容量这个接口，因为不会有提前开辟的空间等待使用，没什么意义，而是用多少开多少。

empty和size接口的使用

// empty 和 size接口的使用
void test1()
{list<int> l;l.push_back(1);if (l.empty()){cout << "该list为空\n";cout << l.size() << endl;}else{cout << "该list不为空\n";cout << l.size() << endl;}
}

2.5 list element access

front和back的使用：

// front 和 back的使用
void test2()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);cout << l.front() << endl; // 1cout << l.back() << endl; // 4
}

2.6list modifiers(增删查改)

这里只展示了部分的接口

使用代码如下：

// 增删查改类接口使用
void test3()
{list<int> l;// push_backl.push_back(3);l.push_back(4);print_list(l); // 3 4// push_frontl.push_front(2);l.push_front(1);print_list(l); // 1 2 3 4// pop_back / pop_frontl.pop_back(); l.pop_front();print_list(l); // 2 3// insertl.insert(l.begin(), 0);l.insert(l.end(), 4);l.insert(++l.begin(), 1);auto pos = ++l.begin();l.insert(pos, 1);print_list(l); // 0 1 1 2 3 4// erasel.erase(l.begin());l.erase(--l.end());pos = l.begin();l.erase(pos);print_list(l); // 1 2 3// swaplist<int> l2;l2.push_back(1);l2.push_back(1);l2.push_back(1);l.swap(l2);cout << "l: ";print_list(l); // l: 1 1 1cout << "l2:";print_list(l2); // l2: 1 2 3// clearl2.clear(); // 虽然有效元素被清空了，但是并不意味着l2为空if (l2.empty()){cout << "l2不为空\n";print_list(l2);}else{cout << "l2为空\n";}
}// findlist<int>::iterator posn = find(l.begin(), l.end(), 3); // find没找到返回l.end()的位置if (posn != l.end()){l.insert(posn, 30); // 在list下这里的posn不会失效，但是vector下就会失效了。}print_list(l);

在使用接口的时候，如果遇到不会的，可以查阅文档

3.list的迭代器失效问题

在讲述list的迭代器失效问题，我们先来看一个例子：

void print_list(const list<int>& l)
{list<int>::const_iterator cit = l.begin();while (cit != l.end()){cout << *cit << " ";++cit;}cout << endl;
}void print_vector(const vector<int>& v)
{vector<int>::const_iterator cit = v.begin();while (cit != v.end()){cout << *cit << " ";++cit;}cout << endl;
}void test1()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator pos1 = find(l.begin(), l.end(), 3);if(pos1 != l.end()){l.insert(pos1, 30);// insert完成后，pos迭代器不会失效。因为他是list结构，vector就会直接崩溃l.erase(pos1);}print_list(l);vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator pos2 = find(v.begin(), v.end(), 3);if (pos2 != v.end()){v.insert(pos2, 30); // insert之后的pos2迭代器失效了。//v.erase(pos2); // vs里直接报错}print_vector(v);
}

在这段代码中，list中使用insert插入数据后的pos1不会在成为失效的迭代器，这是因为list是双向链表的结构，链表的数据是放在一个个结点中的，因此pos1指向的数据不会被移动，也不会改变。

而vector中就会让pos2成为失效的迭代器，**原因是：**1.不增容会导致pos2指向的数据出现错误。2.增容

了会直接导致pos2成为野指针。因为v的地址变动了。具体可以复习vector。STL—容器—vector-CSDN博客这篇博客中有讲述vector的两种迭代器失效的情况。

经过上面的例子分析，我们发现list特殊的双向链表结构导致vector中出现的这种迭代器失效的情况不会在list中出现。

但是list还是存在着迭代器失效的情况。

下面我们就来看看这个情况，在学习vector的时候说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

来看一段代码：

// list的迭代器失效问题
void test2()
{// 只有删除节点的时候会失效int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]));list<int>::iterator it = l.begin();while (it != l.end()){l.erase(it);// 此时的it已经是无效了。因为所指向的节点已经被删除了++it; }print_list(l);
}

正确代码：

void test2()
{// 只有删除节点的时候会失效int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> l(arr, arr + sizeof(arr) / sizeof(arr[0]));list<int>::iterator it = l.begin();while (it != l.end()){l.erase(it++); // 或者是it = l.erase(it);}print_list(l);
}

总结：

list在oj的使用频率没有vector出现的频率那么高，因此这边我们只是简单的使用list的基本接口就足够了，重点是在list的模拟实现上。