7

我想拼接 range [first, last]，包括两个端点。我对元素before first和 to有迭代器last。我可以做到这一点，splice_after()但只能在线性时间内。

我相信这个拼接可以在恒定时间内完成。我该怎么做std::forward_list？

如果问题不清楚，这里是显示我的问题的示例代码：

实时工作空间代码

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;

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

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

    // trg.splice(trg.begin(), src, before_first, last); // no such splice
    auto end = last;
    ++end; // Ouch! splice has to find last again although I already had it  :(
    trg.splice_after(trg.begin(), src, before_first, end);

    cout << "Target after splice:\n";
    copy(trg.begin(), trg.end(), ostream_iterator<char>(cout," "));

    cout << "\nSource after splice:\n";
    copy(src.begin(), src.end(), ostream_iterator<char>(cout," "));

    cout << endl;
}

输出：

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

1 回答 1

6

的规范forward_list说(first, last)应该拼接范围，不幸的是没有办法在 O(1) 时间内做到这一点，因为需要访问来last-1做到这一点，而获得访问权限的唯一方法last-1是从first.

如果规范是拼接 range (first, last]，那么 O(1) 拼接是可能的。我知道没有办法用当前的forward_list规范来实现这一点。

我认为这是一个缺陷。但是我已经尝试过但未能修复它：

http://cplusplus.github.com/LWG/lwg-defects.html#897

然而，过去的问题已经逆转，尤其是当投诉来自非委员会成员（例如您自己）时。提出投诉的方式是打开一个新问题，并在适当的情况下引用任何旧问题或相关问题。打开问题的说明在这里。

PS：关于这个问题的+1。

于 2013-01-05T21:52:59.237 回答