Domanda Razionale per la semantica degli inserimenti di mappe std di C ++?


Sono un po 'confuso da std::map::insertLa semantica di s. Voglio dire, non mi lamento - lo standard è lo standard e l'API è così com'è. Ancora,

insert volere

l'operazione di inserimento controlla per ogni elemento inserito se   un altro elemento esiste già nel contenitore con la stessa chiave   valore, se è così, l'elemento non è inserito e il suo valore mappato non lo è   cambiato in alcun modo.

E - solo nella sua versione a argomento singolo pair<iterator,bool> insert ( const value_type& x ); ti dirà anche se ha inserito anche il (nuovo, possibilmente diverso) valore per la (e) chiave (i). Per quanto ho capito, le versioni iterator ignoreranno silenziosamente gli inserimenti se la chiave esiste già.

Per me, questo è semplicemente contro intuitivo, Mi sarei aspettato che la parte del valore venisse sovrascritta e la parte del vecchio valore da scartare sull'inserto. Ovviamente, i progettisti della STL hanno pensato diversamente - qualcuno conosce la logica (storica) o può dare una spiegazione approfondita di come la semantica esistente ha senso (più) senso?

Per esempio:

Esistono alcuni modi di base per implementare l'inserimento in una mappa a chiave singola come std::map:

  • inserire, sostituire se già esiste
  • inserire, ignorare se già esiste (questo è il comportamento di std :: map)
  • inserisci, genera un errore se già esiste
  • inserisci, UB se già esiste

Sto cercando di capire perché insert_or_ignore ha più senso di insert_or_replace (o insert_or_error)!


Ho esaminato la mia copia di TC ++ PL (sfortunatamente ho solo l'edizione tedesca) e, cosa interessante, Stroustrup scrive nel capitolo 17.4.1.7 (elenca le operazioni per carta geografica): (traduzione approssimativa spiacente dal tedesco)

(...) Normalmente, non importa se una chiave (sic!) È nuova   inserito o già esistito prima della chiamata a insert() (...)

Il che, a mio parere, sarebbe valido solo per impostatoe non per carta geografica, perché per una mappa, fa una certa differenza se il valore fornito è stato inserito o il vecchio rimane nella mappa. (Ovviamente non importa per la chiave, dato che quella è equivalente).


Nota: lo so operator[] e so di Articolo 24 di STL efficace e il là proposto efficientAddOrUpdate funzione. Sono solo curioso di una logica in insertLa semantica perché la trovo personalmente contro intuitiva.


24
2018-05-14 14:13


origine


risposte:


Non so su una motivazione ufficiale, ma vorrei notare la dualità con operator[].

Sembra ovvio che uno vorrebbe i due sapori di inserto:

  • puramente additivo
  • additivo / distruttivo

Se vediamo un map come una rappresentazione sparsa di un array, quindi la presenza di operator[] ha senso. Non so se esistessero dizionari preesistenti e dettati questa sintassi (forse, perché no).

Anche, tutti I contenitori STL hanno diversi sovraccarichi di inserte questa similarità delle interfacce è ciò che consente la programmazione generica.

Pertanto, abbiamo almeno due contendenti per l'API: operator[] e insert.

Ora, in C ++, se leggi:

array[4] = 5;

è naturale che il contenuto della cella all'indice 4 è stato aggiornato in modo distruttivo. In quanto tale, è naturale map::operator[] dovrebbe restituire un riferimento per consentire questo aggiornamento distruttivo.

A questo punto, ora abbiamo bisogno anche di una versione puramente additiva, e abbiamo questo insert metodo in giro. Perchè no ?

Ovviamente uno avrebbe potuto dare insert la stessa semantica di operator[] e poi vai avanti e implementa a insert_or_ignore metodo in cima. Questo sarebbe stato più lavoro però.

Pertanto, mentre sono d'accordo che potrebbe essere sorprendente, penso che il mio ragionamento non sia troppo imperfetto e possa essere una probabile spiegazione delle circostanze che ci portano qui :)


Riguardo alle alternative che hai proposto:

  • inserisci, UB se già esiste

Fortunatamente, non lo è!

  • inserisci, genera un errore se già esiste

Solo Java (e derivati) è un'eccezione pazzesca. Il C ++ è stato concepito in un momento in cui venivano utilizzate eccezioni per circostanze eccezionali.

  • inserire, sostituire se già esiste
  • inserisci, ignora se già esiste (questo è il comportamento di std :: map)

Siamo d'accordo che la scelta era tra uno di quelli. Si noti che anche se map eletto la seconda opzione, non completamente ignorare il fatto che l'elemento esistesse già, almeno nella versione a singolo oggetto poiché ti avvisa che l'oggetto non è stato inserito.


5
2018-05-14 15:20



Il metodo di inserimento non è proprio quello che stai cercando, sembra ... Il metodo di inserimento è fatto per fare solo ciò che il nome implica ... inserire valori. Sono d'accordo che la possibilità di creare un valore se uno non è già presente e sostituire quello che è lì altrimenti è importante in alcune situazioni, ma in altri si preferirebbe davvero non gestire le eccezioni, i valori di ritorno, ecc se si vuoi fare un inserimento solo se il valore non è già presente.

Sembra che il metodo che stai cercando (come indicato da BoBTFish sopra) sia probabilmente il [] operatore. Basta usarlo in questo modo:

myMap["key"] = "value";

Questo attraverserà la tua mappa e troverà la chiave "chiave", e sostituirà il valore corrispondente con "valore". Se la chiave non è lì, la creerà. Entrambi i metodi sono molto utili in diverse situazioni e mi sono trovato ad usare entrambi solo in base a ciò di cui ho bisogno.


7
2018-05-14 14:33



Non pretendo di conoscere la logica originale per la decisione, ma non è troppo difficile da inventare. Credo ;-)

L'attuale comportamento di "insert o ignore" rende molto facile implementare gli altri due - almeno per quelli di noi che non sono sopra la creazione e l'uso di funzioni non membri per integrare la funzionalità di libreria standard ("non è OOP- abbastanza! ").

Esempio (scritto sul posto, quindi possono essere presenti errori):

template<typename Map>
void insert_or_update(Map& map, typename Map::value_type const& x)
{
  std::pair<typename Map::iterator, bool> result = map.insert(x);
  if (!result.second)
    result.first->second = x.second; // or throw an exception (consider using
                                     // a different function name, though)
}

Si noti che, come è, la funzione di cui sopra non differisce molto da molto operator[] - sì, evita l'inizializzazione di default, ma allo stesso tempo (perché sono pigro) non riesce a capitalizzare sulla semantica del movimento che il vostro STL aggiornato probabilmente già supporta per operator[].

In ogni caso, qualsiasi altro comportamento di inserimento per map avrebbe reso più noioso implementare gli altri, come map::find restituisce una sentinella finale solo se la chiave non è già presente nella mappa. Con l'aiuto di <algorithm> (e specialmente lower_bound) sarebbe, naturalmente, ancora possibile scrivere funzioni accessorie performanti senza affogarle dettagli di implementazione e brutti costrutti generici come loop ;-).


2
2018-05-19 16:37



A partire dal insert() non ti aspetti che gli oggetti esistenti nel contenitore vengano toccati. Ecco perché è semplice non toccarli.


0
2018-05-14 14:25



pair<iterator,bool> <- la parte bool non dice se l'inserimento ha successo o no?

È possibile aggiornare la parte del valore dell'iteratore restituito solo se la parte bool è falsa per aggiornare l'elemento esistente con la stessa chiave.


0
2018-05-14 14:33