c++ - Effective data structure for both deleteMin and search by key operations -

i have 100 sets of objects, each set corresponding query point qi, 1 <= <= 100.

class {     int id;     int distance;     float x;     float y; } 

in each iteration of algorithm, select 1 query point qi , extract corresponding set object having minimum distance value. then, have find specific object in 100 sets, searching id, , remove objects.

if use heap each set of objects, cheap extract object min(distance). however, not able find same object in other heaps searching id, because heap organized distance value. further, updating heap expensive.

another option have considered using map<id, (distance, x, y)> each set. way searching (find operation) id cheap. however, extracting element minimum value takes linear time (it has examine every element in map).

is there data structure use efficient both operations need?

• extract_min(distance)
• find(id)

thanks in advance!

std::map or boost::multi_index