How to bind a range in constant time using std :: forward_list?

Question

I want to combine the range of [first, last] , including both end points, inclusive. I have iterators to the first and last element. I could do this with splice_after() , but only in linear time.

I believe that this splicing can be done in constant time. How to do this with std::forward_list ?

If the question is not clear, here is an example code showing my problem:

Live Workspace Code

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

Conclusion:

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

Answer 1

The forward_list specification states that the range (first, last) must be spliced, and, unfortunately, there is no way to do this within O (1), because this requires access to last-1 , and this is the only way to access last-1 - iterate forward from first .

If spec were for splicing the range (first, last] , then splice combining (1) is possible. I don't know how to do this with the current forward_list specification.

I think this is a defect. However, I already tried and could not fix it:

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

However, in the past, problems have been canceled, especially when complaints come from unskilled members like you. The way to file a complaint is to open a new problem, referring to any old or related problems, if necessary. Instructions for opening the problem are here .

PS: +1 to the question.