Qual è l'interfaccia per l'uso dei bucket in std :: unordered_map?

Question

Ho guardato questo video da CppCon 2014 e discovered che esiste un'interfaccia per accedere ai bucket al di sotto di std::unordered_map. Ora ho un paio di domande:

• Esistono esempi ragionevoli di utilizzo di questa interfaccia?
• Perché il comitato ha deciso di definire questa interfaccia, perché la tipica interfaccia del contenitore STL non era sufficiente?

Answer 1

Spesso è illuminante per cercare la proposta che introduce un elemento, in quanto v'è spesso una logica di accompagnamento. In questo caso N1443 dice questo:

G. benna interfaccia

Come tutti i contenitori standard, ognuno dei contenitori hash ha funzione membro iniziare() e di fine(). L'intervallo [c.begin(), c.end()) contiene tutti gli elementi nel contenitore, presentati come intervallo piatto. elementi all'interno di un secchio sono adiacenti, ma l'interfaccia iteratore presenta nessuna informazione riguardo un secchio e il successivo comincia.

È anche utile per esporre la struttura secchio, per due motivi. In primo luogo, consente agli utenti di valutare l'efficacia della loro funzione hash : consente loro di testare la distribuzione uniforme degli elementi all'interno dei bucket e di controllare gli elementi all'interno di un bucket per vedere se hanno proprietà comuni. In secondo luogo, se gli iteratori hanno una struttura segmentata sottostante (come nelle esistenti implementazioni di elenchi con collegamento ), gli algoritmi che sfruttano tale struttura, con un ciclo nidificato esplicito , possono essere più efficienti degli algoritmi che visualizzano gli elementi come gamma piatta.

La parte più importante dell'interfaccia del bucket è un sovraccarico di begin() e end(). Se n è un numero intero, [begin (n), end (n)) è un intervallo di iteratori che puntano agli elementi nell'nimo bucket. Queste funzioni membro restituiscono iteratori, ovviamente, ma non di tipo X :: iterator o X :: const_iterator. Invece restituiscono iteratori di tipo X :: local_iterator o X :: const_local_iterator. Un iteratore locale è in grado di eseguire all'interno di un bucket, ma non necessariamente tra bucket; in alcune implementazioni è possibile per X :: local_iterator di essere una struttura di dati semplice di X :: iterator. X :: iterator e X: local_iterator può essere dello stesso tipo; le implementazioni che utilizzano elenchi doppiamente collegati probabilmente trarranno vantaggio dalla libertà di .

Questa interfaccia bucket non è fornita dalle implementazioni MetroWork SGI, Dinkumware o . Si ispira in parte dall'interfaccia collisione rilevamento Metrowerks , e in parte da lavori precedenti (vedi [Austern 1998]) su algoritmi per contenitori segmentati.

Answer 2

C'è un numero di algoritmi che richiedono l'hashing degli oggetti in un numero di bucket, e quindi ciascun bucket viene elaborato.

Dire, si desidera trovare i duplicati in una raccolta. Hai cancellato tutti gli elementi nella raccolta, quindi in ciascun segmento vengono confrontati gli articoli a coppie.

Un esempio un po 'meno banale è Apriori algorithm per la ricerca di set di articoli frequenti.

Answer 3

Immagino che tu possa trarre grandi vantaggi da questo se sei in una situazione di alte prestazioni e le collisioni finiscono per ucciderti. L'iterazione dei bucket e l'osservazione periodica delle dimensioni del bucket potrebbero dirti se la tua politica di hashing è sufficiente.

Le mappe non ordinate dipendono molto dalla loro politica di hashing quando si tratta di prestazioni.

Answer 4

L'unica ragione per cui ho sempre avuto bisogno dell'interfaccia è di attraversare tutti gli oggetti in una mappa senza dover tenere un blocco sulla mappa o copiare la mappa. Questo può essere usato per la scadenza imprecisa o altri tipi di controlli periodici sugli oggetti nella mappa.

La traversata funziona come segue:

1. Bloccare la mappa.

2. Iniziare a percorrere la mappa nell'ordine del secchio, operando su ciascun oggetto incontrato.

3. Quando si decide di tenere il blocco troppo a lungo, riporre la chiave dell'oggetto su cui si è operato per l'ultima volta.

4. Attendere finché non si desidera riprendere a funzionare.

5. Blocca la mappa e passa al punto 2, iniziando in corrispondenza o in prossimità (in ordine di secchio) del tasto su cui ci si è fermati. Se raggiungi la fine, ricomincia dall'inizio.