What data structure to use?

Question

I need a data structure with the following properties:

• Access to elements must be very fast
• Elements, that are not added, shouldn't take memory (as ideal, size of empty structure near to zero)
• Each element has two integer coordinates (x,y) (access to elements only by them)
• Max count of elements known at creation time (over 10^3)
• Element contains few float values

It would be good if you also directed to an implementation of this structure in C or C++.

Answer 1

 

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

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

};

std::map< ElementAccessor, Element > myElementMap;

You can now use this map as a matrix. ElementAccessor refers to x,y. Just make sure to see if the element exists in the map before you try to access it, or one is created by default.

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

edit: the template brackets are showing up for the map. the map key type is ElementAccessor, the value is Element. Also, for the pair, the templating is int, int.

Answer 2

Check this out - you could alter the element type to float if this does everything you want.

Concise Sparse Matrix Package in C

For C++ you could use Boost.uBLAS - sparse_matrix details here.

Answer 3

If your X and Y are relatively small then a two dimensional array of pointers would work. 10000 pointers would be 40K in 32 bit code.

Answer 4

Are you looking for a sparse matrix ?