c++ - What data structure to use where keys exist in blocks with gaps between blocks? -

c++ - What data structure to use where keys exist in blocks with gaps between blocks? -

i have store info key, integer, follows pattern this:

1, 2, 4, 5, 60, 61, 63

that is, keys clumped in blocks of hundreds of keys few gaps in them, there can big gaps between blocks. there lone keys or little blocks in middle of nowhere.

at moment, std::map used store keys, showing in profiling taking time find keys. because need random-access of keys , there thousands of keys.

so far maximum key 16-bit, tried replacing std::vector , sped 10% in debug mode (whole programme performance). release mode negligible change, lot of long work in debug mode.

but keys may 32-bit in length, not possible.

i tried std::unordered_map gave worse performance std::map! don't have much experience hash maps, maybe tweak hash policy don't know how.

any suggestions on efficient info construction task?

thank you.

i reply not programming side, math side.

maybe solution (everything depends on real info have work with) create heap analyzer, split thousands of numbers hundreds of heaps.

keep in mind lowest heap number "heap base". each heap can create vector of pointers data, n element have number "heap base" + n (so, of pointers nullptr, such vectors not long).

and can create map of "heap base" numbers (each connected it's heap-vector). accessing n element vector takes o(1), have fast. searching in map heap - faster, because search in hundreds of heaps, not in thousands of numbers.

using "lower_bound" able find closest heap number searching, , search in heap.

if medium heap consist of k numbers, increment speed log(2) k. k = 8 - triple times. lose time searching , other actions, may win in speed.

if need create info store once, , work it, can solution.

with numbers example, have receive: (where t objects searching)

vector<t*> = {obj1, obj2, nullptr, obj4, obj5} vector<t*> b = {obj60, obj61, nullptr, obj63} map<int, vector<t*> > mymap; mymap.append(pair(1, a)); mymap.append(pair(60, b));

(where objn t*) , search number, illustration 63 using bounds methods. vector, , take element number 63-"base" (i.e. number 3)

c++ data-structures