Quale struttura dati usare?

Question

Ho bisogno di una struttura di dati con le seguenti proprietà:

• Accesso componenti devono essere molto veloce
• elementi, che non sono aggiunti, non devono assumere memoria (come ideale, dimensione della struttura vuota vicino zero)
• Ciascun elemento ha due coordinate intere (x, y) (accesso a elementi solo da loro)
• conteggio massimo di elementi noti al momento della creazione (oltre 10^3)
• elemento contiene valori pochi galleggiante

Sarebbe bene se si dirigesse anche a un'implementazione di questa struttura in C o C++.

Answer 1

Verificare questo - è possibile modificare il tipo di elemento a float se questo fa tutto ciò che volete.

Concise Sparse Matrix Package in C

per C++ è possibile utilizzare Boost.uBLAS - dettagli sparse_matrix here.

Answer 2

Sei alla ricerca di un sparse matrix?

Answer 3

Se X e Y sono relativamente piccoli, una serie bidimensionale di puntatori funzionerebbe. 10000 puntatori sarebbero 40K in codice a 32 bit.

Answer 4

 

typdef ElementAccessor std::pair<int, int>; 

struct Element 
{ 
    float f1; 
    float f2; 
    //etc. 

}; 

std::map< ElementAccessor, Element > myElementMap; 

È ora possibile utilizzare questa mappa come matrice. ElementAccessor si riferisce a x, y. Assicurati solo di vedere se l'elemento esiste nella mappa prima di provare ad accedervi, o ne viene creato uno per impostazione predefinita.

http://www.cplusplus.com/reference/std/utility/pair/ http://www.cplusplus.com/reference/stl/map/find/

edit: le staffe di modello vengono visualizzati per la mappa. il tipo di chiave della mappa è ElementAccessor, il valore è Element. Inoltre, per la coppia, il template è int, int.