4

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++.

Improve this question
11
  • 1
    Is this a homework assignment? Commented Oct 25, 2010 at 14:15
  • 1
    Choose your language. There is no such thing as C/C++, and the implementations for these 2 languages would be very different. Commented Oct 25, 2010 at 14:16
  • 2
    @R.. your point is taken, but that argument is REALLY tired. I refer to C/C++ all the time. Why? Because our packages usually end up being C++ wrappers around C packages. I don't think anybody is horribly offended, save for the purists in both camps who have the luxury of picking one language or the other. Commented Oct 25, 2010 at 14:26
  • 1
    @San Jacinto: if the questioner is in the same situation as you, then he should specify C, and not C++. The simple reason is that based on the brief (in particular, no requirement to iterate along either rows or columns), the easy C++ solution to this is probably boost::unordered_map<pair<int,int>,Element>. I don't consider it particularly "purist" or "luxurious" to write C++ and use common C++ libraries, so a solution that has to work in both is more or less a C solution. Commented Oct 25, 2010 at 14:47
  • @Steve my point was more that "I can accept a package or solution in either form" since our code already has a part that is C thinly-wrapped in C++, and some straight C++ for most of it. It doesn't have to work in both, it has to work for me. The purists take this cute little "there is no C/C++ language", but I'd like them to explain that to the original writers for the tools like MFC, Qt, and the like. At some point, most C++ programmers end up wrapping C code in C++. That's all I'm saying. Not that the two languages are primarily the same. Commented Oct 25, 2010 at 14:54

4 Answers 4

Reset to default
7

Are you looking for a sparse matrix ?

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Good point. Except that, if the OP's remark "over 10^3" really means "a few thousand", I'd recommend a simple 2-d array.
3

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.

Improve this answer

Comments

1

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.

Improve this answer

1 Comment

Even in 64 bit mode, he can used 32 bit indexes.
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.

Improve this answer

2 Comments

Accesss to these elements is logarithmic time. So if you put 1 million elements in the map, it still would not take many operations to access your data. Not a constant-time array dereference, but a big space-saver.
markup fixed. There is (or used to be, I didn't check) an irritating bug in SO that code indentation doesn't work on the first line, hence the nbsp.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.