contenitori STL associativi. parte 6




C ++ principianti, Standard Template Library, contenitori associativi STL C ++, coppia di C ++, carta geografica<> C ++Tutti i tipi precedenti di contenitori (discusso in dettaglio o menzionati: vettore, lista, e) - Una collezione coerente, in cui gli elementi sono disposti in sequenza uno dopo l'altro, ma differiscono tra loro modo per accedere agli elementi.

Un'altra grande categoria di contenitori sono i cosiddetti contenitori associativi, che sono, effettivamente, tavoli, ricerca di valori che ha reso per qualche chiavi.

Ma prima di descrivere contenitori associativi, prestare attenzione a tale modello di classe (в составе STL) come coppia<>. Questo è un disegno abbastanza semplice. Ogni oggetto rappresenta una coppia di campi collegato primo e secondo. Nelle tabelle che costruiscono (in STL o nelle proprie classi) Tali campi possono essere la chiave, e il valore. Ma non vogliamo correre - un modello di classe coppia<> e può esso stesso essere di interesse indipendentemente contenitori.

noi, per esempio, determinare classe rappresentazione 2D di punti nel piano per un'ampia classe di problemi geometrici (файл point.h):

punto p(*Questo); mezzi, che crea una nuova variabile (oggetto) classe punto, e ha invitato il suo costruttore di copia. Per inizializzare il valore è preso dell'oggetto corrente *Questo – come indicato dalla pointer Questo. vale a dire. una nuova variabile punto p creato, come una copia dell'oggetto corrente. Il resto tutto va inteso.

risultato:C ++ principianti, Standard Template Library, contenitori associativi STL C ++, coppia<> C ++

ora, quando vediamo, quello che un modello di classe coppia<>, possiamo andare alla visione d'insieme, quali sono i contenitori STL associativi di base.

In contrasto con la discusso in precedenza consecutivo contenitori, Elemento dove la posizione è determinata dalla sua posizione tra gli altri elementi, contenitori associativi sono memorizzati come una coppia di elementi (coppia<>) <chiave, senso>. Per trovare i valori del elemento che si desidera cercare la sua chiave, che può essere una varietà di tipi.

nota: può essere considerato, in schieramento o vettore La ricerca è un indice della chiave, che ha sempre numero intero senso. per analogia, tavolo tipo generico (tabella hash) carta geografica<>, da cui inizieremo tipo associativo, può essere considerato, come una matrice o un vettore (per facilità di comprensione ). Può essere indicizzato da qualsiasi (ma sempre solo uno) Tipo chiave casuale, tipo: titolo[ 'un’ ], o pagare[ “Ivanov” ].

Uno dei più comunemente usato è contenitori STL associativi carta geografica<> - tavolo, una matrice di coppie <chiave, senso>, in cui la ricerca viene eseguita su un elemento chiave. La chiave può essere qualsiasi tipo di complesso, purché, che esiste per questo tipo di operazione confronto (Più-meno), o una simile operazione attuata dall'utente e viene specificato quando si crea una tabella. Per illustrare la semplice applicazione carta geografica<> Usiamo l'esempio precedente già discusso con una base di studenti della Facoltà di informazione:

risultato:C ++ principianti, Standard Template Library, contenitori associativi STL C ++, coppia di C ++, carta geografica<> C ++Anche un esempio superficiale (fino a quando siamo andati in profondità nei dettagli dei contenitori associativi) Esso permette di vedere e di trarre alcune conclusioni:

  • elementi, collocato nella tabella, Non è posto in ordine di posizionamento (come con vettore o lista), ma in modo ordinato per valore della chiave (FIO);

  • Questo è il motivo per il tipo di dati la chiave deve essere sia l'operazione di confronto, oppure deve essere creato dall'utente;

per la ricerca (a chiave) contenitori associativi che non utilizzano una scansione sequenziale di tutti gli elementi, un algoritmi altamente efficienti e sofisticati, lavorato per anni (e anche decenni) STL esistenza . Di solito, per l'attuazione del carta geografica<> tecnica utilizzata di alberi rosso-neri ... ma i dettagli non sono fondamentali. Un'importante conclusione di questo fatto dovrebbe essere il, che la ricerca di contenitori associativi è molto veloce, ed è molto meglio, che se si è tentato di implementare manualmente.

Newsletter nuove lezioni sulla programmazione:

contenitori STL associativi. parte 6
4.5 (90%) 2 voti

Di olio

esperienze pratiche circa lo sviluppo del software 40 anni. Maestro globale Logic società di software internazionale. IBM Developer funziona autore permanente di pubblicazioni. redattore scientifico del computer casa editrice letteratura "Simbolo-Plus", San Pietroburgo.

2 pensieri su "contenitori STL associativi. parte 6

Lascia un Commento

L'indirizzo email non verrà pubblicato. i campi richiesti sono contrassegnati *