STL双链表容器list ++++++++++++++++++++++ ``list`` 是STL容器的一种，它是一个双向链表，要使用 ``list`` 容器需要先引入 ``list`` 库，并使用 ``std`` 命名空间。 ``list`` 容器同样是一个线性表类型的容器，所以很多用法和规则都和 ``vector`` 容器类似，也使用左闭右开区间来定义其中一段元素的范围。下表列出了和 ``vector`` 容器相同的一些常用成员函数和运算： +--------------------+-----------------------------------------------------------+ | 成员函数 | 功能 | +====================+===========================================================+ | 构造器 | 构造一个 ``list`` 容器的变量（对象） | +--------------------+-----------------------------------------------------------+ | ``operator=`` | ``list`` 变量之间的相互赋值 | +--------------------+-----------------------------------------------------------+ | ``begin()`` | 获取头部迭代器，指向首元素 | +--------------------+-----------------------------------------------------------+ | ``end()`` | 获取尾部迭代器，指向尾元素的后一个位置 | +--------------------+-----------------------------------------------------------+ | ``empty()`` | 判断 ``list`` 是否为空 | +--------------------+-----------------------------------------------------------+ | ``size()`` | 获取 ``list`` 的长度 | +--------------------+-----------------------------------------------------------+ | ``front()`` | 获取首元素的引用 | +--------------------+-----------------------------------------------------------+ | ``back()`` | 获取尾元素的引用 | +--------------------+-----------------------------------------------------------+ | ``push_back()`` | 在尾部添加一个元素 | +--------------------+-----------------------------------------------------------+ | ``pop_back()`` | 删除尾部元素 | +--------------------+-----------------------------------------------------------+ | ``insert()`` | 使用迭代器指定位置插入元素 | +--------------------+-----------------------------------------------------------+ | ``erase()`` | 使用迭代器指定位置删除元素 | +--------------------+-----------------------------------------------------------+ | ``swap()`` | 和另一个 ``list`` 交换内容 | +--------------------+-----------------------------------------------------------+ | ``clear()`` | 清空所有元素 | +--------------------+-----------------------------------------------------------+ | ``assign()`` | 批量赋值，可使用迭代器指定赋值范围 | +--------------------+-----------------------------------------------------------+ | 比较运算 | 按字典序比较两个 ``list`` 大小的六种比较运算 | +--------------------+-----------------------------------------------------------+ | ``swap(x, y)`` | 非成员函数版交换两个 ``list`` 的内容 | +--------------------+-----------------------------------------------------------+ 上表所列的函数和运算符的用法和 ``vector`` 完全相同，所以不再一一举例细说，有不清楚的可以回到 :ref:`ref_311_vector` 一节回顾一下。接下来重点讲一讲和 ``vector`` 容器不同的地方和 ``list`` 特有的几种用法。 首先，和 ``vector`` 容器最大的不同在于 ``list`` 容器不支持使用下标访问元素。如果我们有一个 ``list`` 容器的变量 ``a``\ ，我们不能使用 ``a[i]`` 这样的方式通过一个整数下标值 ``i`` 来访问 ``a`` 中的元素。这是因为通过下标值随机访问链表元素是低效操作，是不鼓励的，所以STL库干脆就不提供这种操作。 但是 ``list`` 提供了在表头处插入删除元素的功能，这是 ``vector`` 所不具备的，因为在顺序表的表头处增删元素也属于低效操作，是不被鼓励使用的。 **表头增删元素** .. code-block:: c++ void push_front (const value_type& val); // 在表头处增加元素，元素值为val void pop_front(); // 删除表头元素 这两个函数的用法和在表尾增删元素的 ``push_back()``\ 、\ ``pop_back()`` 两个函数完全相同，只是操作位置在表头处而已，插入和删除的都是首元素。 除此之外，\ ``list`` 还提供了以下一些自己特有的成员函数，都非常实用。 **切片转移** 成员函数 ``splice()`` 可以用来将另一个 ``list`` 中的全部或一段元素切片出来并插入到自己一个由迭代器指定的位置处，即插入到该迭代器所指向的元素之前，转入完成之后，另一个 ``list`` 中被切片出来的元素会被从表中删除，所以这个操作叫做切片和转移。 ``splice()`` 函数有三个重载版本： .. code-block:: c++ void splice(iterator position, list& x); // 整表转入 void splice(iterator position, list& x, iterator i); // 单个元素转入 void splice(iterator position, list& x, iterator first, iterator last); // 指定范围转入 三种版本都是将另一个链表中的全部或部分元素转入到迭代器 ``position`` 所指的位置处，即在 ``position`` 所指元素之前，如果迭代器 ``position`` 等于当前链表的尾迭代器 ``end()`` 那么就是链接到表后。 第一个版本转入参数 ``x`` 这个链表中的所有元素；第二个版本转入 ``x`` 中迭代器 ``i`` 所指的那个元素；第三个版本转入 ``x`` 中由前后两个迭代器所指的范围 ``[first, last)`` 中的一段元素，注意是左闭右开区间。 这里，调用者链表自身甚至可以和参数 ``x`` 是同一个链表，只要插入位置参数 ``position`` 不等于要转移的元素位置参数 ``i``\ （版本二）或不在要转移的范围参数 ``[first, last)`` 中（版本三）即可。这么做的时候，就相当于将调用者链表自身中的某一个或某一段元素移动位置。当然在使用版本一的时候，调用者自身和参数 ``x`` 是同一个链表就没有意义了。 **按条件删除元素** ``list`` 容器支持按条件删除元素的操作，共有两种，一种是删除等于某个特定值的所有元素，另一种是删除符合某个特定条件的所有元素： .. code-block:: c++ void remove (const value_type& val); // 删除等于val的元素 void remove_if (Predicate pred); // 删除符合条件pred的元素 注意，这两个成员函数会删除调用者链表中所有符合要求的元素，而不是仅删除一个。 删除等于某个特定值 ``val`` 的元素这个操作很好理解，删除符合某个特定条件 ``pred`` 的所有元素就有点奇怪了。首先，参数 ``pred`` 的数据类型 ``Predicate`` 到底是个什么东西？其次，我们要用什么方式来表示这个条件参数？ 其实很简单，这个所谓的 ``Predicate`` 类型无非是指一个以此链表的元素类型为参数类型的单参数函数，一般建议参数传引用，函数的返回类型为 ``bool``\ ，表示是否符合条件。这和我们以前见过的使用自定义比较函数的算法库排序函数非常类似。请看下面这个例子，在一个链表中先后删除所有的个位数和所有的奇数： .. code-block:: c++ #include #include // 条件判断函数1：判断是否为个位数 bool single_digit(const int& value) { return (value<10); } // 条件判断函数2：判断是否为奇数 bool is_odd(const int& value) { return (value%2)==1; } int main() { int myints[] = {15,36,7,17,20,39,4,1}; std::list mylist(myints, myints + 8); // 15 36 7 17 20 39 4 1 mylist.remove_if(single_digit); // 15 36 17 20 39 mylist.remove_if(is_odd); // 36 20 std::cout << "mylist contains:"; for (std::list::iterator it=mylist.begin(); it!=mylist.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } 运行后的输出为： .. code-block:: none mylist contains: 36 20 **单值化** 所谓单值化就是指删除具有相同值的元素，只保留其中一个。链表的成员函数 ``unique()`` 实现单值化操作，具有两个版本： .. code-block:: c++ void unique(); void unique(BinaryPredicate binary_pred); 第一个版本没有任何参数，单纯地用默认方式比较两个元素的值是否相等，因此需要元素的数据类型支持相等比较运算 ``==``\ 。例如所有内置数据类型、所有的自定义结构类型、C++ string和所有的STL容器都支持 ``==`` 运算。 第二个版本需要提供一个自定义的相等比较函数，用来支持具有某些特殊规则的相等比较。事实上，和 ``remove_if()`` 函数的条件函数类似，这里的参数 ``BinaryPredicate binary_pred`` 实际上也就是一个返回类型为 ``bool`` 的函数，不同的是它需要接收两个与链表元素同类型的参数。 例如我们用一个自定义结构 ``Point`` 来表示平面上的点，结构中保存点的横纵两个坐标值，我们定义一个链表 ``points`` 并随后在其中存放了多个点。 .. code-block:: c++ struct Point { double x, y; }; list points; 现在我们要对 ``points`` 中的点进行去重处理，规则是所有到原点距离相等的点视为相等。我们知道，自定义结构的 ``==`` 运算是比较所有成员变量的值，如果都相等就认为相等。所以我们如果单纯地调用 ``points.unique()`` 来进行去重将会去除所有完全相同的重复点，而不是到原点距离相等的点。这里我们就要用到自定义的等值判断函数了，利用勾股定理很容易写出判断两个点到原点的距离是否相等的判断函数： .. code-block:: c++ bool same_dist(Point &p1, Point &p2) // 判断距离相等不需要开根号出来哦 { return p1.x * p1.x + p1.y * p1.y == p2.x * p2.x + p2.y * p2.y; } points.unique(same_dist); // 等距去重 但是要千万注意，\ ``unique()`` 函数的单值化去重规则是：:emphasis:`每一个元素仅和它的前驱进行比较`\ 。这就意味着，如果等值元素不是全部紧挨着连在一起的，就不能被正确的单值化！ .. warning:: 使用 ``unique()`` 函数进行单值化处理，链表本身必须是有序的，或至少所有等值元素都是排列在一起的！对乱序的链表调用 ``unique()`` 函数毫无意义！ 若使用自定义等值规则判断函数的，那么链表本身也必须是按照这个自定义的比较规则有序的，或能确保所有会被判断为等值的元素都排列在一起。 **归并** ``list`` 容器支持链表归并操作，通过成员函数 ``merge()`` 进行归并，具有以下两个版本： .. code-block:: c++ void merge(list& x); // 使用元素类型默认的小于运算(<)进行归并 void merge(list& x, Compare comp); // 归并时使用自定义比较函数comp进行元素大小比较 和上一节我们介绍过的单链表归并类似，两个 ``list`` 的归并也需要作为调用者的原链表和要归并进来的链表 ``x`` 本身已经是元素有序的，否则归并就会出问题。归并完成之后，链表 ``x`` 会被清空，其中所有元素都被插入到调用者链表的合适位置上。 与算法库排序函数的自定义比较函数一样，这里第二种重载版本的 ``comp`` 参数也应该是一个这样的函数：返回类型为 ``bool``\ ，接受两个与链表中元素同类型的参数，当第一个参数应该排在第二个参数之前（先于或视同为小于）时返回 ``true``\ ，否则返回 ``false``\ 。 **排序** 不知道为什么 ``list`` 容器本身提供了一个用于排序的成员函数 ``sort()``\ ，不出意外，这个函数也有(1)使用默认的小于运算和(2)使用一个自定义比较函数这样两个版本： .. code-block:: c++ void sort(); // 使用元素类型默认的小于运算(<)进行排序 void sort(Compare comp); // 使用自定义先于比较函数comp进行排序 这两个成员函数的使用说明就不赘述了，请自行测试一下即可。这里只说明两点：1、这个函数实现的是稳定排序；2、时间复杂度为 :math:`O(n\log n)`\ 。 **反转** ``list`` 还提供了一个反转自身所有元素的顺序的成员函数 ``reverse()``\ ： .. code-block:: c++ void reverse(); // 元素顺序全部反转 这个就不多解释了，请自行体验一下即可。如果有时候不知道怎样对链表进行元素降序的排序，那么用普通的升序排序排完再反转一下也未尝不可。因为 ``reverse()`` 的时间复杂度为 :math:`O(n)`\ ，而 ``sort()`` 则为更高阶的 :math:`O(n\log n)`\ ，从时间复杂度的上限来看，先排序后反转也并没有增加整个过程的阶，:math:`O(n)+O(n\log n)` 仍然是 :math:`O(n\log n)`\ 。 .. admonition:: 练习 利用 ``list`` 构造一个链表来解决约瑟夫问题，也称为猴子选大王问题。问题如下： 约瑟夫问题：有 :math:`n` 只猴子，编号为 :math:`1,2,\dots,n`\ ，按顺时针方向围成一圈选大王，从第1号猴子开始报数，一直数到 :math:`m`\ ，数到 :math:`m` 的猴子退到圈外，接下来从刚才退出的那只猴子的下一只开始继续从1开始报数到 :math:`m`\ 。就这样不断继续下去，直到圈内只剩下一只猴子时，这个猴子就是猴王。 给定 :math:`n,m`\ ，要求编程求出猴王的编号。 输入数据：用空格分开的两个整数 :math:`n` 和 :math:`m`\ 其中 :math:`0 \lt m, n \le 1,000,000`\ 。 输出要求：一个整数，即猴王的编号。 输入样例： .. code-block:: none 6 2 输出样例： .. code-block:: none 5 .. attention:: 无论是什么STL容器，是 ``vector`` 也好、``list`` 也好，还是任何今后要学到的其他容器，在使用成员函数 ``erase()`` 删除掉一个迭代器所指向的元素后，这个迭代器就会失效。假如我们运行下面的代码片段： .. code-block:: c++ list monkeys; list::iterator it; // ... monkeys.erase(it); 在这一句删除语句之后，迭代器 ``it`` 会失效，变成无效迭代器，不能继续使用。但是一般我们都希望在进行这样的删除之后，\ ``it`` 能变成指向被删除元素的后继元素的迭代器，这是一种最自然的效果。要想达到这样的效果很简单，我们只需要这样调用： .. code-block:: c++ it = monkeys.erase(it); ``erase()`` 成员函数会把被删除元素的后继的迭代器作为返回值返回出来，所以我们只要这样简单的接收它就可以了。