一、前言
list容器，又称为双向链表容器，即该容器的底层是以双向链表的形式实现的，因此list容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
list容器中各个元素的前后顺序是靠指针维系的，每个元素都有两个指针，分别指向它的前一个元素和后一个元素。第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
优点：可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高。
缺点：不能通过下标访问元素，只能从容器中第一个元素或最后一个元素开始遍历容器，直到找到对应元素。
list 容器以模板类 list（T 为存储元素的类型）的形式在头文件中，并位于 std 命名空间中。使用时需包含头文件：
#include
using namespace std;
二、初始化list容器
一共有5种方式创建list容器
①std::list listInt;
②std::list listInt(10);
③std::list listInt(10, 5);
④std::list listInt2(listInt);
⑤//拷贝普通数组，创建list容器
int a[] = { 1,2,3,4,5 };
std::list listInt(a, a+5);
//拷贝其它类型的容器，创建 list 容器
std::array arrInt{ 11,12,13,14,15 };
std::list listInt(arrInt.begin()+2, arr.end());
①创建空的list容器
②创建一个包含10个元素，默认值为0的list容器
③创建一个包含10个元素，初始值为5的list容器
④将以初始化的list容器进行拷贝创建新的list容器，须保证新旧容器存储的元素类型一致
⑤通过拷贝其他类型容器（或者普通数组）中指定区域内的元素，创建 list 容器
1、成员函数
这里不列举迭代器、添加和删除等相关的函数。
| 函数 |
功能 |
| empty() |
判断容器中是否有元素，若无元素，则返回 true；反之，返回 false |
| size() |
返回当前容器实际包含的元素个数 |
| max_size() |
返回容器所能包含元素个数的最大值，一般是 232-1 |
| front() |
返回第一个元素的引用 |
| back() |
返回最后一个元素的引用 |
| assign() |
用新元素替换容器中原有内容 |
| swap(x,y) |
交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的 |
| resize() |
调整容器的大小 |
| splice() |
将一个 list 容器中的元素插入到另一个容器的指定位置 |
| merge() |
合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的 |
| sort() |
通过更改容器中元素的位置，将它们进行排序 |
| reverse() |
反转容器中元素的顺序 |
2、实例
1）、创建list容器
std::list listInt;
listInt.push_back(31);
listInt.push_back(27);
listInt.push_back(29);
std::cout << " listInt size: " << listInt.size() << std::endl;
int i = 0;
std::list::iterator listIter = listInt.begin();
for (;
listIter != listInt.end();
listIter++)
{
std::cout << " listInt[" << i++ << "]=" << *listIter << std::endl;
}listInt.sort();
i = 0;
listIter = listInt.begin();
for (;
listIter != listInt.end();
listIter++)
{
std::cout << " sort listInt[" << i++ << "]=" << *listIter << std::endl;
}int nFront = listInt.front();
int nBack = listInt.back();
std::cout << " listInt front: " << nFront << " back: " << nBack << std::endl;
std::list listInt1{ 14,25,99 };
listInt1.sort();
listInt.merge(listInt1);
i = 0;
listIter = listInt.begin();
for (;
listIter != listInt.end();
listIter++)
{
std::cout << " merge listInt[" << i++ << "]=" << *listIter << std::endl;
}
结果如下：
文章图片
三、迭代器
| 函数 |
功能 |
| begin() |
返回指向容器中第一个元素的双向迭代器（正向迭代器） |
| end() |
返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。（正向迭代器） |
| rbegin() |
返回指向最后一个元素的反向双向迭代器 |
| rend() |
返回指向第一个元素所在位置前一个位置的反向双向迭代器 |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素 |
| cend() |
和 end() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素 |
| crend() |
和 rend() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素 |
具体的功能不再说明，可参考array容器中的说明。list容器的迭代器和之前的array、vector等最大的不同在于：它的迭代器类型为双向迭代器，而不再是随机访问迭代器。
假如p1，p2都是双向迭代器，那么
支持++p1、 p1++、 p1--、 p1++、 *p1、 p1==p2 以及 p1!=p2；
不支持p1[i]、p1-=i、 p1+=i、 p1+i 、p1-i、p1p2、 p1<=p2、 p1>=p2。
1、实例
1）、遍历list容器元素
i = 0;
listIter = listInt.begin();
for (;
listIter != listInt.end();
listIter++)
{
std::cout << " sort listInt[" << i++ << "]=" << *listIter << std::endl;
}
【C++ STL list容器】其他的函数功能和vector等类似，不再说明使用方法
注意点：
1、list 容器不支持随机访问，未提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数
2、 front() 和 back() 成员函数，可以分别获得 list 容器中第一个元素和最后一个元素的引用形式，必要时还能修改其值
3、若希望访问list容器其他位置的元素，只能通过list容器的迭代器，也可以通过迭代器对指定元素的值进行修改
四、插入元素
| 函数 |
功能 |
| push_front() |
向 list 容器首个元素前添加新元素 |
| push_back() |
向 list 容器最后一个元素后添加新元素 |
| emplace_front() |
在容器首个元素前直接生成新的元素 |
| emplace_back() |
在容器最后一个元素后直接生成新的元素 |
| emplace() |
在容器的指定位置直接生成新的元素 |
| insert() |
在指定位置插入新元素 |
| splice() |
将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处 |
1、insert方法
| 格式 |
说明 |
| iterator insert(pos,elem) |
在迭代器 pos 指定的位置之前插入一个新元素 elem，并返回表示新插入元素位置的迭代器 |
| iterator insert(pos,n,elem) |
在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器 |
| iterator insert(pos,first,last) |
在迭代器 pos 指定的位置之前，插入其他容器（例如 array、vector、deque 等）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器 |
| iterator insert(pos,initlist) |
在迭代器 pos 指定的位置之前，插入初始化列表（用大括号 { } 括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器 |
2、splice方法
| 格式 |
说明 |
| void splice (iterator position, list& x);
|
单元 2 |
| 单元 3 |
position 为迭代器，用于指明插入位置；x 为另一个 list 容器。此格式的 splice() 方法的功能是，将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处 |
| void splice (iterator position, list& x, iterator i);
|
position 为迭代器，用于指明插入位置；x 为另一个 list 容器；i 也是一个迭代器，用于指向 x 容器中某个元素。此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。 |
| void splice (iterator position, list& x, iterator first, iterator last);
|
position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域。此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。 |
splice() 成员方法移动元素的方式
将存储该元素的节点从 list 容器底层的链表中摘除，然后再链接到当前 list 容器底层的链表中。当使用 splice() 成员方法将list1容器中的元素添加到list2容器的同时，该元素会从list1容器中删除。
3、实例
这里主要是splice方法的实例
1）、方法1
std::list listInt1{ 16,72,100 }, listInt2{9,201,94};
std::list::iterator listIter = ++listInt1.begin();
**listInt1.splice(listIter, listInt2);
**int i = 0;
std::list::iterator listIter1 = listInt1.begin();
std::list::iterator listIter2 = listInt2.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
for (;
listIter2 != listInt2.end();
listIter2++)
{
std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl;
}
结果如下：
文章图片
2）、方法2
std::list listInt1{ 16,72,100 }, listInt2{9,201,94};
std::list::iterator listIter = ++listInt1.begin();
**listInt2.splice(listInt2.begin(), listInt1, listIter);
**int i = 0;
std::list::iterator listIter1 = listInt1.begin();
std::list::iterator listIter2 = listInt2.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
for (;
listIter2 != listInt2.end();
listIter2++)
{
std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl;
}
结果如下：
文章图片
3）、方法3
std::list listInt1{ 16,72,100 }, listInt2{9,201,94};
std::list::iterator listIter = ++listInt1.begin();
** listInt2.splice(listInt2.begin(), listInt1, listInt1.begin(), listInt1.end());
**int i = 0;
std::list::iterator listIter1 = listInt1.begin();
std::list::iterator listIter2 = listInt2.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " splice1 listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
for (;
listIter2 != listInt2.end();
listIter2++)
{
std::cout << " splice1 listInt2[" << i++ << "]=" << *listIter2 << std::endl;
}
结果如下：
文章图片
五、删除元素
| 函数 |
说明 |
| pop_front() |
删除位于 list 容器头部的一个元素 |
| pop_back() |
删除位于 list 容器尾部的一个元素 |
| erase() |
该成员函数既可以删除 list 容器中指定位置处的元素，也可以删除容器中某个区域内的多个元素。 |
| clear() |
删除 list 容器存储的所有元素 |
| remove(val) |
删除容器中所有等于 val 的元素 |
| unique() |
删除容器中相邻的重复元素，只保留一份 |
| remove_if() |
删除容器中满足条件的元素 |
1、erase
| 格式 |
说明 |
| iterator erase (iterator position);
|
删除 list 容器中 position 迭代器所指位置处的元素 |
| iterator erase (iterator first, iterator last);
|
删除 list 容器中 first 迭代器和 last 迭代器限定区域内的所有元素（包括 first 指向的元素，但不包括 last 指向的元素） |
2、unique
| 格式 |
说明 |
| void unique() |
去除 list 容器中相邻重复的元素 |
| void unique（BinaryPredicate） |
去除 list 容器中相邻重复的元素，仅保留一份 |
3、实例
这里主要是unique()和remove_if()的使用
1）、unique()
std::list listInt1{ 16,72,72,100,72,109,203,671,109,192,671 }, listInt2{9,201,94,43,67,81,901};
**listInt1.unique();
**
int i = 0;
std::list::iterator listIter1 = listInt1.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
结果如下：
文章图片
由结果可知：
①只能比较相邻两个元素，若连续三个或以上元素值相同也适用
bool test(int first, int second)
{
return (first <= second);
}std::list listInt1{ 72,73,100,72,44,48,109,92,671,15,192,671 };
listInt1.unique(test);
int i = 0;
std::list::iterator listIter1 = listInt1.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
结果如下：
文章图片
由结果可知
当执行test返回true时，会删除元素
返回false时，会保留比较的两个元素值
如：{ 72,73,100,72,44,48,109,92,671,15,192,671 }的比较步骤是
①72,73返回true，删除73；72,100返回true，删除100；72,72返回true，删除72
②72,44返回false，保留72,44
③44,48返回true，删除48；44,109返回true，删除109；44,92返回true，删除92；44,671返回true，删除671
④44,15返回false，保留15
⑤15,192返回true，删除192；15,671返回true，删除671
因此最后list中的数据为{72.44.15}
注意：
除了以上谓词函数的方式，还可以使用 lamba表达式以及函数对象的方式定义。
2）、remove_if
std::list listInt1{ 72,73,100,72,44,48,109,92,671,109,15,671 };
listInt1.remove_if([](int nValue) {return nValue < 100;
});
int i = 0;
std::list::iterator listIter1 = listInt1.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
或者
//二元谓词函数
bool test(int nValue)
{
bool bRet =(nValue < 100);
return bRet;
}std::list listInt1{ 72,73,100,72,44,48,109,92,671,109,15,671 };
listInt1.remove_if(test);
int i = 0;
std::list::iterator listIter1 = listInt1.begin();
for (;
listIter1 != listInt1.end();
listIter1++)
{
std::cout << " unique listInt1[" << i++ << "]=" << *listIter1 << std::endl;
}
结果如下：
文章图片
大于等于100的元素值都会被保留
推荐阅读
