Come posso scrivere un modello di funzione che può accettare uno stack o una coda?

Question

Sto implementando quattro algoritmi che sono completamente identici a, tranne per la struttura dei dati che utilizzano: due utilizzano priority_queue, uno utilizza stack e l'ultimo utilizza queue. Sono relativamente lungo, quindi mi piacerebbe avere un solo modello di funzione che accetta il tipo di contenitore come argomento di un template e poi ogni chiamata algoritmo che modello con l'argomento del caso, in questo modo:

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 sono riuscito a fare proprio questo con le implementazioni basate su priority_queue e stack, ma non posso fare lo stesso per l'algoritmo basato su queue perché utilizza un nome diverso per accedere all'elemento più avanzato (front() anziché top()). So che potrei specializzare il modello per questo caso, ma poi avrei una grande quantità di codice duplicato (che è quello che sto cercando di evitare).

Qual è il modo migliore per farlo? Il mio primo istinto è stato quello di creare una classe wrapper per la coda che aggiunge un'operazione top() equivalente a stack, ma ho letto che le classi STL di sottoclassi sono un no-no. Come dovrei ottenere questo comportamento, allora?

Answer 1

È possibile scrivere una top funzione non-membro sovraccarico del tipo dell'adattatore container:

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. 

Se effettivamente utilizza un contenitore di sequenza diverso con gli adattatori contenitore (tramite il loro parametro Sequence modello), si Dovrò modificare opportunamente i sovraccarichi per gestirli.

Potrebbe essere più semplice utilizzare un contenitore di sequenza (ad es.std::vector) direttamente anziché utilizzare uno degli adattatori di sequenza.

Answer 2

front() e top() sono specifici per determinati tipi di contenitori, ma tutti i contenitori STL supportano *begin().

Answer 3

queue, priority_queue e stack sono tutti adattatori per container; sono wrapper attorno a un contenitore sottostante (per impostazione predefinita, deque per queue e stack e vector per priority_queue).

Dal vector, deque e list (le "reali" classi di contenitori) condividono la maggior parte dei loro metodi, è possibile tagliare il middle man e utilizzare quelle classi.

E tenere presente che l'eredità pubblica non è una buona idea per i contenitori STL; private l'ereditarietà va bene (e probabilmente quello che vuoi).

Answer 4

È possibile creare un wrapper attorno a std::queue senza utilizzare l'ereditarietà; infatti, l'eredità sarebbe lo strumento sbagliato qui perché si sta cercando di decorare un queue piuttosto che raffinazione o estendere il queue. Ecco una possibile implementazione:

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

Spero che questo aiuti!

Answer 5

È possibile utilizzare la specializzazione parziale per scegliere il metodo giusto:

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. :(
}