Come eseguire la giunzione in serie in tempo costante con std :: forward_list?

Question

Desidero unire l'intervallo [first, last], con entrambi gli endpoint inclusi. Ho degli iteratori per l'elemento prima dellofirst e last. Potrei farlo con splice_after() ma solo in tempo lineare.

Credo che questa giuntura possa essere eseguita in tempo costante. Come posso farlo con std::forward_list?

Se la questione non è chiara, qui come è un codice di esempio che mostra il mio problema:

Codice in 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; 
} 

uscita:

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

Answer 1

La specifica di forward_list afferma che il range (first, last) deve essere giuntato, e purtroppo non c'è modo di farlo in O (1) perché è necessario accedere a last-1 per farlo, e l'unico modo per ottenere l'accesso a last-1 è iterare in avanti da first.

Se la specifica fosse stata giunta a unire l'intervallo (first, last], sarebbe possibile una giunzione O (1). Non conosco alcun modo per raggiungere questo obiettivo con l'attuale specifica forward_list.

Penso che sia un difetto. Comunque ho già provato e non è riuscito a risolvere il problema:

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

Tuttavia le questioni sono state invertite in passato, soprattutto quando le denunce arrivano da paesi non membri della commissione come te. Il modo per presentare un reclamo è aprire un nuovo problema, facendo riferimento a eventuali problemi precedenti o correlati, se necessario. Le istruzioni per l'apertura di un problema sono here.

PS: +1 sulla domanda.