C ++ STL: дублирование кода из-за отсутствия базового класса для итератора и reverse_iterator - PullRequest
Новая
       31

C ++ STL: дублирование кода из-за отсутствия базового класса для итератора и reverse_iterator

7 голосов
/ 13 февраля 2012

В моем текущем 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[] -call на find. STL-ссылка говорит о том, что сложность 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 -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 и настроить его для обоих случаев: 

     if (/* ... */)
     {
        /* for(...) which uses normal iterator in the while-loop */
     }
     else
     {
        /* for(...) which uses reverse iterator in the while-loop */
     }

Очень плохо ... Знаете ли вы лучшее решение?

Ответы [ 3 ]

6 голосов
/ 13 февраля 2012

Общий базовый тип не требуется, если язык допускает общее программирование.

Что вам просто нужно понять, так это то, что вместо использования длинных линейных функций с несколькими вариантами действий у вас может быть несколько вложенных функций, каждый из которых приводит к отдельному вызову.

Принимая ваш пример: 

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

И одна хорошая вещь заключается в том, что вы уменьшаете количество изменений состояний внутри ваших функций и, следовательно, их сложность.

4 голосов
/ 13 февраля 2012

Используйте шаблонную функцию. Насколько я знаю, единственное место в стандартной библиотеке, где наследование используется над шаблонами, - это 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.

3 голосов
/ 13 февраля 2012

Вы можете использовать шаблоны: 

 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());
 }
...