std :: unordered_set <T> :: insert (T &&): è un argomento spostato se esiste

Question

Questa domanda riguarda le specifiche di diverse funzioni nella libreria standard C++ 11, che prendono i loro argomenti come riferimenti di valore, ma non consumali in tutti i casi. Un esempio è std::unordered_set<T>::insert(T&&).

È abbastanza chiaro che questo metodo utilizzerà il costruttore di spostamenti di T per costruire l'elemento all'interno del contenitore, se non esiste già. Tuttavia, cosa succede se l'elemento esiste già nel contenitore? Sono abbastanza sicuro che non vi sia alcun motivo per cambiare l'oggetto nel caso. Tuttavia, non ho trovato nulla nello standard C++ 11 che supporta il mio reclamo.

Ecco un esempio per mostrare perché questo potrebbe essere interessante. Il seguente codice legge le righe da std :: cin e rimuove la prima occorrenza delle righe duplicate.

std::unordered_set<std::string> seen; 
std::string line; 
while (getline(std::cin, line)) { 
    bool inserted = seen.insert(std::move(line)).second; 
    if (!inserted) { 
     /* Is it safe to use line here, i.e. can I assume that the 
     * insert operation hasn't changed the string object, because 
     * the string already exists, so there is no need to consume it. */ 
     std::cout << line << '\n'; 
    } 
} 

Apparentemente, questo esempio funziona con GCC 4.7. Ma non sono sicuro, se è corretto secondo lo standard.

Answer 1

Ho trovato questa nota nella norma (17.4.6.9):

[Nota: Se un programma getta un lvalue a un xValue mentre passa che valore assegnabile ad una funzione di libreria (ad esempio chiamando il funzione con l'argomento move(x)), il programma sta effettivamente chiedendo a quella funzione di trattare quel lvalue come temporaneo. L'implementazione è gratuita per ottimizzare i controlli di aliasing che potrebbero essere necessari se l'argomento fosse un lvalue. - end note]

Mentre non risponde direttamente alla tua domanda indica che hai effettivamente "dato" l'argomento alla funzione di libreria come temporaneo quindi non fare affidamento sul suo valore una volta Ho chiamato insert. Per quanto posso dire, un'implementazione di libreria avrebbe il diritto di passare dal parametro anche se successivamente determina che non manterrà il valore nel contenitore.

Answer 2

È corretto.

Naturalmente, quando si ha a che fare con la filosofia, tutto può essere messo in discussione, ma il compilatore deve fare in qualche modo.

La scelta dei progettisti è che -per eseguire un mossa - ci deve essere un posto dove andare . Se non c'è un posto del genere, la mossa non avviene.

Si noti che qualsiasi funzione prende uno & &, si assume che il parametro sia "temporaneo": se non "ruba" i dati, il temporaneo verrà distrutto all'estremità dell'espressione. Se la temporaneità era stata forzata (tramite std :: move), l'oggetto rimarrà in ogni caso lì fino a quando non viene distrutto dal proprio ambito. Con o senza i suoi dati originali all'interno.

Answer 3

La semantica fornita per insert su contenitori associativi non ordinati in §23.2.5/Tabella 103 non specifica se il costruttore spostamento dell'argomento per insert viene richiamato se l'inserimento non riesce, la formulazione parla solo sul fatto che l'inserimento avviene:

a_uniq.insert(t)

Returns: pair<iterator, bool>

Richiede: Se t è un non-const espressione rvalue, T devono essere MoveInsertable in X; altrimenti, T deve essere CopiaInsertable in X.

Effetti: Inserti t se e solo se v'è alcun elemento nel contenitore con tasto equivalente al tasto di t. Il componente bool della coppia restituita indica se l'inserimento di avviene e il componente iteratore punta all'elemento con chiave equivalente alla chiave di t.

Tuttavia, la specifica per emplace è più chiaro (anche dalla Tabella 103), e si dovrebbe essere in grado di usarlo al posto del insert per ottenere le garanzie desiderate:

a_uniq.emplace(args)

Returns: pair<iterator, bool>

richiede: T deve essere EmplaceConstructible in X da args.

Effetti: inserisce un oggetto Tt costruito con std :: avanti (args) ... se e solo se non v'è alcun elemento nel contenitore con tasto equivalente al tasto di t. Il componente booleano della coppia restituita è true se e solo se si verifica l'inserimento e il componente iteratore della coppia punta all'elemento con chiave equivalente alla chiave di t.

Interpreto questo per significare ((inserisce un oggetto Tt costruito ...) (se e solo se non v'è alcun elemento nel contenitore ...)), cioè sia l'inserimento e costruzione dovrebbero succede solo se non ci sono elementi corrispondenti già nel contenitore. Se nessun oggetto è costruito, lo std::string che si passa non verrà mai passato a un costruttore di movimento e pertanto sarà ancora valido dopo la chiamata non riuscita emplace.

gcc 4.7.0 non sembra supportare unordered_set::emplace, ma è nello standard (§23.5.6.1)

Come @NicolBolas sottolineato nei commenti, e nonostante quanto sopra, è impossibile implementare una funzione emplace che non costruire una T se una voce in conflitto esiste già.

Quindi l'unico modo per ottenere la semantica che si desidera in un modo che è standard conformi sarebbe quella di fare un find seguito da, condizionale, un insert o emplace.