Insérez dans une file d'attente STL en utilisant std :: copy

Question

Je voudrais utiliser std :: copie pour insérer des éléments dans une file d'attente comme ceci:

vector<int> v; 
v.push_back(1); 
v.push_back(2); 

queue<int> q; 

copy(v.begin(), v.end(), insert_iterator< queue<int> >(q, q.front())); 

Mais cela ne parvient pas à compiler, se plaignant que « commencer » n'est pas membre de 'std :: queue'.

Remarque: Je l'ai également essayé avec std::inserter - cela a également échoué, cette fois en disant que 'reference' n'est pas membre de 'std :: queue'. std::back_inserter et std::back_insert_iterator échouent également avec la même erreur.

Ai-je quelque chose d'évident, ou est-ce que insert_iterator ne fonctionne pas avec les files d'attente?

Answer 1

Malheureusement std::queue « adapte » la fonction connue sous le nom push_back juste push ce qui signifie que la norme back_insert_iterator ne fonctionne pas. Probablement le moyen le plus simple (quoique conceptuellement moche) est d'adapter l'adaptateur de conteneur avec un adaptateur d'adaptateur de conteneur à durée de vie courte (eugh!) Qui vit aussi longtemps que l'itérateur d'insertion arrière.

template<class T> 
class QueueAdapter 
{ 
public: 
    QueueAdapter(std::queue<T>& q) : _q(q) {} 
    void push_back(const T& t) { _q.push(t); } 

private: 
    std::queue<T>& _q; 
}; 

Utilisé comme ceci:

std::queue<int> qi; 

QueueAdapter< std::queue<int> > qiqa(qi); 

std::copy(v.begin(), v.end(), std::back_inserter(qiqa)); 

Answer 2

