10

可以在恒定时间内完成从一个列表到另一个列表的拼接，但代价是使size()' 的复杂性呈线性。

C++11std::list通过要求size()恒定时间改变了这一点。例如，这破坏了 gcc 的实现，请参阅[C++0x] std::list::size complex。

除了 range 之外splice()，还有什么其他原因 size() 不能在早期的符合 C++03 的 std::list 实现中设为恒定时间吗？

为什么拼接整个列表或范围是线性的 std::forward_list？

参见splice_after()案例 (1) 和 (3)。另见标准草案 N3485中的 23.3.4.6 forward_list 操作 [forwardlist.ops] 。std::forward_list甚至没有size()实现。

我知道 forward_list 是一个单链表，但我不明白为什么不能splice_after()在恒定时间内完成该范围。我可能在这里遗漏了一些微不足道的东西......

编辑：好的，至少部分是我的误解，我预计 4不会保留在源列表中。代码：

#include <algorithm>
#include <iostream>
#include <forward_list>

using namespace std;

void dump_list(const forward_list<char>& l) {
    for(char c : l)
        cout << c << ' ';
    cout << '\n';
}

int main()
{
    forward_list<char> trg = {'a','b','c'};
    forward_list<char> src = {'1','2','3','4'};

    auto first = src.begin();
    auto last  = find(src.begin(), src.end(), '4');
    cout << "first = " << *first << ", last = " << *last << "\n\n";

    trg.splice_after(trg.begin(), src, first, last);

    cout << "Target after splice:\n";
    dump_list(trg);

    cout << "Source after splice:\n";
    dump_list(src);

    cout << endl;
    return 0;
}

输出：

first = 1, last = 4
Target after splice:
a 2 3 b c
Source after splice:
1 4
4

2 回答 2

2

在 forward_list 的情况下，如何使范围 splice_after 保持恒定时间？在源列表中，您只有迭代器。要从源正向链表中删除节点，您将需要紧接在之前的节点last，因此您需要在源中线性搜索该链表节点。first因此，为什么它在和之间的距离上是线性的last

使用整个源列表的版本仍然需要搜索紧接在源末尾之前的节点，这样就可以修改为指向目标中拼接后的元素。所以它还需要源大小的线性时间。

于 2013-01-04T14:41:29.873 回答
1

size范围拼接是在以前的 C++ 标准中不是恒定时间的唯一原因。事实上，Sun CC 编译器选择了使size常数时间和所有版本的splice线性。

拼接整个前向列表是线性的，因为您必须遍历要合并的列表才能将其最后一个节点链接回您要拼接的列表。我无法弄清楚为什么范围拼接是线性的。

编辑：正如@Xeo 指出的那样，基于范围的版本也需要线性时间，因为last它不包含在范围内，它需要搜索 fromfirst 以找到before last的迭代器。

于 2013-01-04T15:11:35.273 回答