在我当前的C -project中,我有一个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 []. 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发生了变化.而不是检查是否增加或减少while循环内的迭代器,我可以在进入for循环之前决定.
我认为我只需将地图<> :: 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循环并针对这两种情况进行调整：
if (/* ... */)
{
/* for(...) which uses normal iterator in the while-loop */
}
else
{
/* for(...) which uses reverse iterator in the while-loop */
}
很糟糕……你知道一个更好的解决方案吗？
解决方法
当语言允许通用编程时,不需要通用基本类型.
你需要意识到的是,你可以拥有几个嵌套函数,其中每个选项都会导致不同的调用,而不是一个冗长的线性函数,并且有多个选择.
举个例子：
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());
}
