C++ STL：iteratorとreverse_iteratorの基本クラスがないためにコードを複製する

Question

私の現在のC++プロジェクトには、整数キーをオブジェクトにマップするSTLマップがあります。アルゴリズムはエントリのセットを返します。返されるデータは、アルゴリズムの入力に依存し、したがって、予測することはできません。

class MyClass 
    { 
    //... 
    }; 

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

    int main(int argc, char *argv[]) 
    { 
    vector<int> inputData; 
    map<int, MyClass> myMap; 
    //<fill map with some data> 
    //<fill inputData> 

    vector<MyClass> result; 

    for (vector<int>::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()とoperator[] -callsを置き換えることができます。 STL-referenceは、map :: find（）の複雑さは対数である（O(log n)）と言います。

私は、ほとんどの場合、myMapのエントリは結果の2つの連続したエントリに非常に近いことを発見しました。したがって、私は）（私はmap.findを交換した場合、私はより良い性能を達成するであろうという結論に達しましたイテレータで呼び出します：

 map<int, MyClass>::iterator myMapIt = myMap.begin(); 
    for (vector<int>::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 -loop内のイテレータをインクリメントするのかデクリメントするのかを調べる代わりに、for -loopを入力する前にそれを決めることができました。

私はちょうどmap<>::reverse_iteratorにmap<>::iteratorを切り替えてrbegin()/rend()代わりのbegin()/end()を使用して大丈夫だよと思いました。しかし、その後、私はreverse_iteratorとiteratorは何の共通の基底クラスがないことに気づい：

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

素晴らしいことだが、ないbase_iteratorはありません。

私はこの問題の簡単な回避策を知っている：私はちょうど全体for -loopをコピーして、両方のケースのためにそれを調整する必要があります。

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

非常に悪い...あなたがよりよい解決策を知っていますか？

Answer 1

一般的なプログラミングが可能な言語では、共通の基本タイプは不要です。

簡単に理解する必要があるのは、道に沿っていくつかの選択肢がある長時間の線形関数の代わりに、それぞれの選択肢が異なる呼び出しにつながる複数の入れ子関数を持つことができるということです。

あなたの例を取る：

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 

をあなたは、次にコードを変換することができます：

// 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 
} 

そしてストレートif/else体内にコールを注入：

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

そして一つの良いことは、関数内の状態の変化の数を減らし、その複雑さを軽減します。

Answer 2

あなたは、テンプレートを使用することができます。

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()); 
} 

Answer 3

は、テンプレート機能を使用してください。スタンダードライブラリのテンプレート上で継承が使用される唯一の場所は、私が知っている限り（それは間違いだった）IOストリームです。あなたは、単にunordered_mapのように、常にO（1）コンテナに変更したほうが良いかどう

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

しかし、私は疑問。