Wie man Bereich Spleißen in konstanter Zeit mit std :: forward_list tun?

Question

Ich möchte den Bereich [first, last] spleißen, mit beiden Endpunkten inklusive. Ich habe Iteratoren für das Element vorfirst und last. Ich könnte es mit splice_after() aber nur in linearer Zeit tun.

Ich glaube dieser Spleiß kann in konstanter Zeit erfolgen. Wie kann ich es mit std::forward_list machen?

Wenn die Frage nicht klar ist, hier als ein Beispiel-Code zeigt mein Problem:

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

Ausgang:

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

Answer 1

Die Spezifikation von forward_list sagt, dass der Bereich (first, last) sollte gespleißt werden, und es gibt leider keine Möglichkeit, dies in O (1) -Zeit zu tun, da man Zugriff aufbenötigt, um dies zu tun, und die einzige Möglichkeit, Zugriff auf last-1 erhalten, ist von first iterate vorwärts.

Hätte es die Spezifikation, den Bereich (first, last] zu spleißen, dann wäre ein O (1) -Spleiß möglich. Ich kenne keine Möglichkeit, dies mit der aktuellen forward_list Spezifikation zu erreichen.

Ich denke, es ist ein Fehler. Ich habe aber schon versucht und sind gescheitert, es zu beheben:

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

jedoch Probleme in der Vergangenheit umgekehrt worden, vor allem, wenn Beschwerden kommen von Nicht-Ausschussmitglieder wie dich selbst. Der Weg, eine Beschwerde einzureichen, besteht darin, ein neues Problem zu öffnen, das gegebenenfalls auf alte oder verwandte Probleme verweist. Die Anweisungen zum Öffnen eines Problems lauten here.

PS: +1 auf die Frage.