我想拼接范围 [first, last]
,包括两个端点。我有元素 before first
和 last
的迭代器。我可以使用 splice_after()
来完成,但只能在线性时间内完成。
我相信这个拼接可以在恒定时间内完成。我如何使用 std::forward_list
完成它?
如果问题不清楚,这里是显示我的问题的示例代码:
Live Work Space 上的代码
#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
最佳答案
forward_list
的规范说应该拼接区间(first, last)
,很遗憾没有办法在O(1)时间内做到这一点,因为需要访问 last-1
才能执行此操作,而访问 last-1
的唯一方法是从 first
向前迭代。
如果规范是拼接范围 (first, last]
,那么 O(1) 拼接是可能的。我知道没有办法用当前的 forward_list 实现这个
规范。
我认为这是一个缺陷。但是我已经尝试过但未能修复它:
然而,问题在过去发生了逆转,尤其是当投诉来自非委员会成员(例如您)时。提出投诉的方法是打开一个新问题,并在适当时引用任何旧问题或相关问题。打开问题的说明是 here .
PS:对这个问题 +1。
关于c++ - 如何使用 std::forward_list 在恒定时间内进行范围拼接?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14170746/