What data structure to use?

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