C ++ STL: дублирование кода из-за отсутствия базового класса для итератора и reverse_iterator

В моем текущем C ++ - проекте у меня есть карта STL, которая отображает целочисленные ключи на объекты. Алгоритм возвращает набор записей. Возвращаемые данные зависят от входных данных алгоритма и, следовательно, не могут быть предсказаны:

  class MyClass
  {
     //...
  };

  int myAlgorithm(vector::iterator inputIt)
  {
     // return a key for myMap which is calculated by the current value of inputData
  }

  int main(int argc, char *argv[])
  {
     vector inputData;
     map myMap;
     //
     //

     vector result;

     for (vector::iterator it = inputData.begin(); it != inputData.end(); it++)
     {
        int myMapKey = myAlgorithm(*it);
        // count() > 0 means "check whether element exists. Performance can be improved by replacing
        //    the operator[] and count() calls by map::find(). However, I want to simplify things
        //    in this example.
        if (myMap.count(myMapKey) > 0)
        {
           // in some cases there is no entry in myMap
           result.push_back(myMap[myMapKey]);
        }
     }
  }

Как упоминалось в примере, я могу заменить map :: count () и вызовы оператора [] на найти. В справочнике STL говорится, что сложность map :: find () логарифмическая по размеру ( O (log n) ).

Я обнаружил, что в большинстве случаев записи в myMap очень близки для двух последовательных записей в результате. Поэтому я пришел к выводу, что достигну большей производительности, если заменю вызовы map.find () итераторами:

     map::iterator myMapIt = myMap.begin();
     for (vector::iterator it = inputData.begin(); it != inputData.end(); it++)
     {
        int myMapKey = myAlgorithm(*it);
        // just increment iterator
        while (myMapKey != myMapIt->first)
        {
           myMapIt++;
           // we didn't find anything for the current input data
           if (myMapIt == myMap::end() || myMapIt->first > myMapKey)
           {
              break;
           }
        }

        // I know that I'm checking this twice, but that's not the point of my
        //    question ;)
        if (myMapIt == myMap::end() || myMapIt->first > myMapKey)
        {
           // probably it would be better to move the iterator back to the position
           //    where we started searching, to improve performance for the next entry
           myMapIt = myMap.begin();
        }
        else
        {
           result.push_back(myMapIt.second);
        }
     }

Эта концепция работает, но у меня есть большая проблема: в зависимости от inputData я должен искать вперед или назад . Учтите, что я вызываю код внутри main () несколько раз, и inputData изменяется для этих вызовов. Вместо того, чтобы проверять, увеличивать или уменьшать итератор внутри цикла while , я мог бы решить это до входа в цикл for .

Я подумал, что меня вполне устраивает переключение map :: iterator на map :: reverse_iterator и использование rbegin () / rend () вместо begin () / end () . Но потом я понял, что reverse_iterator и итератор не имеют общего базового класса:

     map::base_iterator myIt;
     if (/* ... */)
     {
        myMapIt = myMap::begin();
        myMapEndIt = myMap::end();
     }
     else
     {
        myMapIt = myMap::rbegin();
        myMapEndIt = myMap::rend();
     }
     /* for (...) ... */

Это было бы здорово, но нет base_iterator .

Я знаю простой способ решения этой проблемы: мне просто нужно скопировать весь для -цикла и настроить его для обоих случаев:

     if (/* ... */)
     {
        /* for(...) which uses normal iterator in the while-loop */
     }
     else
     {
        /* for(...) which uses reverse iterator in the while-loop */
     }

Очень плохо ... Вы знаете лучшее решение?