c++ 使用std::priority_queue和std::reference_wrapper

0x6upsns  于 2023-04-01  发布在  其他
关注(0)|答案(2)|浏览(96)

我有一个std::vector<Server>,我填充它,然后在我的程序的其余部分中永远不会改变。
我想在优先级队列中使用这些,但我需要身份语义;复制Server对象会创建我无法正确使用的新对象。基本上:

  • Server对象可由done成员(类型double,表示时间)排序,Server实现operator <operator >
  • 我将重复地将Server对象放入优先级队列并将它们取出
  • 这允许我从优先级队列中取出一个具有最早done时间的队列
  • 我从不将Server放入队列两次(如果有关系的话)
  • Server在优先级队列中时,done时间永远不会更改,只有当Server在队列外时才会更改
  • 我需要能够在将Server对象从队列中取出时直接访问它,而不是通过vector

我读到std::reference_wrapper可以在std::vector和其他容器中使用。但是当Server对象在reference_wrapper中时,我似乎无法让优先级队列识别它们的顺序关系。
有办法解决吗?下面是我的程序的相关部分:

class Server {
private:
    ...          // other members
    double done; // done time
public:
    ...
    double next_free(void) const { return done; }
    bool operator < (const Server& other) const {
        return done < other.done;
    }
    bool operator > (const Server& other) const {
        return done > other.done;
    }
};

...

int main(int argc, char **argv) {
    
    ...
    
    std::vector<Server> servers;
    for (int i = 0; i < 10; ++i)
    {
        Server server(i,i,0.01);
        servers.push_back(server);
    }
    typedef std::reference_wrapper<Server> ServerRef;

    std::priority_queue<ServerRef, std::vector<ServerRef>, std::greater<ServerRef>> pq;
    for (auto it = servers.begin(); it < servers.end(); ++it)
    {
        pq.push(std::ref(*it));
    }

...
}

如果我注解掉包含pq.push的for循环,那么我的程序编译,但否则我会从clang得到一堆错误,从以下开始:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/functional:742:21: error: 
      invalid operands to binary expression ('const std::__1::reference_wrapper<Server>' and 'const
      std::__1::reference_wrapper<Server>')
        {return __x > __y;}
                ~~~ ^ ~~~
baubqpgj

baubqpgj1#

std::reference_wrapper没有为它定义比较运算符,所以你必须提供自己的比较运算符。你可以使用lambda表达式来实现:

auto ServerRefCmp = [](const ServerRef& lhs, const ServerRef& rhs) { return lhs.get() > rhs.get(); };

然后,您可以将其提供给priority_queue,如下所示:

std::priority_queue<ServerRef, std::vector<ServerRef>, decltype(ServerRefCmp)> pq;

如果你不想使用lambda表达式,你可以写你自己的仿函数:

struct ServerRefCmp
{
    bool operator()(const ServerRef& lhs, const ServerRef& rhs) const
    {
        return lhs.get() > rhs.get();
    }
};

std::priority_queue<ServerRef, std::vector<ServerRef>, ServerRefCmp> pq;
eoigrqb6

eoigrqb62#

我想我只需要为ServerRef定义operator >

typedef std::reference_wrapper<Server> ServerRef;

bool operator >(const ServerRef& lhs, const ServerRef& rhs)
{
    return lhs.get() > rhs.get();
}

相关问题