Il vettore è un caso speciale di elenchi collegati?

Question

Quando parlo dell'STL, ho diversi compagni di scuola che mi dicono che "i vettori sono elenchi concatenati".

Ne ho un altro che sostiene che se si chiama il metodo cancella() con un iteratore, si interrompe il vettore, poiché si tratta di un elenco collegato.

Tendono anche a non capire perché sto sempre sostenendo che i vettori sono contigui, proprio come qualsiasi altro array, e non sembrano capire cosa significa accesso casuale. Il vettore è strettamente contiguo, proprio come gli array regolari, o al massimo contigui? (per esempio assegnerà diversi segmenti contigui se l'intero array non si adatta).

Answer 1

Mi dispiace dire che i tuoi compagni di scuola hanno completamente torto. Se i tuoi compagni di scuola possono dire onestamente che "i vettori sono elenchi concatenati" allora devi rispettosamente dire loro che hanno bisogno di raccogliere a good C++ book (o qualsiasi libro di informatica decente) e leggerlo. O forse anche gli articoli di Wikipedia per vectors e lists. (Vedi anche gli articoli per dynamic arrays e linked lists.)

---

vettori (come in std::vector) non sono liste collegate. (Notare che std::vector non deriva da std::list). Mentre entrambi possono archiviare una raccolta di dati, come fa un vettore è completamente diverso da come lo fa un elenco collegato. Pertanto, hanno caratteristiche di prestazione diverse in diverse situazioni.

Ad esempio, le inserzioni sono un'operazione a tempo costante su elenchi collegati, mentre è un'operazione a tempo lineare su vettori se è inserita in un punto diverso dalla fine. (Tuttavia, è ammortizzati costante di tempo se si inserisce alla fine di un vettore.)

Il std::vector di classe in C++ sono richiesto essere contiguo dallo standard C++:

23.2.4/1 modello Classe vector

un vector è una sorta di sequenza che supporta iteratori ad accesso casuale. Inoltre, supporta operazioni di inserimento e cancellazione costanti (ammortizzate) alla fine; inserire e cancellare nel mezzo prendere tempo lineare. La gestione dello storage viene gestita automaticamente, sebbene possano essere forniti suggerimenti per migliorare l'efficienza. Gli elementi di un vector vengono memorizzati in modo contiguo, nel senso che se v è un vector<T, Allocator> dove T è un certo tipo diverso da bool, poi obbedisce l'identità &v[n] == &v[0] + n per tutti 0 <= n < v.size().

Confronti che, per std::list:

23.2.2/1 modello Classe list

Un list è una sorta di sequenza che supporta iteratori bidirezionali e concede il tempo di inserimento costante e cancellare le operazioni ovunque all'interno della sequenza, con gestione della memoria gestita automaticamente. A differenza dei vettori (23.2.4) e deques (23.2.1), l'accesso casuale rapido agli elementi della lista non è supportato, ma molti algoritmi hanno comunque bisogno di un accesso sequenziale.

Chiaramente, lo standard C++ stabilisce che un vettore e un elenco sono due contenitori diversi che fanno le cose in modo diverso.

Non è possibile "interrompere" un vettore (almeno non intenzionalmente) semplicemente chiamando erase() con un iteratore valido. Ciò renderebbe piuttosto inutile il std::vector poiché il punto della sua esistenza è gestire la memoria per te!

Answer 2

Per definizione, vector s sono blocchi contigui di memoria come array C. Vedi: http://en.wikipedia.org/wiki/Vector_(C%2B%2B)

I vettori consentono l'accesso casuale; ovvero, un elemento di un vettore può essere a cui si fa riferimento nello stesso modo degli elementi di array (per indici di array). Gli elenchi collegati e gli insiemi, nell'altra mano , non supportano l'accesso casuale o l'aritmetica del puntatore .

Answer 3

vettori non sono collegati lista collegata, che forniscono l'accesso casuale e sono contigui, proprio come gli array. Per ottenere ciò, riassegnano la memoria sotto il cofano.

L'elenco è progettato per consentire inserimenti e cancellazioni veloci, pur non invalidando alcun riferimento o iteratore tranne quelli dell'elemento eliminato.

Answer 4

vector conterrà all ' del proprio archivio in un unico luogo. A vector non è nemmeno lontanamente simile a un elenco collegato. Infatti, se dovessi scegliere due strutture di dati che erano le più diverse l'una dall'altra, sarebbe vector e list. "Al più contiguo" è come funziona un deque.

vettoriale:

1. garantito di memorizzazione contiguo per tutti gli elementi - si copiare o spostare gli elementi.
2. O (1) tempo di accesso.
3. O (n) per inserimento o rimozione.
4. Iteratori non validi all'inserimento o alla rimozione di qualsiasi elemento.

listino:

1. No archiviazione contiguo a tutti - mai copie o sposta elementi.
2. O (n) il tempo di accesso, oltre a tutti i brutti ricordi della cache che otterrai.
3. O (1) inserire o rimuovere.
4. Iteratori validi fino a quando quell'elemento specifico non viene rimosso.

Come si può vedere, si comportano in modo diverso in ogni caso di utilizzo della struttura dati.