问题描述
我有一些代码处理各种std :: list对象，我目前使用一个非常低效的方法在它们之间传输内容（我通过一个列表的任意部分迭代，并逐个移动元素到第二列表中）。在我意识到std :: list :: splice函数之前，我写了这个代码，我现在打算替换我的代码，例如：
I have some code which deals with various std::list objects, and I am currently using a very inefficient method of transferring content between them (I'm iterating through arbitrary sections of one list, and moving the elements one by one into the second list). I wrote this code some time ago before I was aware of the std::list::splice function, which I now intend to replace my code with, for example:
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"
我有一个关于拼接函数的复杂性的问题。根据此来源：
I have a question regarding the complexity of the splice function. According to this source:
它应该在拼接的第一个和最后一个元素之间的范围内具有线性复杂度在我的例子中的iterator2和list2.end（），并且源建议这是因为迭代器提前。我可以生活在这里，但我一直希望不断的复杂性。
It should have linear complexity in the range between the first and last elements being spliced in (iterator2 and list2.end() in my example), and the source suggests that this is because of iterator advance. I can live with this but I had been hoping for constant complexity.
我的假设（在我找到这个源之前）是splice函数做这样的： p>
My assumption (before I found this source) was that the splice function do something like this:
- 切断x和y之间的链接
- 切换z list2.end（）
- 在x和list2.end（）之间形成链接
- 切换a和b
- 在a和y之间建立连结
- 在「y」和「b」之间建立连结
- Sever the link between "x" and "y"
- Sever the link between "z" and list2.end()
- Form a link between "x" and list2.end()
- Sever the link between "a" and "b"
- Form a link between "a" and "y"
- Form a link between "y" and "b"
因此将两个列表还原为完整链。
Thus restoring both lists to complete chains.
任意大小。我不知道我看到有什么需要splice函数来推进任何迭代器，因为我提供它所需要的所有迭代器它需要做的工作。
The same principle would then apply to lists of arbitrary size. I'm not sure I see where there is the need for the splice function to advance any iterators, since I am providing it with all the iterators it needs to do it's job.
所以我的问题是，C ++规范如何处理这？它是否仅在接头的起点和终点处断开和重新形成链路，或者它是否逐个通过每个链路前进？如果后者，做任何其他列表容器（例如从QT）提供前者？我的代码驻留在一个模拟程序的内循环中，所以赋予它的常数而不是线性复杂度是非常有价值的。
So my question is, how does the C++ specification deal with this? Does it break and re-form the links only at the start and end points of the splice, or does it advance through each link one by one? If the latter, do any other list containers (e.g. from QT) provide the former? My code resides inside the inner loop of a simulation program, so giving it constant rather than linear complexity would be quite valuable.
推荐答案
在C ++ 11的标准化过程中，这是一个非常有争议的话题。问题是所有标准容器，包括列表，也都有一个恒定时间 size 操作。
This was a very contentious topic during the standardization of C++11. The problem is that all standard containers, including lists, also have a constant-time size operation.
++ 11，许多实现在不同列表之间做了 size 线性时间和 splice 常量时间。 C ++ 11现在要求 size 为常量， splice 为线性。
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.
问题是，如果拼接范围的长度不是一个一个地计数，那么容器不能跟踪删除和添加多少个元素，并且下一次调用 size 需要在O（N）时间内恢复此信息 - 使用整个序列的较大的N，而不仅仅是拼接的部分。
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.
一个非标准的列表容器可以提供所需的操作，因为只要你不需要O（1） size
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.
对于其他库...我不知道一个，但Boost 应该有一个。 （我检查，它不，所以有人去开始！）由于你清楚地了解如何写自己的，这样做可能比竞争如Qt这样的大图书馆的努力。
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.
如果你不需要线程安全，你可以在 std :: list 中实现一个包装，其中每个容器只拥有一个单例的子范围列表。这将消除复制标准接口的大部分编程工作。
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.
这篇关于std :: list :: splice和其他列表容器的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！