Вставить в очередь STL, используя std :: copy

Question

Я бы хотел использовать std::copy для вставки элементов в очередь следующим образом:

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

Но это не компилируется, жалуясь, что begin не является членом std::queue.

Примечание: я тоже попробовал с std::inserter - это тоже не удалось, на этот раз, говоря, что 'reference' не является членом 'std :: queue' std::back_inserter и std::back_insert_iterator также завершаются с той же ошибкой.

Я упускаю что-то очевидное или insert_iterator просто не работает с очередями?

Answer 1

К сожалению, std::queue 'адаптирует' функцию, известную как push_back, к значению push, что означает, что стандарт back_insert_iterator не работает.

Вероятно, самый простой способ (хотя и концептуально уродливый) состоит в том, чтобы адаптировать адаптер контейнера с помощью недолговечного адаптера контейнера [sic] (ух!

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

Используется так:

std::queue<int> qi;

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

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

Answer 2

Очередь не допускает итерацию по своим элементам.

Из документов SGI STL :

Очередь - это адаптер, который обеспечивает ограниченное подмножество контейнера Функциональность Очередь "первая в структура данных "первый выход" (FIFO). 1 То есть элементы добавляются в задняя часть очереди и может быть удалена с фронта; Q.front () является элемент, который был добавлен в очередь хотя бы недавно. Очередь не позволяет итерация по его элементам. [2]

Вы можете сделать эту работу, но вы не можете использовать insert_iterator. Вам нужно написать что-то вроде queue_inserter, представляющее интерфейс итератора.

Обновление Я не мог с собой поделать и решил попробовать реализовать итератор, который вам нужен. Вот результаты:

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

Это прекрасно работает для таких функций:

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

Но это не работает с копией STL, потому что STL глупо.

Answer 3

insert_iterator и back_insert_iterator работают только с контейнерами (или адаптерами) с (соответственно) методами insert и push_back - queue не имеет их. Вы можете написать свой собственный итератор, смоделированный на них, что-то вроде этого:

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

Если такая вещь уже не существует, но я уверен, что это не так.

Answer 4

Я почти уверен, что это просто не будет работать - очередь предоставляет push, но итератор вставки предполагает использовать push_front или push_back. Нет никакой реальной причины, по которой вы не могли бы написать свое push_insert_iterator (или любое другое имя, которое вы предпочитаете), но это немного болезненно ...

Answer 5

std::queue не является контейнером в смысле STL, это контейнер адаптер с очень ограниченными функциями. То, что вам, кажется, нужно либо std::vector, либо std::deque ("двусторонняя очередь, которая является" реальным контейнером "), кажется правильным выбором.

Answer 6

Что вам нужно, это push_inserter (т. Е. Устройство вставки, которое выполняет push в очередь). Насколько я знаю, в STL такого итератора нет. Обычно я грустно возвращаюсь к старому доброму циклу for.

Если у вас есть смелость, вы можете запустить свой собственный итератор, что-то вроде этого:

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

Это всего лишь черновик, но у вас есть идея. Работает с любым контейнером (или, кроме того, с адаптером контейнера) методом push (например, queue, stack).

Answer 7

std::queue не является одним из основных контейнеров в STL. Это контейнерный адаптер, который построен с использованием одного из базовых контейнеров STL (в данном случае один из последовательных контейнеров либо std::vector std::deque, либо std::list). Он разработан специально для поведения FIFO и не обеспечивает случайной вставки в данный итератор, который вы хотите, чтобы insert_iterator работал. Следовательно, невозможно использовать очередь, подобную этой.

Самый простой способ, которым я мог придумать, это сделать:

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

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

И используйте это как:

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

Answer 8

В этом простом случае вы можете написать:

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

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

Это создаст копию vector и будет использовать ее в качестве основного контейнера queue.

Конечно, этот подход не будет работать, если вам нужно ставить вещи в очередь после того, как очередь будет построена.