已更新
具有这样的逻辑,即之前的整数被排队到 vector 中的队列中,搜索队列循环并将整数排队到队列中具有最小大小的队列。下面的代码展示了操作过程
#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);
}
如何实现这个逻辑?
最佳答案
最干净的解决方案需要 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 所做的事情,并使用它。
编辑:
现在我对想要什么有了更好的想法, 像下面这样应该可以解决问题:
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() )
)。
或者,您可以手动完成,并避免使用 map (但您 必须保留两个变量):
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++ - 比较 vector 中的队列大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14894658/