comparing queue sizes in a vector

问题:

UPDATED

Having a logic that where a integer before gets enqueued to a queue in a vector, the loop of queues 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)

i am trying extend this logic 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.

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

}

how to implement this logic?

回答1:

The cleanest solution requires C++11:

std::min_element( 
        q.begin(),
        q.end(),
        []( std::queue<int> const& lhs, std::queue<int> const& rhs)
            { return lhs.size() < rhs.size(); } )
    ->push(value);

Even without C++11, I think I'd write a small predicate class to do what the lambda does, and use this.

EDIT:

Now that I have a better idea as to what is wanted, something like the following should do the trick:

class OrderInMap
{
    MultiQueue* myOwner;
public:
    OrderInMap( MultiQueue* owner )
        : myOwner( owner )
    {
    }
    bool operator()( int lhs, int rhs ) const
    {
        return myOwner->myQueues[ lhs ].size()
                < myOwner->myQueues[ rhs ].size();
    }
};

std::vector <std::queue<int>> myQueues;
std::vector <int> myMap;
int myCurrent;
bool myOrderIsValid;
OrderInMap myOrder;

int getIndexForPush()
{
    if ( ! myOrderIsValid || myOrder( myMap[0], myCurrent ) ) {
        myMap.push_back( myCurrent );
        std::push_heap( myMap.begin(), myMap.end(), myOrder );
        std::pop_heap( myMap.begin(), myMap.end(), myOrder );
        myCurrent = myMap.back();
        myMap.pop_back();
    }
    return myCurrent;
}

Since popping can change the order, you'll have to set myOrderIsValid to false when you pop (or perhaps only if after the pop, myOrder( poppedIndex, myMap.front() )).

Alternatively, you can do it by hand, and avoid the map (but you do have to keep two variables):

int myCurrent;
int myNext;

void order()
{
    if ( myQueues[myNext].size() < myQueues[myCurrent].size() ) {
        std::swap( myNext, myCurrent );
    }
}
int getQueueIndex()
{
    if ( ! myOrderIsValid || myQueues[myNext].size() < myQueues[myCurrent].size() ) {
        myCurrent = 0;
        myNext = 1;
        order();
        for ( int i = 2; i < myQueues.size(); ++ i ) {
            if ( myQueues[i].size() < myQueues[myNext].size() ) {
                myNext = i;
                order();
            }
        }
    }
    return myCurrent;
}

This is probably slower than maintaining the heap, but even with a very large number of queues, I'm not sure the difference will be noticeable.