比较向量中的队列大小 [英] 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);

}

如何实现此逻辑？

推荐答案

最干净的解决方案需要C ++ 11：

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

即使没有C ++ 11，我想我会写一个小的谓词类到
做什么lambda做，并使用这个。

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

现在我有一个更好的想法，什么是想要的东西
像下面这样应该做的诀窍：

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

由于弹出可以更改顺序，因此您必须设置$ b $当你弹出（或者可能只有在
之后的弹出， myOrder（poppedIndex，myMap.front（）） myOrderIsValid / code>）。

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.

这篇关于比较向量中的队列大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！