为什么为std :: forward_list剪切整个列表或范围线性？

问题描述

将一个范围从一个列表拼接到另一个列表可以在恒定时间内完成，而以 size（）的复杂度为线性。

C ++ 11已通过要求 size（）为恒定时间。这打破了，例如，gcc的实现，请参见 [C ++ 0x] std ::

除了 splice（）还有任何其他原因，因为 size（） 不能在之前的C ++ 03符合 $ c> std :: list 实现？

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

=http://en.cppreference.com/w/cpp/container/forward_list/splice_after =nofollow> splice_after（） ，案例（1）和（3）。另请参见标准草案N3485 中的23.3.4.6 forward_list操作[forwardlist.ops]。 std :: forward_list 甚至不实现 size（）。

我知道forward_list是一个单链表，但我不明白为什么不能做范围 splice_after（）在常量时间。我可能在这里缺少一些小事...

  #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<< '\\\'; }   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 =<< *第一<< ，last =< * last<< \\\\\\;   trg.splice_after（trg.begin（），src，first，last）;   cout<< Target after splice：\\\;  dump_list（trg）;   cout<< Source after splice：\\\;  dump_list（src）;   cout<< endl;  return 0; }   

输出：

  first = 1，last = 4 拼接后目标：a 2 3 bc 拼接后的源： 1 4   

你会使范围splice_after恒定时间吗？在源列表中，您只有迭代器。要从源前向链表中删除节点，您将需要紧接在 last 之前的节点，因此您需要对源链接列表节点进行线性搜索。因此，为什么第一和最后

使用整个源列表的版本仍然需要在源结束之前搜索节点，以便可以将其修改为指向目标中拼接后的元素。因此，它还需要源尺寸的线性时间。

Splicing a range from one list to another can be accomplished in constant time, at the expense of making size()'s complexity linear.

C++11 has changed that in case of std::list by requiring size() to be constant time. This broke, for example, gcc's implementation, see [C++0x] std::list::size complexity.

Apart from the range splice(), is there any other reason why size() could not be made constant time in the earlier, C++03 conforming std::list implementations?

Why is splicing an entire list or a range linear for std::forward_list?

See splice_after(), cases (1) and (3). See also 23.3.4.6 forward_list operations [forwardlist.ops] in the standard draft N3485. The std::forward_list doesn't even implement size().

I know forward_list is a singly linked list but I don't see why one couldn't do the range splice_after() in constant time. I am probably missing something trivial here...

EDIT: OK, It was at least partly my misunderstanding, I expected that 4 would not remain in the source list. Code:

#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;
}

Output:

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

In the case of a forward_list, how would you make the range splice_after constant time? In the source list, you only have the iterators. To remove the nodes from the source forward linked list, you will need the node immediately before last, so you need to search the source linearly for that linked list node. Hence, why it's linear in the distance between first and last

The version that uses the entire source list still needs to search for the node immediately before the end of the source, so that it can be modified to point to the element after the splice in the destination. So it also requires linear time in the size of the source.