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

Question

En mi proyecto C++ actual, tengo un mapa STL que asigna claves enteras a los objetos. Un algoritmo devuelve un conjunto de entradas. Los datos devueltos depende de la entrada del algoritmo y por lo tanto no se puede predecir:

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 se ha mencionado en el ejemplo que puedo reemplazar map::count() y operator[] -calls con find. El STL-reference 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 iba a lograr un mejor rendimiento si sustituye la map.find() llama 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 la datosEntrada, tengo que busca hacia adelante o hacia atrás. Considere que llamo al 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 for -loop.

pensé que estoy bien con sólo cambiar el map<>::iterator-map<>::reverse_iterator y el uso de rbegin()/rend() en lugar de begin()/end(). Pero entonces me di cuenta que reverse_iterator y iterator tienen ninguna 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 (...) ... */ 

que sería grande, pero no hay base_iterator.

sé una solución sencilla para este problema: sólo hay que copiar todo el 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 mala ... ¿Conoce a una solución mejor?

Answer 1

Un tipo de base común no es necesario 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 elección da lugar a una llamada diferente.

Tomando su 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 inyectar la llamada directamente en el if/else cuerpo:

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

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

Answer 2

Se puede 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 3

utilizar 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 O (1) contenedor de siempre, como un unordered_map.