Domanda Esiste un modo standard per spostare un intervallo in un vettore?


Considera il seguente programma che inserisce un intervallo di elementi in un vettore:

vector<string> v1;
vector<string> v2;

v1.push_back("one");
v1.push_back("two");
v1.push_back("three");

v2.push_back("four");
v2.push_back("five");
v2.push_back("six");

v1.insert(v1.end(), v2.begin(), v2.end());

Questo copia efficacemente l'intervallo, allocando spazio sufficiente nel vettore di destinazione per l'intero intervallo in modo che sia richiesto un massimo di un ridimensionamento. Considerare ora il seguente programma che tenta di spostare un intervallo in un vettore:

vector<string> v1;
vector<string> v2;

v1.push_back("one");
v1.push_back("two");
v1.push_back("three");

v2.push_back("four");
v2.push_back("five");
v2.push_back("six");

for_each ( v2.begin(), v2.end(), [&v1]( string & s )
{
    v1.emplace_back(std::move(s));
});

Ciò comporta una mossa riuscita, ma non gode dei vantaggi che insert () ha per quanto riguarda la preallocazione dello spazio nel vettore di destinazione, quindi il vettore potrebbe essere ridimensionato più volte durante l'operazione.

Quindi la mia domanda è: esiste un equivalente in fogli che può spostare un intervallo in un vettore?


44
2018-05-23 12:41


origine


risposte:


Tu usi a move_iterator con insert:

v1.insert(v1.end(), make_move_iterator(v2.begin()), make_move_iterator(v2.end()));

L'esempio in 24.5.3 è quasi esattamente questo.

Otterrai l'ottimizzazione che desideri se (a) vector::insert usa l'invio di iterator-tag per rilevare l'iteratore ad accesso casuale e precalcolare la dimensione (che hai assunto che faccia nel tuo esempio che copia), e (b) move_iterator conserva la categoria iteratore dell'iteratore che avvolge (che è richiesto dallo standard).

In un punto oscuro: ne sono abbastanza sicuro vector::insert può emplace dalla sorgente (che è irrilevante qui, dato che la sorgente è dello stesso tipo della destinazione, quindi un emplace è uguale a una copia / mossa, ma sarebbe rilevante per gli esempi altrimenti identici). Non ho ancora trovato una dichiarazione che è richiesto di farlo, l'ho appena dedotto dal fatto che il requisito sulla coppia iteratore i,j passato a insert è questo T essere EmplaceConstructible a partire dal *i.


69
2018-05-23 12:48



  1. std::move algoritmo con preallocazione:

    #include <iterator>
    #include <algorithm>
    
    v1.reserve(v1.size() + v2.size()); // optional
    std::move(v2.begin(), v2.end(), std::back_inserter(v1));
    
  2. Quanto segue sarebbe più flessibile ancora:

    v1.insert(v1.end(), 
         std::make_move_iterator(v2.begin()), 
         std::make_move_iterator(v2.end()));
    

    Steve Jessop ha fornito informazioni di base su esattamente ciò che fa e probabilmente su come lo fa.


32
2018-05-23 12:45