Good datastructure for look up of an id mapping to set of elements (c++)

Question

No boost, just plain STL please.

I have a class Foo* mapping to a set of pointers of class ID.

and I need to map a pointer to an instance of ID to a FOO class.

say I have this function:

void FindXXX(const ID* pID)
{

 /*find the containing FOO class quickly, but not at expense of an ugly code*/

}

right now I map each ID* to FOO* thus having something like that

map myMap; which I think is kind of ugly and redundant.

Please suggest

Answer 1

Sounds like a job for std::map, but your remarks seem to indicate that you don't want to use one, is that true?

std::map <key_type, data_type, [comparison_function]>

Answer 2

right now I map each ID* to FOO* thus having something like that

map myMap; which I think is kind of ugly and redundant.

I assume you have something like this:

map<ID*, Foo*> myMap;

Why would that be ugly?

Answer 3

Well, it kind of depends on the size of the two sets (ID* and foo*). I assume that you have #ID >> #FOO, and #FOO big enough to not warrant linear search through them.

I assume ID <-> Foo is a 1-to-many mapping.

You could store the mapping as a set > > and sort them this way: the set is sorted in increasing order of ID* (pointer value order would be fine) the set> is sorted in ascending order of the value of the first ID* in the .second of the pair.

When searching, you need to find the range of Foo* that have a set where the first ID* has a (pointer) value lower than the searched-for item, and the last a value higher. This will result in a hopefully much smaller set of items to iterate over their set. Then, iterate over these and find the one that contains the ID* you are looking for.

You will need a comparator for the pair > like this:

typedef Item pair<Foo*, set<ID*> >;

// Sorter in ascending order of first ID*, then ascending order of last ID*
struct IDOrdering: public binary_function<Item, Item, bool> {
  bool operator ()(const Item& lhs, const Item& rhs) {
    return *(lhs.second.begin()) < *(rhs.second.begin())
        || *(lhs.second.rbegin()) < *(rhs.second.rbegin());
  }
};


// your global map
set<Item, FirstIDOrdering> myMap;
typedef set<Item, FirstIDOrdering>::iterator ItemIterator;

// search for the item
Foo* FindXXX(const ID* pId) {
   Item criterion;
   criterion.second.insert(pId);
   ItemIterator start = myMap.lower_bound(criterion);
   while (start != myMap.end() && *(start->second.rbegin()) > pId) {
     if (start->second.count(pId))
       return start->first;
   }
   return NULL;
}

You may save some memory here, as Foo* and ID* are stored only once, but it comes at the cost of some complexity and probably some performance.

Note that this example does not take into account all sorts of border cases (empty lists), and you have to be careful when inserting a new item into the global myMap, as you may be able to add a new ID* to the list of a pair<>, but you need to make sure the entire set is sorted again, so that the find will actually work.

It is, however, difficult to know what would be best for you, as there is very little info about what you try to achieve: are the Foo* in the millions, the ID* in the millions, is this function to resolve ID* to Foo* called often ? In a performance critical section of your system ? All these are useful to make the trade-offs for the readability, complexity and performance of the code.