c++ - Object search on part of the array -

c++ - Object search on part of the array -

i have object this:

class search_object { public: unsigned int index; // 0 <= index <= 50000 unsigned int search_field; // 1 <= search_field <= 5000000000, can duplicates! };

i have approximately 50000 objects such type. these objects sorted index.

my programme gets search queries this: "is there object, have index between left_index , right_index (left_index <= index <= right_index) , have search_field eqaul number (search_field == number).

there approximately 50000 queries.

i have solution, slow context system.

my algorithm is:

sort search objects search_field. find lower_index, search_object[lower_index] = number (lower_bound() function, binary search) iterate on array of objects lower_index end of array. if this_object has index between left_index , right_index, true. otherwise, false. repeat steps 2-3 search queries (left_index, right_index , number).

i utilize standard container, not utilize object key. code example:

std::map<decltype(search_object::index), search_object> container; ... auto itr = container.lower_bound(left_index); while (itr != container.end() && itr->first <= right_index) if (itr->second == number) homecoming itr; homecoming container.end();

c++ algorithm search binary-search