std::queue n'est pas un conteneur au sens STL, c'est un conteneur adaptateur avec des fonctionnalités très limitées. Pour ce que vous semblez avoir besoin soit std::vector ou std::deque ("file d'attente à deux extrémités, ce qui est un « vrai conteneur »), semble le bon choix.

Answer 3

file d'attente ne permet pas d'itération à travers ses éléments.

De la SGI STL Docs:

une file d'attente est un adaptateur qui fournit un sous-ensemble restreint de fonctionnalité Container une file d'attente est un « premier premier sorti » (FIFO) structure de données 1 Autrement dit, el. Les éléments sont ajoutés à l'arrière de la file d'attente et peuvent être supprimés de l'avant; Q.front() est l'élément qui a été ajouté à la file d'attente moins récemment. La file d'attente n'autorise pas l'itération à travers ses éléments. [2]

Vous peut faire ce travail, mais vous ne pouvez pas utilisation insert_iterator. Vous devrez écrire quelque chose comme queue_inserter qui présente une interface d'itérateur.

Mise à jour Je n'ai pas pu m'empêcher de définir l'itérateur dont vous avez besoin. Voici les résultats:

template< typename T, typename U > 
class queue_inserter { 
    queue<T, U> &qu; 
public: 
    queue_inserter(queue<T,U> &q) : qu(q) { } 
    queue_inserter<T,U> operator ++ (int) { return *this; } 
    queue_inserter<T,U> operator *() { return *this; } 
    void operator = (const T &val) { qu.push(val); } 
}; 

template< typename T, typename U > 
queue_inserter<T,U> make_queue_inserter(queue<T,U> &q) { 
    return queue_inserter<T,U>(q); 
}  

Cela fonctionne très bien pour des fonctions comme ceci:

template<typename II, typename OI> 
void mycopy(II b, II e, OI oi) { 
    while (b != e) { *oi++ = *b++; } 
} 

Mais il ne fonctionne pas avec la copie STL parce que la STL est stupide.

Answer 4

Ce dont vous avez besoin est un push_inserter (c'est-à-dire un inséreur qui exécute push es dans la file d'attente). Autant que je sache, il n'y a pas de tel itérateur dans le STL. Ce que je fais habituellement est malheureusement de revenir au bon vieux pour la boucle.

Si vous avez le courage, vous pouvez rouler votre propre iterator, quelque chose le long de ces lignes:

template <typename Container> 
class push_insert_iterator 
{ 
    public: 
    typedef Container      container_type; 
    typedef typename Container::value_type value_type; 

    explicit push_insert_iterator(container_type & c) 
     : container(c) 
    {} // construct with container 

    push_insert_iterator<container_type> & operator=(const value_type & v) 
    { 
     //push value into the queue 
     container.push(v); 
     return (*this); 
    } 

    push_insert_iterator<container_type> & operator*() 
    { 
     return (*this); 
    } 

    push_insert_iterator<container_type> & operator++() 
    { 
     // Do nothing 
     return (*this); 
    } 

    push_insert_iterator<container_type> operator++(int) 
    { 
     // Do nothing 
     return (*this); 
    } 

    protected: 
    container_type & container; // reference to container 
}; 

template <typename Container> 
inline push_insert_iterator<Container> push_inserter(Container & c) 
{ 
    return push_insert_iterator<Container>(c); 
} 

Ceci est juste un projet, mais vous eu l'idée. Fonctionne avec n'importe quel conteneur (ou, bien, adaptateurs de conteneur) avec une méthode push (par ex.queue, stack).

Answer 5

std::queue n'est pas l'un des conteneurs de base en STL. C'est un adaptateur de conteneur qui est construit en utilisant l'un des conteneurs STL de base (dans ce cas, l'un des conteneurs séquentiels soit std::vectorstd::deque ou std::list). Il est conçu spécifiquement pour le comportement FIFO et ne fournit pas d'insertion aléatoire à l'itérateur donné que vous voulez que le insert_iterator fonctionne. Il ne sera donc pas possible d'utiliser une file d'attente comme celle-ci.

Le je pouvais penser moyen le plus facile de le faire est de:

class PushFunctor 
{ 
public: 
    PushFunctor(std::queue<int>& q) : myQ(q) 
    { 
    } 
    void operator()(int n) 
    { 
     myQ.push(n); 
    } 

private: 
    std::queue<int>& myQ; 
}; 

et de l'utiliser comme:

queue<int> q; 
PushFunctor p(q); 
std::for_each(v.begin(), v.end(), p); 

Answer 6

Je suis sûr qu'il ne va pas fonctionner - un la file d'attente fournit push, mais un itérateur d'insertion s'attend à utiliser push_front ou push_back. Il n'y a aucune raison réelle, vous ne pourriez pas écrire votre propre push_insert_iterator (ou quel que soit le nom que vous préférez), mais il est un peu une douleur ...

Answer 7

Dans ce cas simple, vous pouvez écrire:

vector<int> v; 
v.push_back(1); 
v.push_back(2); 

queue<int, vector<int> > q(v); 

Cela fera une copie du vector et l'utilisera comme conteneur sous-jacent du queue.

Bien sûr, cette approche ne fonctionnera pas si vous avez besoin de mettre en file d'attente après la construction de la file d'attente.

Answer 8

insert_iterator et back_insert_iterator ne fonctionnent sur des conteneurs (ou adaptateurs) avec (respectivement) insert et push_back méthodes - queue n'a pas ces derniers. Vous pouvez écrire votre propre iterator calqué sur ceux-ci, quelque chose comme ceci:

template <typename Container> 
class push_iterator : public iterator<output_iterator_tag,void,void,void,void> 
{ 
public: 
    explicit push_iterator(Container &c) : container(c) {} 

    push_iterator &operator*() {return *this;} 
    push_iterator &operator++() {return *this;} 
    push_iterator &operator++(int) {return *this;} 

    push_iterator &operator=(typename Container::const_reference value) 
    { 
     container.push(value); 
     return *this; 
    } 
private: 
    Container &container; 
}; 

À moins qu'une telle chose existe déjà, mais je suis sûr qu'il ne fonctionne pas.