C++ STL：迭代器和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中的條目對於結果中的兩個連續條目非常接近。因此，我得出的結論，如果我取代了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更改爲這些調用。而不是檢查是否增加或減少循環內的迭代器，我可以決定在輸入for -loop之前。

我認爲我很好只是切換到map<>::iterator和map<>::reverse_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

使用模板功能。就我所知（這是一個錯誤），標準庫中繼承用於模板的唯一地方是IOstream。

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

不過，我的問題，如果你只會變得更好更改爲始終O（1）的容器，就像一個unordered_map。