Take the 2-minute tour ×

I am building a class which uses a std::map<tuple<...>> as a lookup data structure. I want to be able to do a prefix search on the map to find all elements sharing a certain prefix inside the tuple. For instance:

using namespace std;
map<tuple<int,int,int,string>,Value> index;

This does exactly what I need but I have to manually (for non POD types) figure out the minimum value. Even worse, when I want to find the highest element with a certain prefix (which I do), I would have to find the maximum element value for a certain type, which in case of string is rather problematic.

Ideally, I would be able to supply map.find/lower_bound/upper_bound (not std::find which is linear complexity on maps) with a separate comparison which does not take the suffix into account but unfortunately this is not possible, most likely because prefix search is more or less the only sensible application.

I think options would be modifying the comparison used by map at runtime (which I consider extremely bad style) or implementing a numeric_limits equivalent for all types I will have inside of tuples.

Is there a better option out there for doing a prefix search on a map/set?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

You get to pass in a "static" comparison functor to the map when you define it. The default ordering on tuple<...> is a lexicographic ordering on the type.

Extend the key type to ones that allow for fields to be flagged as max or min values, and provide a sorting algorithm that accepts them.

ie, something like this:

template<typename T>
struct InfiniteExtensionOf
  enum ExtendedOrder {NegInfinity=-1, Normal=0, PosInfinity=1};
  ExtendedOrder order;
  T value;
  bool operator<(InfiniteExtensionOf const& other) const
    if (order != other.order)
      return order<other.order;
    return value < other.value;
  template<typename U>
  InfiniteExtensionOf( U&& u ):order(Normal),value(std::forward(u)) {}
  InfiniteExtensionOf( InfiniteExtensionOf&& other ):order(other.order),value(std::move(other.value)) {}
  InfiniteExtensionOf( InfiniteExtensionOf& other ):order(other.order),value(other.value) {}
  InfiniteExtensionOf( InfiniteExtensionOf const& other ):order(other.order),value(other.value) {}
  InfiniteExtensionOf( ExtendedOrder& eo ):order(eo), value() {}
  InfiniteExtensionOf( ExtendedOrder&& eo ):order(eo), value() {}
  InfiniteExtensionOf( ExtendedOrder const& eo ):order(eo), value() {}

then key like this:

map<tuple<InfiniteExtensionOf<int>, InfiniteExtensionOf<int>, InfiniteExtensionOf<int>, InfiniteExtensionOf<string>>, Value> myMap;

which should accept tuples without the InfiniteExtensionOf argument (as such tuples implicitly convert, I hope), and you can specify +inf or -inf as the value of a particular field easily when calling lower_bound or upper_bound.


Note that if lower_bound took a template argument and only required it to be compatible to elements in the map in a way that agreed with the existing ordering, this would be less hassle. :) But sadly, that isn't true.

share|improve this answer
I came up with this idea too (thanks for the code though!) but the map will be extremely big, therefore I would roughly waste 1 byte (which due to alignent will probably end up being 8 bytes) per attribute times the number of tuples, so this solution will be quite expensive in terms of memory consumption compared to a hack involving finding a min and max element per type. I agree though, that a templated lower_bound method allowing compatible compare objects would completely solve this issue - though compatible is relatively hard to check and there's not a lot of use cases I suppose... –  Henrik Mühe Nov 15 '12 at 16:51
Another possibility: is the map a build once-use many times type of map? (or modify extremely rarely) In that case, the sorted pair vector trick does give you a lower_bound that takes a templated target and comparison. And vector has less memory overhead. :) Plus, that kind of pseudo-map has better performance than the std::map. –  Yakk Nov 15 '12 at 18:22
Sadly it's not; otherwise: neat trick. –  Henrik Mühe Nov 16 '12 at 14:06
Ok, then one more try. Stuff an int (or smaller, depending on how many keys in the tuple) into the pseudo-tuple that is the number of fields that are valid. Use a bit of said int to indicate if you want the upper or lower bound that the prefix requires. Enhance operator< on the pseudo-tuple to take this int into account. The cost here is 1 int per key: given that you already have many-pointer overhead per entry (map and new overhead), this should be cheap. –  Yakk Nov 16 '12 at 14:55
We've actually build that this morning though with a std::array<bool> and a separate variadic "advanced_tuple" type. It will not be used for the lower/upper bound problem but it's a pretty clean solution. For upper/lower bound we will not provide fake min and max values for each type used in the tuple which luckily does not contain arbitrarily long strings right now. If that should happen in the future, I'll wrap all strings with a class as you suggested. Thanks for your help! –  Henrik Mühe Nov 16 '12 at 15:00

What you could do is not using the key types directly but sort of a tristate version of an optional type:

  1. If the value is set, the comparison just uses the value.
  2. If the small flag is set the value is thought to be smaller than all other values.
  3. If the large flag is set the value is thought of being larger than any other value.

To find the lower bound you would then search, e.g., using the small value:


This is for a map having a key made up of an int and a std::string, each one potentially replaced by a small or a large value.

share|improve this answer

Your Answer


