1

i just implement a logic where a integer before gets enqueued to a queue, the loop of queues in a vector is searched and integer is enqueued to a queue which has minimum size among the queues. the following code shows the operation.

#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
int min_index = 0;
std::size_t size = q.size();
for( i=0; i<size; i++){ //accessing loop of queues
    if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(int)

now additionally i would like to extend my paradigm with a condition that the integers should get continued to enqueue in the shortest queue while the condition is true that the shortest queue's size is less than or equal to any another queue's size in the loop of queues.

want to do something like the code shown below

#include <vector> 
    #include <queue> 
    std::vector<std::queue<int> > q
    int min_index = 0;
    std::size_t size = q.size();
    for( i=0; i<size; i++){ //accessing loop of queues
        if(q[min_index].size() > q[i].size())
            min_index = i

    while(q[min_index].size <= q[some_other_index].size() )
    {
        q[min_index].push(int);

}

i think i should find successive minimas of the loop and compare it in the while loop? but i don't know how to proceed to mind find successive minimas.

continuation of this question as i didn't ask the question clearly comparing queue sizes in a vector

4

1 に答える 1

2

If the other queues aren't changed while your loop is ongoing, you can use the initial minimum-search to find the two shortest queues. Something like: 

std::size_t min_index = 0;
std::size_t second_shortest_index = 0;
std::size_t size = q.size();
for( i=0; i<size; i++){ //accessing loop of queues
    if(q[min_index].size() > q[i].size()) {
        second_shortest_index = min_index; 
        min_index = i; // Now q[min_index] is the shortest queue
    } else if (q[second_shortest_index].size() > q[i].size()) {
        second_shortest_index = min_index;
    }
}

You can then use second_shortest_index as your some_other_index. This will still require you to search a new second-shortest queue, when you hit that limit (as there may be multiple shortest or second-shortest elements)

If you can reorder your vector<queue> or using an index vector with an indirect comparator, you could use std::make_heap and related functions to keep track of smallest queue much more easily.

于 2013-02-15T16:06:28.133 に答える