come implementare una classe sparse_vector

Question

Io sono l'attuazione di una classe di sparse_vector su modelli. E 'come un vettore, ma solo memorizza gli elementi che sono diversi dal loro valore costruito di default.

Quindi, sparse_vector sarebbe memorizzare il pigramente-ordinato coppie index qualità per tutti gli indici il cui valore non è T ().

sto basando la mia implementazione su vettori sparse esistenti in libraries-- numerica anche se la mia gestirà tipi non numerici T pure. Ho guardato boost::numeric::ublas::coordinate_vector e eigen::SparseVector.

Sia negozio:

size_t* indices_;  // a dynamic array
T* values_;  // a dynamic array 
int size_;
int capacity_;

Perché non è sufficiente utilizzare

vector<pair<size_t, T>> data_;

La mia domanda principale è: quali sono i pro ei contro di entrambi i sistemi, e che è in definitiva migliore?

Il vettore di coppie gestisce size_ e capacity_ per voi, e semplifica le accompagnano iteratore classi; ha anche un blocco di memoria invece di due, in modo che incorre metà riassegnazioni, e può avere una migliore frazione di riferimento.

L'altra soluzione potrebbe cercare più rapidamente in quanto le linee di cache si riempiono di dati degli indici solo durante una ricerca. Ci potrebbero essere anche alcuni vantaggi di allineamento se T è un tipo di 8 byte?

Mi sembra quel vettore di coppie è la soluzione migliore, ma entrambi i contenitori ha scelto l'altra soluzione. Perché?

Answer 1

In effetti, sembra che hanno reinventato la ruota (per così dire).

vorrei prendere in considerazione personalmente 2 librerie per il vostro bisogno:

• Loki, per Loki::AssocVector -> l'interfaccia di una mappa attuato per il vector (che è ciò che si desidera fare)
• Boost.Iterator, per la sua classe iterator_adaptor. Lo rende molto facile da implementare un nuovo contenitore per composizione.

Come osservazione, vorrei sottolineare che si potrebbe desiderare di essere un po 'più generico che valori diversi dal T() perché questo impongono T essere DefaultConstructible. Si potrebbe fornire un costruttore che prende un T const&. Quando si scrive un contenitore generico è bene cercare di ridurre i requisiti necessari quanto più possibile (fino a quando non le prestazioni non male).

Inoltre, vi ricordo che l'idea di usare un vector per la conservazione è molto buona per un piccolo numero di valori, ma si potrebbe desiderare di cambiare il contenitore sottostante verso una map classico o unordered_map se il numero di valori cresce. Può essere utile profiling / temporizzazione. Si noti che lo STL offrono questa capacità con gli adattatori contenitore come stack, anche se si potrebbe fare implementazione leggermente più difficile.

Buon divertimento.

Answer 2

Avere indici in un elenco separato li renderebbe più veloce per guardare in alto -. Come lei suggerisce, sarebbe utilizzare la cache in modo più efficace, in particolare se T è grande

Se si desidera implementare il proprio, perché non basta usare std::map (o std::unordered_map)? Le chiavi sarebbero più grandi, ma i tempi di implementazione sarebbe vicino allo zero!