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 контейнеров, где местоположение элемента определяется его положением среди других элементов, в ассоциативных контейнерах элементы хранятся как пара (coppia<>) <chiave, senso>. Для поиска значения элемента требуется его ключ поиска, который может быть самых разнообразных типов.

nota: Можно считать, in массиве o векторе ключом поиска является индекс, который всегда имеет целочисленное senso. По аналогии, шаблонный тип таблицы (tabella hash) carta geografica<>, с которого мы начнём обзор ассоциативных типов, можно рассматривать, как массив или вектор (для простоты понимания ). Он может индексироваться любым (ma sempre только одним) произвольным типом ключа, tipo: title[ 'un’ ], или pay[ “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<> воспользуемся уже рассмотренным раньше примером с базой данных студентов факультета:

risultato:C ++ principianti, Standard Template Library, contenitori associativi STL C ++, coppia di C ++, carta geografica<> C ++Даже такой поверхностный пример (пока мы не углубились в детали ассоциативных контейнеров) позволяет увидеть и сделать некоторые выводы:

  • Элементы, помещаемые в таблицу, размещены не в порядке их помещения (как было с vettore o lista), а в отсортированном порядке по значению ключа (ФИО);

  • Вот почему для типа данных ключа должна либо существовать операция сравнения, либо она должна быть создана пользователем;

Для поиска (a chiave) в ассоциативных контейнерах используется не последовательный перебор всех элементов, а в высшей степени эффективные и сложные алгоритмы, отработанные за годы (и даже десятилетия) существования STL . Обычно для реализации carta geografica<> используется техника красно-чёрных деревьев … но детали этого не принципиальны. Важным выводом из этого факта должно стать то, что поиск в ассоциативных контейнерах весьма быстр, и он гораздо лучше, чем если бы вы попытались его реализовывать вручную.

Newsletter nuove lezioni sulla programmazione:


Accetto di ricevere messaggi da purecodecpp.com sulla mia e-mail

data
pagina
contenitori STL associativi. parte 6
valutazione
5
olio

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.

Lascia un Commento

Inserire il codice nei tag: <pre class="lang:C ++ decodifica:true ">IL TUO CODICE</pre>