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!