std :: implementazione non array di vettori?

Mi ci è voluto un po 'per trovare qualcosa che ritenevo autorevole e ho finalmente trovato questo nugget da un Dott. Articolo di Dobb's Journal 2001 :

"Intuitivamente, la classe vettoriale della libreria standard è come un array incorporato: possiamo considerarla come se fosse contenuta in un singolo blocco di memoria contigua, anche se lo Standard C ++ non richiede esplicitamente che gli elementi di un vettore occupano una memoria contigua, il comitato degli standard ha deciso nell'ottobre 2000 che questo requisito era mancante a causa di una svista e ha votato per includere il requisito come parte della sua rettifica tecnica, che ha ritardato l'imposizione. ogni implementazione esistente ha già funzionato in questo modo. "

Quindi, da una prospettiva rigorosa, credo che nessuna implementazione STL abbia mai usato qualcosa di diverso da un array.

Tuttavia, per i curiosi, credo che VLists (la variante di array crescente) più o meno soddisfi tutto il runtime requisiti di std :: vector senza contiguità e in particolare senza copie extra durante l'espansione. Da un punto di vista più teorico, stable_vector è un approccio interessante per gestione iteratore e si adatta al disegno di legge da una prospettiva più "letter of the law".

Inoltre, grazie @ 0fnt per la spiegazione della crescita ammortizzata!

StackOverflow sarebbe un posto migliore per chiedere domande relative a programmazione / algoritmo. In ogni caso, l'implementazione che si deve leggere sarebbe basata su "tabelle". Ecco come funziona tale implementazione:

• Inizializza vettore con dimensione n, ad esempio n = 16

Indirizzo: 0xAAA0 a 0xAAB0 Memoria riservata

• Inserisci 17 elementi. Il primo 16 inserito bene. Il prossimo elemento richiede più memoria.

Libreria STL: alloca memoria per 16 * 2 = 32. Copia 16 elementi. (Tempo reale impiegato = 16 unità). Inserisci il 17 ° elemento.

• Inserisci altri 16 elementi. Il primo 15 inserito bene. L'elemento successivo richiede più spazio.

Libreria STL: alloca memoria per 16 * 2 * 2 = 64. Copia 32 elementi. (Tempo reale impiegato = 32 unità). Inserisci l'elemento 33 °.

• Inserisci altri 32 elementi. Il primo 31 inserito bene. Successivo richiede più spazio. Libreria STL: alloca memoria per 16 * 2 * 2 * 2 = 128. Copia 64 elementi. (Tempo reale impiegato = 64 unità). Inserisci il 65esimo elemento.

Questa implementazione è O (1) per l'accesso e O (1) ammortizzata per l'inserimento. Come? Su un numero molto grande di operazioni, il tempo totale degli inserti sarebbe:

Tempo = 2 ^ 0 (inserti) + 2 ^ 0 (copia) + 2 ^ 1/2 (inserti) + 2 ^ 1 (copia) + 2 ^ 2/2 (inserti) + 2 ^ 2 (copia) ... .. + 2 ^ n (copia)

• Numero totale di inserti = 2 ^ n Tempo = 2 ^ 0 + 2 ^ 0 + 2 ^ 0 + 2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 2 ^ 2 = 1 + 2 * 2 ^ 0 + 2 * 2 ^ 1 + ... + 2 * 2 ^ (n-1) = 1 + 2 * (2 ^ n - 1)

Tempo medio per inserimento = 2 unità

• Inserti totali = 2 ^ n + 1 Tempo = 2 ^ 0 + 2 ^ 0 + 2 ^ 0 + 2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 2 ^ 2 + 2 ^ 3 ... = 1 + 2 * 2 ^ 0 + 2 * 2 ^ 1 + ... + 2 * 2 ^ (n-1) + 2 ^ n = 1 + 2 * (2 ^ n - 1) + 2 ^ n

Tempo medio per inserto = 3 unità

Non è un elenco collegato, ma sono carina questo è ciò che leggi: dimensioni 'crescenti / decrescenti'. La riduzione delle dimensioni delle eliminazioni è simile. Se la dimensione utilizzata è inferiore a 1/4, liberare il resto della memoria, liberare metà della memoria. Se si utilizza il proprio allocatore di memoria, non dovrebbe essere troppo difficile liberare solo ciò che si desidera. Ma se vuoi copiare anche oltre, l'analisi ti direbbe che le eliminazioni rimangono O (1)

