在我当前的C++项目中,我有一个将整数键映射到对象的STL映射。算法返回一组条目。返回的数据依赖于算法的输入,因此无法预测:C++ STL:迭代器和reverse_iterator缺少基类的代码复制
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 */
}
极坏的...你知道一个更好的解决方案?
会调用一个函数模板的工作? – PlasmaHH 2012-02-13 14:23:55
你是如何得出结论的,你会获得更好的表现?你有数据支持它吗?如果这不是应用程序中真正的瓶颈,那么您可能只是为自己做更多的工作。这就是说,这仍然是一个有趣的问题。 :) – Scott 2012-02-13 15:08:23
由于使用'map :: find()'时O(log n)的复杂性,它无法假定下一个条目接近当前条目。此代码处于非常关键的位置,在几个嵌套循环内 – fishbone 2012-02-14 21:01:51