Insert into an STL queue using std::copy

Question

Hi, I'd like to use std::copy to insert elements into a queue like this:

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

But this fails to compile, complaining that 'begin' is not a member of 'std::queue'.

Note: I tried it with std::inserter too - this also failed, this time saying that 'reference' is not a member of 'std::queue'. std::back_inserter and std::back_insert_iterator also fail with the same error.

Am I missing something obvious, or do insert_iterators just not work with queues?

Answer 1

std::queue isn't a container in the STL sense, it's a container adapter with very limited functionality. For what you seem to need either std::vector or std::deque ("double-ended queue, which is a "real container"), seems the right choice.

Answer 2

Queue does not allow iteration through its elements.

From the SGI STL Docs:

A queue is an adaptor that provides a restricted subset of Container functionality A queue is a "first in first out" (FIFO) data structure. [1] That is, elements are added to the back of the queue and may be removed from the front; Q.front() is the element that was added to the queue least recently. Queue does not allow iteration through its elements. [2]

You can make this work, but you can't use insert_iterator. You'll have to write something like queue_inserter that presents an iterator interface.

Update I couldn't help myself and deicded to try to implement the iterator you need. Here are the results:

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

This works great for functions like this:

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

But it doesn't work with the STL copy because the STL is stupid.

Answer 3

What you need is a push_inserter (i.e. an inserter that performs pushes into the queue). As far as I know, there is no such iterator in the STL. What I usually do is sadly fall back to the good old for loop.

If you have the courage, you can roll your own iterator, something along these lines:

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

This is just a draft but you got the idea. Works with any container (or, well, container adapters) with a push method (e.g. queue, stack).

Answer 4

std::queue is not one of the basic containers in STL. It is a container adaptor which is built using one of the basic STL containers ( in this case one of the sequential container either std::vector std::deque or std::list). It is designed specifically for FIFO behaviour and does not provide random insertion at the given iterator which you want for the insert_iterator to work. Hence it will not be possible to use queue like this.

The easiest way I could think of to do this is to:

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

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

And use it like:

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

Answer 5

I'm pretty sure it just won't work -- a queue provides push, but an insert iterator expects to use push_front or push_back. There's no real reason you couldn't write your own push_insert_iterator (or whatever name you prefer) but it is a bit of a pain...

Answer 6

In this simple case, you can write:

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

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

This will make a copy of the vector and use it as the underlying container of the queue.

Of course, this approach won't work if you need to enqueue things after the queue has been constructed.

Answer 7

insert_iterator and back_insert_iterator only work on containers (or adaptors) with (respectively) insert and push_back methods - queue doesn't have these. You could write your own iterator modelled on these, something like this:

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

Unless such a thing already exists, but I'm pretty sure it doesn't.

Answer 8

Unfortunately std::queue 'adapts' the function known as push_back to just push which means that the standard back_insert_iterator doesn't work.

Probably the simplest way (albeit conceptually ugly) is to adapt the container adapter with a short lived container adapter adapter[sic] (eugh!) that lives as long as the back insert iterator.

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

Used like this:

std::queue<int> qi;

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

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