È giuridicamente possibile implementare std::vector<T> senza utilizzare matrici (o strutture dati che utilizzano array sotto il cofano). L'unica condizione è che std::vector<T>::max_size() deve restituire un valore di 0 o 1 .

Esempio:

// A standard's conforming sketch for (std::vector) that does not use arrays
// under the hood.
template <typename T>
class vector {
public:
    typedef T * iterator;

    vector () {}

    // This is provably guaranteed to be O(1) in the number of elements in the vector.
    void push_back (T const & x) {
        if (!ptr) {
            ptr = new T(x);
        }
        else {
            throw "You've been a bad boy. You've viloated this->max_size().";
        }
    }

    void pop_back () {
        assert(ptr);
        ptr.reset(nullptr);
    }

    size_t size () const {
        return ptr ? 1 : 0;
    }

    size_t max_size () const {
        return 1;
    }

    T * data () {
        return ptr;
    }

    iterator begin () {
        return ptr;
    }

    iterator end () {
        // Technically adding 1 to a non-array pointer is undefined (or at least
        // something to that effect). This problem can be mitigated by using a
        // proper iterator class instead of a typedef'ed pointer.
        return ptr ? ptr + 1 : ptr;
    }

private:
    std::unique_ptr<T> ptr;
};

Il caso max_size() == 0 è banale. Lasciato come esercizio per il lettore.

Trovare documentazione STL molto vecchia potrebbe non essere così semplice come sembra. Quello che ricordo di aver usato STL nel 1996 è stato che & vec [0] era già garantito per fornire l'inizio della matrice di dati del vettore. Dubito che ci siano state implementazioni di non array che hanno soddisfatto le specifiche STL originali.

Il commento stava diventando troppo lungo e la mia risposta precedente era abbastanza complessa da non confonderla ulteriormente, ma in base al tuo link VList, ecco un'altra risposta:

Struttura dati principale: elenco (non c'è bisogno di essere collegato) di array (li chiamerò main_arrays), raddoppiando le dimensioni quando la capacità è limitata. Inizia con 1 main_array di dimensioni, quindi aggiungi un main_array a 2 lunghezze, quindi un 4-length.

La dimensione massima di questo array dipenderebbe dal controllo del computer, quindi 2 ^ 64 per un computer a 64 bit. Il vettore di capacità totale 2 ^ 64 richiederebbe 63 tali main_array nella nostra struttura dati. Quindi allocare un array ausiliario di dimensioni 63 (o 64) (lo chiamerò aux_array) per mantenere i riferimenti ai punti finali di ciascuno di questi main_arrays. L'allocazione dello spazio sarebbe un tempo costante se il sistema operativo piacesse. L'aggiunta di una voce a aux_array è costante.

Ora il trucco qui è che per tutti gli scopi pratici, specialmente quando si parla di C ++ stl, possiamo usare il modello di RAM per l'analisi, il che significa che tutte le operazioni di bit sarebbero costanti.

Diciamo che finora abbiamo assegnato n = 5 main_arrays, la capacità vettoriale totale finora è: 2 ^ 0 + 2 ^ 1 .. 2 ^ 4 = 2 ^ n - 1 = 31.

Ora per accedere a (k = 3) elemento, sottrarre k da 2 ^ n - 2, (2 ^ 5-2) -3 = 27.

J = Bitwise OP il risultato tale che i bit iniziali di 64-n di questo risultato sono 1.

Ora trova il primo 0 bit da sinistra in questo numero intero (questo è il tempo costante nel modello RAM)

Diciamo che l'indice è q. sia p = 63 - q.

L'indirizzo finale di main_array che memorizza questo elemento è aux_array [p]. H = Crea un nuovo numero intero che è 0.reft_shift (p bit, inserisci 1).

Il valore all'indirizzo aux_array [p] - (J & H) dovrebbe darti il valore dell'array.

O (1) tempo per ogni singolo accesso. Potrei aver fatto un po 'di errori con uno, ma nessuno così male che cambia la complessità dell'algoritmo (penso!: -)).

Felice di sapere se ci sono errori in questo algoritmo ..

EDIT: Se non assumiamo il modello RAM, la complessità prevista di un accesso sarebbe O (1) sotto ipotesi di tutti gli indici che sono in accesso uniforme . Il passo legato al tempo sarebbe trovare quale array principale ha i dati e che verrebbe calcolato guardando i bit nell'indice. L'analisi probabilistica qui è la stessa di quella di VList.