C++ STL: código de duplicación debido a la falta de clase base para iterador y reverse_iterator

map polymorphism

Question

En mi proyecto C ++ actual, tengo un mapa STL que mapea claves enteras en objetos. Un algoritmo devuelve un conjunto de entradas. Los datos devueltos dependen de la entrada del algoritmo y, por lo tanto, no pueden predecirse:

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

Como mencioné en el ejemplo, puedo reemplazar map::count() y operator[] -calls con find. La referencia de STL dice que la complejidad de map :: find () es de tamaño logarítmico ( O(log n) ).

Descubrí que en la mayoría de los casos las entradas en myMap están muy cerca de dos entradas consecutivas en el resultado. Por lo tanto, llegué a la conclusión de que obtendría un mejor rendimiento si reemplazaba las llamadas map.find () por iteradores:

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

Este concepto funciona pero tengo un gran problema: Dependiendo de inputData, tengo que buscar hacia delante o hacia atrás. Considere que llamo el código dentro de main() varias veces y el inputData cambia para estas llamadas. En lugar de verificar si aumentar o disminuir el iterador dentro del while -loop, podría decidirlo antes de ingresar al -loop.

Pensé que estoy bien con solo cambiar el map<>::iterator para map<>::reverse_iterator y usar rbegin() / rend() lugar de begin() / end() . Pero luego me di cuenta de que reverse_iterator e reverse_iterator no tienen una clase base común:

     map<int, MyClass>::base_iterator myIt;
     if (/* ... */)
     {
        myMapIt = myMap::begin();
        myMapEndIt = myMap::end();
     }
     else
     {
        myMapIt = myMap::rbegin();
        myMapEndIt = myMap::rend();
     }
     /* for (...) ... */

Eso sería genial, pero no hay base_iterator .

Conozco una solución simple para este problema: solo necesito copiar el todo for -loop y ajustarlo para ambos casos:

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

Muy mal ... ¿Conoces una mejor solución?

Answer 1

Puedes usar plantillas:

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

Answer 2

Un tipo de base común es innecesario cuando el lenguaje permite la Programación genérica.

Lo que simplemente necesita darse cuenta es que en lugar de tener funciones lineales largas con varias opciones en el camino, puede tener varias funciones anidadas en las que cada opción da lugar a una llamada diferente.

Tomando tu ejemplo:

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

Puede transformar el código en lo siguiente:

// 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
}

Y luego inserte la llamada directamente en el cuerpo if/else :

if (/* ... */) {
  dosomething(map.begin(), map.end());
} else {
  dosomething(map.rbegin(), map.rend());
}

Y una cosa buena es que reduce el número de cambios de estados dentro de sus funciones y, por lo tanto, su complejidad.

Answer 3

Use una función de plantilla. El único lugar en la biblioteca estándar donde se usa la herencia sobre las plantillas es IOstreams, que yo sepa (y eso fue un error).

template<typename Iterator> ... stuff(Iterator begin, Iterator end) {
    // implement loop here
}
if (/*...*/) {
    stuff(map.rbegin(), map.rend());
} else {
    stuff(map.begin(), map.end());
}

Sin embargo, me pregunto si simplemente sería mejor cambiar a un contenedor siempre O (1), como un unordered_map .