What is the best data structure for my needs?
Posted on 2004-08-04
I have to map integers like this:
1 -> 1
2 -> 9
they are formed under the following rules:
1) the source number (2,4, etc.) is not necessarily contiguous. it is not necessarily 2,3,4 but can be 2,3,6,7 or something. However they are in ascending order. I mean when I call to add them to data structure the calls will be in ascending order (e.g. add(2,9)... add(4,15) etc.)
2) the result numbers are also in ascending order. e.g. the result of source 4 will be something > 9 which is the result of the source 2
- I need efficient lookups of both source -> result and result -> source (e.g. result(2) returns 9 and source(9) returns 2)
- now this is the tricky part... I need to be able to look up "in-between" numbers of the result to get the source. (e.g. anything less than 9 should return 1 and anything >= 9 and < 15 should return 2 and anything >= 15 should return 4.
- also this data structure can be somewhat large. I'm not sure if there would be performance benefits keeping it as simple primitives instead of objects. Probably there wouldn't be usually more than, say, a few thousand of these mapped pairs.