29

我有一些处理各种 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()），并且消息来源表明这是因为迭代器提前。我可以忍受这个，但我一直希望不断的复杂性。

我的假设（在我找到这个来源之前）是 splice 函数做这样的事情：

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

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

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

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

4

1 回答 1

33

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

Before C++11, many implementations made size linear time and splice between different lists constant time. C++11 now requires that size be constant and splice be linear.

The problem is that, if the length of the spliced range isn't counted one-by-one, then the containers cannot keep track of how many elements were removed and added, and the next call to size would need to recover this information in O(N) time — using the larger N of the entire sequence, not just the spliced part.

A non-standard list container can supply the desired operation, because so long as you don't need O(1) size, your argument is correct.

As for other libraries… I'm not aware of one, but Boost should have one. (I checked, it doesn't, so someone go get started!) Since you clearly understand how to write your own, doing so might be less effort than contending with such a large library as Qt.

If you don't need thread safety, you could implement a wrapper around std::list in which each container only owns a subrange of a singleton list. This would eliminate most of the programming effort in replicating the standard interface.

于 2012-04-13T03:30:49.127 回答