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

如示例中所述,我可以使用find 替换map::count()和operator[]-calls.在STL引用说,地图:: 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会针对这些调用进行更改.而不是检查是否增加或减少while-loop中的迭代器,我可以在进入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());
}

一个好处是,您可以减少函数中状态的更改次数,从而减少其复杂性.