【C++】list的使用

list的底层结构是双向循环链表，在任意位置插入和删除效率很高，但是不支持任意位置的随机访问。

下面来介绍一些常用的list接口：

1 构造

1.1 无参构造

list()

list<int> lt;

1.2 构造的list中包含n个值为val的元素

list (size_type n, const value_type& val = value_type())

list<int> lt(6, 77);

1.3 用[?rst, last)区间中的元素构造list

只要是迭代器都可以在其范围内初始化它的内容

list (InputIterator ?rst, InputIterator last)

	list<int> lt1{ 1,2,3,4,5 };
	list<int> lt2(lt1.begin(), lt1.end());

1.4 拷贝构造

list (const list& x)

	list<int> lt1{ 1,2,3,4,5,6,7 };
	list<int> lt2(lt1);

2 迭代器的使用

2.1 begin + end

返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

list<int> lt{ 1,2,3,4,5,6,7,8,9,10 };
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
	cout << *it << " ";
	++it;
}
cout << endl;

2.2 rbegin + rend

返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

list<int> lt{ 1,22,3,44,5,6,67,8,91,10 };
list<int>::reverse_iterator it = lt.rbegin();
while (it != lt.rend())
{
	cout << *it << " ";
	++it;
}
cout << endl;

3 容量操作

list不需要扩容，它的每个节点是独立的一块空间，根据需求来进行新增节点或者删除节点。

3.1 empty + size

empty :检测list是否为空，是返回true，否则返回false
size:返回list中有效节点的个数

list<int> lt{ 1,2,3,4,5 };
cout << lt.empty() << endl;//0
cout << lt.size() << endl;//5

4 获取元素

4.1 front + back

返回list第一个节点的值和最后一个节点的值

list<int> lt{ 1,2,3,4,5 };
cout << lt.front() << endl;//1
cout << lt.back() << endl;//5

5 插入、删除、修改

5.1 头插-push_front和尾插-push_back

list<int> lt{ 1,2,3,4,5 };
lt.push_front(100);
lt.push_back(1000);
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

5.2 头删-pop_front和尾删-pop_back

list<int> lt{ 1,2,3,4,5 };
lt.pop_front();
lt.pop_back();
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

5.3 交换——swap

	list<int> lt1{ 1,2,3,4,5 };
	list<int> lt2{ 6,7,8,9,10 };
	lt1.swap(lt2);

5.4 清理——clear

清空有效元素，保留哨兵位节点

list<int> lt{ 1,2,3,4,5 };
lt.clear();
lt.push_back(1);
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

5.5 insert-pos位置插入元素

list<int> lt{ 1,2,3,4,5 };
auto pos = find(lt.begin(), lt.end(), 3);
lt.insert(pos, 100);
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

5.6 erase-pos位置删除元素

list<int> lt{ 1,2,3,4,5 };
auto pos = find(lt.begin(), lt.end(), 3);
lt.erase(pos);
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

6 迭代器失效问题

前面的例子中都只是使用一次，如果重复使用可能会出现迭代器失效问题，先来insert。

list<int> lt{ 1,2,3,4,5 };
auto pos = find(lt.begin(), lt.end(), 3);
lt.insert(pos, 100);
lt.insert(pos, 999);

按正常的思路，第一次在3的前面插入100，第二次在100前面插入999，但是：

list的insert不会出现迭代器失效的问题，但是会出现以上的情况，因为pos指向元素为3的节点，第一次插入是3的前面没有问题，但是第二次插入时pos还是指向元素3，所以插入999还是在元素3的前面插入。

恢复正常逻辑，只需要给pos重新赋值即可。

注：insert和erase是可以有返回值的，返回的是迭代器

pos = lt.insert(pos, 100);
lt.insert(pos, 999);

erase重复使用就会出现因迭代器失效而报错的问题了。
先看代码：

list<int> lt{ 1,2,3,4,5 };
auto pos = find(lt.begin(), lt.end(), 3);
lt.erase(pos);
lt.erase(pos);

因为第一次删除pos位置的节点，该节点已经不存在了，第二次删除还是使用上一次的pos，所以会报错。解决方法就是给pos重新赋值

pos = lt.erase(pos);//下一次如果使用，必须重新赋值
lt.erase(pos);//最后一次使用赋不赋值没有关系