Esiste già una struttura dati "Raccoglitore"?

Stavo pensando a una struttura dati che non riesco a descrivere meglio della parola "libro", o più esattamente "raccoglitore". Mi chiedevo se questo fosse già stato implementato in librerie come Boost o altri.

Principio

È una struttura dati che consente l'accesso casuale a tempo costante e l'inserimento / eliminazione di un tempo costante ammortizzato (a condizione che la sequenza di tali eventi sia eseguita su indici non troppo distanti l'uno dall'altro).

Consiste di due stack "left" e "right" che rappresentano lo stato di un raccoglitore che sarebbe aperto su una determinata pagina. L'inserimento e l'eliminazione di elementi vicino a questa pagina è piuttosto veloce poiché consiste nello spingere / scoppiare le pagine nella / dalla pila di sinistra e sfogliare alcune pagine se necessario. Naturalmente nel peggiore dei casi si dovrebbe passare dalla prima pagina all'ultima pagina (riempire una pila con l'altra), ad esempio se l'utente inserisce qualcosa all'inizio e poi qualcosa alla fine.

Ecco un'implementazione molto rudimentale in C ++:

#include <iostream>
#include <vector>

using namespace std;

template<class T>
class Book {

    vector<T> left, right;

public:

    inline size_t size()
    {
        return left.size() + right.size();
    }

    void push(T t)
    {
        insert(size(),t);
    }

    T& get(size_t i)
    {
        if (i < left.size())
             return left[i];
        else return right[right.size()-i+left.size()-1];
    }

    void insert(size_t i, T t)
    {
        reposition(i-1);
        left.push_back(t);
    }

    void remove(size_t i)
    {
        reposition(i);
        left.pop_back();
    }

protected:

    void reposition(size_t i)
        // puts the element at position i on the top of the left stack
    {
        while (i < left.size()-1)
        {
            right.push_back(left.back());
            left.pop_back();
        }
        while (right.size() >= size()-i)
        {
            left.push_back(right.back());
            right.pop_back();
        }
    }

};

int main()
{
    Book<int> b;
    for (int i = 0; i < 15; i++)
        b.push(i);

    b.insert(5,42);
    b.remove(10);

    int i = 0;
    while (i < b.size())
    {
        if (b.get(i)%2 != 0)
             b.remove(i);
        else i++;
    }

    for (int i = 0; i < b.size(); i++)
    {
        cout << b.get(i) << " ";
    }
    cout << endl;
    return 0;
}

Nota: una possibile buona ottimizzazione sarebbe quella di avere i due stack in ordine inverso, per consentire a una memcpy dell'intera porzione di essere spostata dallo stack all'altro piuttosto che spostare gli elementi uno per uno (la memcpy è di solito molto più veloce ).

Usa

Quindi un buon caso d'uso di questo DS sarebbe un algoritmo che attraversa una sequenza di elementi e può, per ogni indice, aggiungere nuovi elementi o rimuovere vecchi elementi vicino a questo indice.

Un caso particolare di questo è il filtraggio di una matrice di elementi. Tutto quello che devi fare è iterare su tutti gli indici e semplicemente chiamare binder.remove (i) se l'elemento di index i deve essere rimosso.

Un modo efficiente (e ottimale) per farlo, data una serie di elementi, di solito è di allocare un altro array della stessa dimensione e copiare solo gli elementi che vogliamo salvare. È facile vedere che questo fa la stessa quantità di operazioni rispetto all'implementazione di Binder (se inizia sulla prima pagina), la differenza principale è che Binder consente un algoritmo più semplice che nasconde i dettagli sporchi dell'implementazione. (E non ci ritroviamo con un oggetto diverso.)

Le cose diventano ancora più complicate da implementare quando dobbiamo gestire la cancellazione di elementi vicini o un mix di cancellazione e aggiunta, mentre con il Raccoglitore DS è tutto incapsulato e l'algoritmo rimane molto semplice.

Quindi Binder DS può essere visto come una matrice (o "vettore" nel senso di C ++) che consente di lavorare in modo efficiente sul suo contenuto includendo un buffer di lavoro, quindi non si deve mai allocare spazio extra a mano (quindi aiuta a ridurre le allocazioni dinamiche della memoria). Rende trasparenti tutti i processi di mutazione.

Conclusione

Non l'ho testato a lungo contro algoritmi più convenzionali, ma mi aspetto che sarebbe un po 'più lento nell'accesso agli elementi di un vettore semplice a causa della maggiore complessità di avere due buffer invece di uno.

Pensi che questa sia una buona idea di una struttura dati e sarebbe efficiente? È già stato fatto e in quale libreria? Hai un'alternativa migliore da proporre?