c++ - std::list::splice 和其他列表容器的复杂性

Question

我有一些处理各种 std::list 对象的代码，我目前正在使用一种非常低效的方法在它们之间传输内容(我正在遍历一个列表的任意部分，并一个一个地移动元素进入第二个列表)。我在知道 std::list::splice 函数之前写了这段代码，现在我打算用它替换我的代码，例如:

list<string> list1, list2;

list1.push_back("a");
list1.push_back("b");
list1.push_back("c"); // list1: "a", "b", "c"

list<string>::iterator iterator1 = list1.begin();
iterator1++: // points to "b"

list2.push_back("x");
list2.push_back("y");
list2.push_back("z"); // list2: "x", "y", "z"

list<string>::iterator iterator2 = list2.begin();
iterator2++; // points to "y"

list1.splice(iterator1, list2, iterator2, list2.end());

// list1: "a", "y", "z", "b", "c"
// list2: "x"

我对拼接函数的复杂性有疑问。根据这个来源:

http://www.cplusplus.com/reference/stl/list/splice/

它应该在被拼接的第一个和最后一个元素之间的范围内具有线性复杂性(在我的示例中为 iterator2 和 list2.end())，并且消息来源表明这是因为迭代器提前。我可以忍受这一点，但我一直希望不断复杂。

我的假设(在我找到这个来源之前)是拼接函数做了这样的事情:

1. 切断“x”和“y”之间的链接
2. 切断 "z"和 list2.end() 之间的链接
3. 在 "x"和 list2.end() 之间形成一个链接
4. 切断“a”和“b”之间的链接
5. 在“a”和“y”之间形成链接
6. 在“y”和“b”之间形成链接

从而将两个列表恢复为完整的链。

同样的原则将适用于任意大小的列表。我不确定在哪里需要 splice 函数来推进任何迭代器，因为我为它提供了完成工作所需的所有迭代器。

所以我的问题是，C++ 规范如何处理这个问题？它是仅在接头的起点和终点断开并重新形成链接，还是一个接一个地通过每个链接？如果是后者，是否有任何其他列表容器(例如来自 QT)提供前者？我的代码位于模拟程序的内部循环中，因此赋予它恒定而不是线性复杂度将非常有值(value)。

Answer 1

这是 C++11 标准化过程中一个非常有争议的话题。问题是所有标准容器，包括列表，也有一个恒定时间的 size 操作。

在 C++11 之前，许多实现使 size 线性时间和不同列表之间的 splice 恒定时间。 C++11 现在要求 size 为常数，splice 为线性。

问题是，如果拼接范围的长度不是一个一个计算，那么容器就无法跟踪删除和添加了多少元素，以及下一次调用 size 需要在 O(N) 时间内恢复此信息 - 使用整个序列中较大的 N，而不仅仅是拼接部分。

非标准的 list 容器可以提供所需的操作，因为只要您不需要 O(1) size，您的论点就是正确的。

至于其他库...我不知道有一个，但 Boost 应该有一个。 (我查了一下，没有，所以有人开始吧!)既然你清楚地知道如何编写你自己的，这样做可能比与 Qt 这么大的库竞争更省力。

如果您不需要线程安全，您可以在 std::list 周围实现一个包装器，其中每个容器只拥有一个单例列表的子范围。这将消除复制标准接口(interface)的大部分编程工作。