Retrieve container's comparison function given an iterator

Question

Given an iterator, is it possible to retrieve/use the correct comparison function for the collection that this iterator refers to?

For example, let's assume I'm writing a generic algorithm:

template <class InIt, class T>
void do_something(InIt b, InIt e, T v) { 
    // ...
}

Now, let's say I want to do something simple, like find v in [b..e). If b and e are iterators over a std::vector, I can simply use if (*b == v) .... Let's assume, however, that b and e are iterators over a std::map. In this case, I should only compare the keys, not the whole value type of what's contained in the map.

So the question is, given those iterators into the map, how do I retrieve that map's comparison function that will only compare the keys? At the same time, I don't want to blindly assume that I'm working with a map either. For example, if the iterators pointed to a set, I'd want to use the comparison function defined for that set. If they pointed to a vector or deque, I'd probably have to use ==, because those containers won't have a comparison function defined.

Oh, almost forgot: I realize that in many cases, a container will only have an equivalent of operator< rather than operator== for the elements it contains -- I'm perfectly fine with being able to use that.

Answer 1

Iterators don't have to be connected to containers, so they don't give you any details about the containers that they aren't necessarily connected to. That's the essential iterator abstraction: iterators delimit sequences, without regard to where the sequence comes from. If you need to know about containers you have to write algorithms that take containers.

Answer 2

There is no standard way to map from an iterator to the underlying container type (if there is such a container at all). You might be able to use some heuristics to try to determine which container, although that will not be simple and probably not guaranteed either.

For example, you can use a metafunction to determine whether the *value_type* is std::pair<const K, T>, which is a hint that this could be a std::map and after extracting the types K and T try to use a metafunction to determine whether the type of the iterator and the type of std::map<K,T,X,Y>::iterator or std::map<K,T,X,Y>::const_iterator match for a particular combination of X, Y.

In the case of the map that could be sufficient to determine (i.e. guess with a high chance of success) that the iterator refers to a std::map, but you should note that even if you can use that and even extract the type X of the comparator, that is not sufficient to replicate the comparator in the general case. While uncommon (and not recommended) comparators can have state, and you would not know which is the particular state of the comparator without having access to the container directly. Also note that there are cases where this type of heuristic will not even help, in some implementations of std::vector<> the iterator type is directly a pointer, and in that case you cannot differentiate between an 'iterator' into an array and an iterator into a std::vector<> of the same underlying types.