C++ STL:由于缺少迭代器和reverse_iterator的基类，正在复制代码
在我当前的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-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-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 */
}非常糟糕..。你知道更好的解决方案吗？
回答 4
Stack Overflow用户
发布于 2012-02-13 23:15:41
当语言允许泛型编程时，公共基类型是不必要的。
您只需要认识到的是，您可以使用多个嵌套函数，其中每个选项都会导致不同的调用，而不是使用一个冗长的线性函数。
以你的例子为例：
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());
}一件好事是你减少了函数中状态变化的次数，从而减少了它们的复杂性。
Stack Overflow用户
发布于 2012-02-13 23:09:27
使用模板化函数。据我所知，标准库中唯一使用继承而不是模板的地方是IOstreams (这是一个错误)。
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。
Stack Overflow用户
发布于 2012-02-13 23:09:05
您可以使用模板：
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());
}https://stackoverflow.com/questions/9262030
复制相似问题
腾讯云开发者
