Std::Queue Iteration

std::queue iteration

If you need to iterate over a queue then you need something more than a queue. The point of the standard container adapters is to provide a minimal interface. If you need to do iteration as well, why not just use a deque (or list) instead?

Iterate over C++ STL queue

No, you cannot iterate over a std::queue since that is not its purpose.

A container that allows fast insertion at both ends, as well as iteration, is std::deque. Note that iteration is slower than for a std::vector, but insertion/removal at the beginning is much faster.

Iterating through std queue

std::deque supports efficient insert and removal at the beginning and end of the data structure. You can do queue operations manually using push_back and pop_front.

A queue uses a deque internally by default. It's a wrapper that only exposes queue operations (hence why you can't iterate over it). I asked a similar question a while back, and the best answer gave me good insight into the real use of std::queue. One should use std::queue not because one needs a queue, but to make it clear that only queue-like operations are legal on a given data structure. It sounds like you need more freedom than that, so go with deque, list, or some other structure with O(1) insert and remove at both ends.

Range-based loop for std::queue

Well, the answer is actually pretty simple: there is no function begin() in std::queue and there isn't any overload of std::begin taking a std::queue either. You can have a look at the documentation.

The core problem is that std::queue is not meant to be iterated over. It exists to satisfy other needs. If you really need to iterate over it, you should just use the underlying container (by default std::deque) which supports iteration and for which your code would be valid.

Traversing queue in C++

Your queue's printQueue method already has access to the private internals of the queue. Instead of using the public interface to print the queue, just use the internal queueFront pointer and walk the list, printing each element.

Something like (pseudocode since this homework):

for(node* n = queueFront; n; n = n->next)
{
    // Print data from node n.
}

Iterating queue of struct type in stl

Let me try to support you. It is good that you are getting more and more acquainted with the STL.

So, you would like to store elements in a FIFO, a “First In First Out” – Container. You checked the STL and found the std::queue most fitting. It has exactly what you need:

• front
• back
• push
• pop

So you selected std::queue as your container for your elements “Task”. Now, looking at your code, there are several steps of improvement possible, to come up with a modern C++ program.

First we need to eliminate a C++ syntax (and semantic) error. In C++ you cannot define dynamic plain arrays. The dimension of the array needs to be a compile time constant. So a real C++ compiler will not eat

Task task[t];

But fortunately C++ has a container that behaves similar like plain arrays, but can grow dynamically: std::vector. You should prefer std::vector (or other containers) over plain arrays. The result is that:

std::vector<Task> task(t);

This will create a vector with t empty tasks.

Next optimization is the removal of temporary variables. In your input loop you can write:

cin >> task[i].pid >> task[i].days >> task[i].depend;

With that you can eliminate 3 temporary variables: id,day,dep
And, additionally you can also delete w and j. They are not needed.

Next step: A class or struct knows how its values should be read (or written). So you will overload the >> operator for your class Task. With that the start of your class will look lke this:

struct Task {
    int pid;
    int days;
    int depend;
    friend istream& operator>>(istream& is, Task& task) { return is >> task.pid >> task.days >> task.depend;  }
};

int main()
{
    int t, i;
    cin >> t;
    std::vector<Task> task(t);
    for (i = 0; i < t; i++)
    {
        cin >> task[i];
    }

    . . . . 

Already much better. Now the next and major problem and the answer to your question. For debug purposes you want to iterate over you job_queue. And you are asking:

Iterating queue of struct type in stl

And the answer is: Not possible.

std::queue has no iterators and no index operator []. The reason for that is that std::queue is a wrapper around a different STL container. It is the intention of the std::queue to hide its “inner” values and allow only access to front and back. This is OK for your normal purposes, but not for your wish to access “inner” members in the debugging case. The solution is easy. Select a different container and in this case and for your purposes, a std::deque. Is has also your needed functions, e.g. front, back. The push and pop functions have extended names, because there is a pop_front and a pop_back and a psuh_front and push_back. And, that is the point, it has iterators and an indexing operator []. Now you could make your program like that:

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct Task {
    int pid;
    int days;
    int depend;
    friend istream& operator>>(istream& is, Task& task) { return is >> task.pid >> task.days >> task.depend; }
    friend ostream& operator<<(ostream& os, const Task& task) { return os << task.pid << ' ' << task.days << ' ' << task.depend; }
};

int main()
{
    int t, i;
    cin >> t;
    std::vector<Task> task(t);
    for (i = 0; i < t; i++)
    {
        cin >> task[i];
    }
    deque<Task> job_queue;
    for (i = 0; i < t; i++)
        job_queue.push_back(task[i]);

    cout << "Queue size is: " << job_queue.size() << endl;
    // Option 1
    for (i = 0; i < t; ++i) {
        cout << task[i] << '\n';
    }
    // Option 2, more C++
    for (auto it = job_queue.begin(); it!=job_queue.end(); ++it){
        cout << *it << '\n';
    }
    // Or, even better, taking C++ range based for
    for (const auto& taskref : job_queue) {
        cout << taskref  << '\n';
    }
    return 0;
}

But that is not the end. In C++ you can use algorithms for everything. For input and output you can especially use std::istream_iterator and std::ostream:iterator and std::copy functions.

With that, and, this is maybe a final optimization, your program looks like:

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <iterator>

struct Task {
    int pid;
    int days;
    int depend;
    friend std::istream& operator>>(std::istream& is, Task& task) { return is >> task.pid >> task.days >> task.depend; }
    friend std::ostream& operator<<(std::ostream& os, const Task& task) { return os << task.pid << ' ' << task.days << ' ' << task.depend; }
};

int main()
{
    int numberOfTasks{ 0 };
    std::deque<Task> jobQueue{};

    std::cin >> numberOfTasks;

    // Read all task values
    std::copy_n(std::istream_iterator<Task>(std::cin), numberOfTasks, std::back_inserter(jobQueue));

    // For Debug purposes. Print job Queue
    std::copy(jobQueue.begin(), jobQueue.end(), std::ostream_iterator<Task>(std::cout, "\n"));

    return 0;
}

That is the "more-C++" solution.

I hope I could help you a little bit . . .

Trying to iterate through queue of object pointers in c++

Here:

for (std::deque<Node*>::iterator it=closedList.begin();it!=closedList.end();++it) {
    if (compare_states(it->getState(), currentNode->getState())) {

Because it is declared as

std::deque<Node*>::iterator it

the thing to which it refers is a Node*, not a Node, so it->foo would, if it could, access members of Node*, not of Node. Node has a member function getState, Node* does not, and because of this the expression

it->getState()

fails to compile. This is analogous to the way it would fail to compile if it were of type Node**. Use

(*it)->getState()

instead. *it is a Node*, the thing it points to has a member function getState, so thing->getState() works for it.

---

Related Topics