Data structure for efficient search

Question

I am looking for a suggestion for the appropriate data structure to use in the following scenario I have minimum value and maximum value defined for keys for eg.

Key          Min Value                Max Value

key1          0 .5                    4.5
key2          1                       9
key3          0.75                    1.5

I have to break each value to further sub buckets such that the difference between a minimum value and maximum value can’t exceed 1 and each bucket minimum value will be incremented by 0.5.

for e.g. key1 will break down further

Key               Bucket   Min Value                Max Value
key1             B1       0.5                      1.5
key1             B2       1                        2
key1             B3       1.5                      2.5
key1             B4       2                        3
key1             B5       2.5                      3.5
key1             B6       3                        4
key1             B7       3.5                      4.5

Once I have these buckets created(which is just one time), I need to find eligible buckets for a given key and value.

For e.g. eligible buckets for key1 and 2.2 are B3 and B4.

currently, I am storing all the bucket in std::map<Key, std::vector<Buckets> >

where Buckets is struct having bucket name, min and max as a variable.

What another alternative I can use than std::map<Key, std::vector<Buckets> > to speed up my search process?

Answer 1

You could place all the records into a std::vector, then use std::map<key, vector-index>. This is known as creating an index table.

For small amounts of data, a linear search is not distinguishable from using index tables (actually may be faster).

Search the internet for "first normal form", for ways to optimize your data.