2

更新しました

前に整数がベクトルのキューにエンキューされるというロジックを持つと、キューのループが検索され、キューの中で最小サイズのキューに整数がエンキューされます。次のコードは、操作を示しています

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

キューのループ内の最短キューのサイズが別のキューのサイズ以下であるという条件が真である間、整数が最短キューにエンキューされ続ける必要があるという条件でこのロジックを拡張しようとしています。

以下のコードのようなことをしたい

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

}

このロジックを実装する方法は？

4

1 に答える 1

3

最もクリーンなソリューションには 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 がなくても、ラムダが行うことを実行する小さな述語クラスを作成し、これを使用すると思います。

編集：

何が必要かについてより良いアイデアが得られたので、次のようなものがうまくいくはずです。

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

ポップすると順序が変わる可能性があるため、 myOrderIsValidポップするときは false に設定する必要があります (または、おそらくポップの後のみmyOrder( poppedIndex, myMap.front() ))。

または、手動でマップを回避することもできます (ただし、2 つの変数を保持する必要があります)。

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

これはおそらくヒープを維持するよりも遅くなりますが、キューの数が非常に多い場合でも、違いが顕著になるかどうかはわかりません.

于 2013-02-15T12:43:16.967 に答える