Increase the queue size and find the shortest queue

Question

I have a paradigm where in a loop of queues of a vector,if a condition is true for the ith queue, increase queuesize of that ith queue by 5 . After this operation i need to search the queue sizes of all queues and enqueue in the shortest queue. i want to do something like the code given below

#include <vector> 
#include <queue> 
int min_index = 0;
std::vector<std::queue<int> > q
std::size_t size = q.size();
for( i=0; i<size; i++){ 
    if(..) {// A condition is true
 //increase the size of the ith queue by 5 more times
}

if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(int)
}

how to increase the queue size artifically, if a condition is true? and then search the queues and find the shortest size queue.

UPDATED

#include <vector> 
#include <deque> 
int min_index = 0;
std::vector<std::deque<int> > q
std::size_t size = q.size();
for( i=0; i<size; i++){ 
   if(...) {// A condition is true
  q[i].resize(q[i].size() + 5)
}
if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(int)
}

"how to increase the queue size artificially" ? I'm hoping you mean the backing store the queue can hold data in but currently does not, because outside of that the only "size" increase you're going to get is item-occupancy, I.e. Push junk into the queue. — WhozCraig, Feb 20 '13 at 16:07
@WhozCraigSo a loop `if(..) {// A condition is true for(int j = 0; j < 5; j++) q[i].push(0);` will do? — billa, Feb 20 '13 at 16:15

score 3 · Accepted Answer · answered Feb 20 '13 at 16:21

3

It's not clear what you mean by 'increase the queue size'.

If you mean 'increase the capacity of the queue', you don't need to. The default underlying container of queue is a deque, which isn't a contiguous block in memory and thus doesn't suffer any issues with expansion, removing the need to reserve() in advance. See here for more detail on this.

So, the size of a queue is just the number of items in it. If you want to increase that, deque has a resize() function which either takes a specified value for all the new items as a parameter, or otherwise just value-initialises them.

answered Feb 20 '13 at 16:21

jam

3,640
5
34
50

@J20As you said deque will be a good option, so above i updated the question with answer,please check whether it can be done like that. I used vector of `deques` instead of `queues` and used the `resize()` to increase the size of the ith deque. And then i search for a shortest deque and enqueue in it – billa Feb 21 '13 at 13:41
Hang on, I think you've misunderstood what I wrote. `queue` is not a container - it's a container adaptor (sort of a wrapper around a container) which can be implemented using a few different container types for its internals. Your queue *is a* deque under the hood unless you specified a different underlying container type when you made it. So you don't need to change anything. – jam Feb 21 '13 at 13:46
@J20Actually i need to increase the size of the ith queue (not the capacity) before finding the shortest queue (as this paradigm is related to scheduling of the tasks in multple local queues of threads). so i need like if a condition is true increase the size of the ith queue and search the shortest queues. – billa Feb 21 '13 at 13:57
@J20yeah, and just for discussion, i read somewhere 'using a Deque, you can model a queue as well as a stack' so what is difference in using a deque and queue. – billa Feb 21 '13 at 14:03
1

Can't move to chat due to rep, so I'll try to be brief. `Queue` is a container adaptor for general FIFO structure. Under the hood, depending on your particular needs, you could use any container type that meets its requirements (i.e. ability to get the first and last elements, and to add at the back/pop off the front). `Deque` (double-ended queue) is one of a few containers that meet those requirements, but it also allows pushing at the front and popping off the back (hence the 'double-ended' in the name). – jam Feb 21 '13 at 14:15
great thank you :) and i found the detailed explanation here too http://stackoverflow.com/questions/2247982/deque-vs-queue-in-c?rq=1 – billa Feb 21 '13 at 14:19

score 1 · Answer 2 · answered Feb 20 '13 at 16:17

Here is a possible way of doing that (assuming C++11 is an option, otherwise the example is easily rewritten without lambdas and auto):

#include <vector>
#include <queue>
#include <algorithm>

// Don't use this in your real code: I use it here just for convenience.
// It is a bad programming practice to import a whole namespace (especially
// if it is a Standard Library namespace).
using namespace std;

// The function that defines your condition on each queue
bool cond_on_q(queue<int> const& q)
{
    bool satisfied = false;
    // Determine whether the condition is satisfied...
    return satisfied;
}

int main()
{
    vector<queue<int>> v = ...; // Initialize your vector of queues somehow

    // Iterate over the vector of queues
    for (auto& q : v)
    {
        if (cond_on_q(q)) // Is the condition satisfied?
        {
            // Insert 5 elements with any valid value (for instance, 0)
            for (int i = 0; i < 5; i++) (q.push(0));
        }
    }

    // Determine the queue with the minimum size.
    auto i = min_element(begin(v), end(v),
        [] (queue<int> const& q1, queue<int> const& q2) { 
            return q1.size() < q2.size(); 
            }
        );

    int newValue = ...; // Initialize the value to be enqueued somehow.        

    // Add the value to the queue with minimum size.
    i->push(newValue);
}

Increase the queue size and find the shortest queue

2 Answers2