Esiste una classe sorted_vector, che supporta insert(), ecc.?

Question

Spesso, è più efficiente utilizzare un numero ordinato std::vector anziché uno std::set. Qualcuno conosce una classe di libreria sorted_vector, che in pratica ha un'interfaccia simile a std::set, ma inserisce elementi nel vettore ordinato (in modo che non vi siano duplicati), utilizza la ricerca binaria sugli elementi find, ecc.?

So che non è difficile scrivere, ma probabilmente meglio non perdere tempo e utilizzare comunque un'implementazione esistente.

Update: La ragione per usare un vettore ordinato invece di un insieme è: Se si dispone di centinaia di migliaia di piccoli gruppi che contengono solo 10 o giù di lì membri ciascuno, è più memoria-efficiente di utilizzare solo i vettori ordinati anziché.

Answer 1

Penso che non ci sia l'adattatore 'contenitore ordinato' nell'STL perché ci sono già i contenitori associativi appropriati per mantenere le cose ordinate che sarebbe appropriato usare in quasi tutti i casi. Per essere onesti, l'unica ragione per cui posso pensare di non avere un contenitore ordinato vector<> potrebbe essere l'interoperabilità con le funzioni C che aspettano una matrice ordinata. Certo, potrei mancare qualcosa.

Se ritieni che un ordinato vector<> sarebbe più adatto alle vostre esigenze (essendo a conoscenza delle carenze di inserimento di elementi in un vettore), ecco un'implementazione in codice del progetto:

• An STL compliant sorted vector By Martin Holzherr

Non l'ho mai usato, quindi non posso garantire per questo (o la sua licenza - se ne è specificato uno). Ma una rapida lettura dell'articolo e sembra che l'autore abbia fatto un buon sforzo affinché l'adattatore del contenitore abbia un'interfaccia STL appropriata.

Sembra che valga la pena dare un'occhiata più da vicino.

Answer 2

La ragione per cui un tale contenitore non fa parte della libreria standard è che sarebbe inefficiente. L'uso di un vettore per la memorizzazione significa che gli oggetti devono essere spostati se qualcosa è inserito nel mezzo del vettore. Facendo questo su ogni inserimento diventa inutilmente costoso. (In media, la metà gli oggetti dovranno essere spostati per ogni inserimento. Questo è abbastanza costoso)

Se si desidera un vettore ordinato, è probabile meglio inserire tutti gli elementi, e quindi chiamare std::sort()volta, dopo gli inserimenti.

Answer 3

Loki di Alexandresu ha un'implementazione vettoriale ordinata, se non si desidera passare attraverso lo sforzo insignificante relativley di rotolare il proprio.

http://loki-lib.sourceforge.net/html/a00025.html

Answer 4

Se si decide di rotolare il proprio, si potrebbe anche voler controllare Boost: uBLAS. Nello specifico:

#include <boost/numeric/ublas/vector_sparse.hpp> 

e guarda a coordinate_vettore, che implementa un vettore di valori e indici. Questa struttura dati supporta l'inserimento di O (1) (violando l'ordinamento), ma poi ordina Omega on-demand (n log n). Ovviamente, una volta ordinate, le ricerche sono O (logn). Se una parte dell'array viene ordinata, l'algoritmo riconosce questo e ordina solo gli elementi appena aggiunti, quindi esegue un'unione.Se ti interessa l'efficienza, questo è probabilmente il meglio che puoi fare.

Answer 5

Boost.Container flat_set

Boost.Container flat_ [MULTI] contenitori mappa/set sono ordinate-vettore basato contenitori associativi basati su Austern e di linee guida di Alexandrescu. Questi contenitori vettoriali ordinati hanno anche beneficiato di recente con l'aggiunta della semantica di movimento a C++, velocizzando notevolmente i tempi di inserimento e cancellazione. contenitori associativi piatto con i seguenti attributi:

• veloce ricerca di contenitori associativi standard di
• Molto più veloce iterazione di contenitori associativi standard.
• consumo di memoria Meno per piccoli oggetti (e per grandi oggetti se viene utilizzato shrink_to_fit)
• migliorato le prestazioni della cache (dati vengono memorizzati nella memoria contigua)
• iteratori non stabili (iterators sono invalidate durante l'inserimento e elementi cancellazione)
• tipi valori non copiabile e non mobile non possono essere memorizzati
• debole sicurezza eccezione che contenitori associativi standard (copia/costruttori movimento può generare quando spostamento valori raschiature e inserzioni)
• lento inserimento e cancellazione di standard associativo contenitori (in particolare per i tipi non-mobili)

Live demo:

#include <boost/container/flat_set.hpp> 
#include <iostream> 
#include <ostream> 

using namespace std; 

int main() 
{ 
    boost::container::flat_set<int> s; 
    s.insert(1); 
    s.insert(2); 
    s.insert(3); 
    cout << (s.find(1)!=s.end()) << endl; 
    cout << (s.find(4)!=s.end()) << endl; 
} 

---

JALF: ​​Se si desidera un vettore ordinato, è probabile meglio inserire tutti gli elementi, e quindi chiamare std :: sort() una volta, dopo gli inserimenti.

boost::flat_set possono farlo automaticamente:

template<typename InputIterator> 
flat_set(InputIterator first, InputIterator last, 
     const Compare & comp = Compare(), 
     const allocator_type & a = allocator_type()); 

Effetti: costruisce un insieme vuoto utilizzando l'oggetto di confronto specificato e allocatore, e inserisce elementi della gamma [first, last) .

Complessità: lineare in N se la gamma [first, last) è già ordinato utilizzando comp e altrimenti N * log (N), dove N è l'ultima - in primo luogo.

Answer 6

Here è la mia classe sorted_vector che uso da anni nel codice di produzione. Ha sovraccarichi che ti consentono di utilizzare un predicato personalizzato. L'ho usato per contenitori di puntatori, che può essere una soluzione davvero piacevole in molti casi d'uso.