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

Question

将一个范围从一个列表拼接到另一个列表可以在恒定的时间内完成,但代价是使size()线性变得复杂.

C++ 11已经改变了,在std::list需要size()恒定时间的情况下.这打破了,例如,gcc的实现,参见[C++ 0x] std :: list :: size complexity.

除了范围之外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 

Answer 1

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

使用整个源列表的版本仍然需要搜索源末尾紧前的节点，以便可以将其修改为指向目标中拼接之后的元素。因此它也需要源大小的线性时间。