How to do range splice in constant time with std::

Question

I want to splice the range [first, last], with both endpoints inclusive. I have iterators to the element before first and to last. I could do it with splice_after() but only in linear time.

I belive this splice can be done in constant time. How can I do it with std::forward_list?

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

Code on 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;
}

Output:

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

Answer 1

The specification of forward_list says that the range (first, last) should be spliced, and there is unfortunately no way to do this in O(1) time because one needs access to last-1 to do that, and the only way to get access to last-1 is to iterate forward from first.

Had the spec been to splice the range (first, last], then an O(1) splice would be possible. I know of no way to achieve this with the current forward_list spec.

I think it is a defect. However I've already tried and failed to fix it:

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

However issues have been reversed in the past, especially when complaints come in from non-committee members such as yourself. The way to file a complaint is to open a new issue, referencing any old or related issues if appropriate. The instructions for opening an issue are here.

PS: +1 on the question.