¿Cómo puedo escribir una plantilla de función que pueda aceptar una pila o una cola?

Question

Estoy implementando cuatro algoritmos que son completamente idénticos excepto por la estructura de datos que utilizan - dos usan priority_queue, uno usa stack, y el último usa queue. Son relativamente largo, así que me gustaría tener sólo una plantilla de función que acepte el tipo de contenedor como un argumento de plantilla y luego tener cada llamada algoritmo que plantilla con el argumento apropiado, así:

template <class Container> 
void foo(/* args */) 
{ 
    Container dataStructure; 
    // Algorithm goes here 
} 

void queueBased(/* args */) 
{ 
    foo<queue<Item> >(/* args */); 
} 

void stackBased(/* args */) 
{ 
    foo<stack<Item> >(/* args */); 
} 

I He logrado hacer esto con las implementaciones basadas en priority_queue y stack, pero no puedo hacer lo mismo con el algoritmo basado en queue porque usa un nombre diferente para acceder al elemento principal (front() en lugar de top()). Sé que podría especializar la plantilla para este caso, pero luego tendría una gran cantidad de código duplicado (que es lo que estoy tratando de evitar).

¿Cuál es la mejor manera de lograr esto? Mi primer instinto fue crear una clase contenedora para la cola que agrega una operación top() equivalente a stack, pero he estado leyendo que las clases STL de subclases son un no-no. ¿Cómo debería obtener este comportamiento, entonces?

Answer 1

Puede escribir un top función no miembro de sobrecarga del tipo del adaptador del recipiente:

template <typename T> 
T& top(std::stack<T>& s) { return s.top(); } 

template <typename T> 
T& top(std::queue<T>& q) { return q.front(); } 

// etc. 

Si en realidad se utiliza un contenedor de secuencias diferentes con los adaptadores de contenedores (a través de su parámetro Sequence plantilla), se Será necesario modificar las sobrecargas de forma adecuada para manejar eso.

Podría ser más sencillo usar un contenedor de secuencia (p.std::vector) directamente en lugar de usar uno de los adaptadores de secuencia.

Answer 2

front() y top() son específicos para ciertos tipos de contenedores, pero todos los contenedores STL admiten *begin().

Answer 3

queue, priority_queue y stack son todos los adaptadores de contenedor; son envoltorios alrededor de un contenedor subyacente (de forma predeterminada, deque para queue y stack y vector para priority_queue).

Dado que vector, deque y list (las clases de contenedores "reales") comparten la mayoría de sus métodos, puede cortar el intermediario y utilizar esas clases en su lugar.

Y tenga en cuenta que public herencia no es una buena idea para contenedores STL; privado herencia está bien (y probablemente lo que desee).

Answer 4

Puede crear un contenedor alrededor de std::queue sin usar herencia; De hecho, la herencia sería la herramienta equivocada aquí porque usted está tratando de decorar un queue en lugar de refinación o extender la queue. Aquí hay una posible implementación:

template <typename QueueType> 
class QueueWrapper { 
public: 
    explicit QueueWrapper(const QueueType& q) : queue(q) { 
     // Handled in initializer list 
    } 

    typedef typename QueueType::value_type value_type; 

    value_type& top() { 
     return queue.front(); 
    } 
    const value_type& top() const { 
     return queue.front(); 
    } 

    void pop() { 
     queue.pop(); 
    } 
private: 
    QueueType queue; 
}; 

Hope this helps!

Answer 5

Puede utilizar la especialización parcial para seleccionar el método adecuado:

template<class Container> 
struct foo_detail { 
    static typename Container::value_type& top(Container &c) { return c.top(); } 
    static typename Container::value_type const& top(Container const &c) { return c.top(); } 
}; 
template<class T, class Underlying> 
struct foo_detail<std::queue<T, Underlying> > { 
    typedef std::queue<T, Underlying> Container; 
    static typename Container::value_type& top(Container &c) { return c.front(); } 
    static typename Container::value_type const& top(Container const &c) { return c.front(); } 
}; 

template<class Container> 
void foo(/* args */) 
{ 
    Container dataStructure; 
    // Use foo_detail<Container>::top(dataStructure) instead of dataStructure.top(). 
    // Yes, I know it's ugly. :(
}