Lookup table where most sequential values point to the same object?

Question

Suppose I have a range of keys, say 0 -> 1000

Say 0 - > 99 map to one object 100 -> 251 map to another etc. etc.

What is a good way to map a key to an object without having to have an array of 1000 size and a bunch of if (x >= 0 && x <= 99) business?

I mean without any logic i.e. a stairstep table

Answer 1

You should probably only store the endpoints of the range in your data structure, and have those mapped to the value they point at. Then overload the [] operator and have it look up the range the index fits in.

You could use a list, if the data structure is of the proportions you described (10 or so possible ranges, given their size)

Answer 2

Use a std::map along with lower_bound:

map<long, string> theMap;
theMap[0] = "lessThan1";
theMap[99] = "1to99";
theMap[1000] = "100to1000";
theMap[numeric_limits<long>::max()] = "greaterThan1000";
cout << theMap.lower_bound(0)->second << endl; // outputs "lessThan1"
cout << theMap.lower_bound(1)->second << endl; // outputs "1to99"
cout << theMap.lower_bound(50)->second << endl; // outputs "1to99"
cout << theMap.lower_bound(99)->second << endl; // outputs "1to99"
cout << theMap.lower_bound(999)->second << endl; // outputs "100to1000"
cout << theMap.lower_bound(1001)->second << endl; // outputs "greaterThan1000"

Wrap it up in your own class to hide the details and you're good to go.

Answer 3

I like Eclipse's answer the best, but in cases where the starting point of a range is a consequence of accumulating some concept of the targets' "widths", you are probably better off just storing them in a vector. This will work especially well if you expect the set of ranges to change.