Is it possible to use a custom class in place of std::pair in an STL map?

Question

Is this possible?

#include <map>

class Example {

  private:
  std::map<std::string, std::string, less<std::string>,
    std::allocator< CustomPair<std::string, std::string> > > myMap;
};

In the example above, CustomPair would be a template class holding a key and value. If this is possible, is it that simple or is there anything I should look out for?

Answer 1

One can only speculate what your real intent is here, so I assume you already have a class that contains both key and value. In that case std::set with a custom comparison may be a better choice than a std::map.

You then need to provide a comparison that will only compare the key part of your class and the key part must be const (not change over time) as long as the object is in the set. As mentioned in the comment the elements of a set are only accessable as consts, so if you want to change the value of a such element you need to const_cast the write access or declare the member mutable.

In another answer iain made another very good suggestion. If you rarely insert into the container and mostly access the container searching for elements then a sorted std::vector and std::binary_search are a very effective alternative to the set.

Answer 2

I would be more likely to use std::set.

Answer 3

I think you can do it but will not get the desired effect, because the use of std::allocator will be done via rebind<std::pair>, thus overriding your selection of CustomPair. In fact, it probably doesn't matter what type you put there, the STL functions will ignore it. At least some of them will definitely do this, but I'm not sure all will. Strictly speaking this is almost certainly implementation dependent. I don't know what the standard says.

Answer 4

I would either use a set as described by lothar or use an sorted std::vector as described in "Effective STL" chapter 23: "Consider replacing associative containers with sorted vectors".

The rational for this is that a std::binary_search of a sorted vector with a custom comparitor is nearly as fast and sometimes faster than a map lookup and iteration is much faster. The insert operations are more expensive though (you have to call sort after each insert). A lot of map use cases insert very infrequently though.

The vector would be more flexibility than the set.

I replaced a map of 2000 complex objects (indexed by int) with this approach, iteration and processing every object in the map went from 50 seconds to less than 5 on a server class system. There was no noticeable difference for map lookups times.