C++ STL: Duplicating code due to missing base-class for iterator and reverse_iterator

A common base type is unnecessary when the language allows Generic Programming.

What you simply need to realize is that instead of having a long-winded linear functions with several choices along the way, you can have several nested function in which each choice lead to a different call.

Taking your example:

boost::any_iterator start, end;
if (/* ... */) {
  start = map.begin(), end = map.end();
} else {
  start = map.rbegin(), end = map.rend();
}

// do something with start and end

You can transform the code into the following:

// Define a free-function in the .cpp to help factor common stuff
template <typename FwdIt>
static void dosomething(FwdIt start, FwdIt end) {
  // do something with start and end
}

And then inject the call straight into the if/else body:

if (/* ... */) {
  dosomething(map.begin(), map.end());
} else {
  dosomething(map.rbegin(), map.rend());
}

And one good thing is that you reduce the number of changes of states within your functions and thus their complexity.

Use a templated function. The only place in the Standard library where inheritance is used over templates is IOstreams, as far as I'm aware (and that was a mistake).

template<typename Iterator> ... stuff(Iterator begin, Iterator end) {
    // implement loop here
}
if (/*...*/) {
    stuff(map.rbegin(), map.rend());
} else {
    stuff(map.begin(), map.end());
}

However, I question if you would simply be better off changing to an always O(1) container, like an unordered_map.

You could use templates:

 template <typename T>
 void myFunction(T start, T end)
 {
     /* for (...) ... */
 }

 map<int, MyClass>::base_iterator myIt;
 if (/* ... */)
 {
    myFunction(myMap.begin(), myMap.end());
 }
 else
 {
    myFunction(myMap.rbegin(), myMap.rend());
 }