comparer la taille des files d’attente dans un vecteur

MIS À JOUR

Avec une logique dans laquelle un entier avant est mis en queue dans une queue d’un vecteur, la boucle de files d’attente est recherchée et l’entier est mis en queue dans une queue de taille minimale entre les files d’attente. Le code suivant montre l’opération

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

J’essaie d’étendre cette logique avec une condition selon laquelle les entiers doivent continuer à être mis en queue dans la queue la plus courte alors que la condition est vraie que la taille de la queue la plus courte est inférieure ou égale à celle d’une autre queue dans la boucle de files d’attente.

je veux faire quelque chose comme le code ci-dessous

 #include  #include  std::vector<std::queue > q int min_index = 0; std::size_t size = q.size(); for( i=0; i q[i].size()) min_index = i while(q[min_index].size <= q[some_other_index].size() ) { q[min_index].push(int); } 

comment implémenter cette logique?

La solution la plus propre nécessite C ++ 11:

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

Même sans C ++ 11, je pense que je rédigerais une petite classe de prédicats pour faire ce que le lambda fait, et l’utiliser.

MODIFIER:

Maintenant que j’ai une meilleure idée de ce qui est voulu, voici ce qui devrait faire l’affaire:

 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 > myQueues; std::vector  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; } 

Étant donné que popping peut changer la commande, vous devez définir myOrderIsValid sur false lorsque vous effectuez un pop-up (ou peut-être seulement après la pop, myOrder( poppedIndex, myMap.front() ) ).

Alternativement, vous pouvez le faire à la main et éviter la carte (mais vous devez garder deux 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; } 

C'est probablement plus lent que de maintenir le tas, mais même avec un très grand nombre de files d'attente, je ne suis pas sûr que la différence sera perceptible.