Tuesday, November 13, 2007

Partial Match Within a std::map find()

In the C++ standard library, std::map does not support partial match of a multipart key. If an exact match of your key is not found, std::map returns end(). In short, it does not support partial matches within find().

If you are not defining the std::map, you are out of luck. If you can define the std::map, you can make it work. That is because you std::map does not let the caller of find determine sort order, and its a good thing too, otherwise chaos may ensue.

The Problem
The fundamental problem is when you want an insert and iterate sort order which is more specific than a search order. That is, the search terms are a subset of the sort terms. For composite key type { X, Y, Z } sort on less-than comparisons of X, Y, and Z, but search for the first match of X, without knowing Y or Z. std::map appears to not support a partial match.

The Possibility
std::map does support custom comparisons through a predicate object. Predicates get passed as the third parameter in the template instantiation.
std::map<Key, Value, Predicate> myMap;
A predicate is a function object, meaning it must have the following declaration:
class Predicate
bool operator()(const Key& lhs, const Key& rhs) const;
};
The trick is to make a predicate which knows the difference between a search and an insert. The find() method on std::map is no help, the only argument is a Key.

The Answer
That is enough for our problem. Assuming you have control over the key type of the map, insert into your key class a field that shows whether to do a full or partial comparison. The flag should be checked within the predicate using the following rule -

If either lhs or rhs is a partial match key, only compare the partial match fields. Otherwise, do the full comparison. So, if your key contains the following:

string name;
int id;
bool flag;

form your key like this:
class Key {
public:
std::string name;
int id;
bool flag;
bool partial_match;
};
and your predicate like this:
class PartialMatchPredicate {
public:
bool operator()(const Key& lhs, const Key& rhs) const {
if (rhs.partial_match || lhs.partial_match) {
// only comparing name
return lhs.name < rhs.name;
} else if (lhs.name < rhs.name) {
return true;
} else if (lhs.name > rhs.name) {
return false;
} else if (lhs.id < rhs.id) {
return true;
} else if (lhs.id > rhs.id) {
return false;
} else {
return lhs.flag < rhs.flag;
}
}
};


Happy searching!

6 comments:

Cristi A. said...

Dude,

Whoever you are this little post saved my ass.
I ran into the same problem of defining a 2 field composite key for a std::map, then having to search for a partial match based on only the first field. i implemented the predicate function and it works great.

Thanks.

Jeff Schmitz said...

Cristi

I'm glad to hear this helped you. Ideally, std::map<>::find() would allow us to pass in a predicate to override the default one. But as such, this is what I think is the best solution.

As for Whoever you are... I AM THE SCHMITZER

Anonymous said...

Hi schmitzer,

Is there any way to do a partial key match based on 2nd field of a composite key?

Thanks.

Jeff Schmitz said...

No, you can't partially match on the "middle" of a key. This would imply a different sort order.

Instead, you could try boost::multiindex, I believe.

Anonymous said...

Also that we would do without your magnificent idea

Anonymous said...

Nice dispatch and this post helped me alot in my college assignement. Thank you as your information.