4

使用 std::priority_queue top() 时,它返回一个常量引用。那么有没有办法既可以利用 std::priority_queue 又可以更改 top() 的值?

4

1 回答 1

2

我必须首先澄清关于关联容器的一点,但现在我终于能够写出我对这个问题的答案了。

@Xymotech 的评论中已经概述了修改作为关联容器一部分的对象的键时的基本策略。您复制/检索元素,将其从容器中删除,对其进行修改,最后将其重新插入容器中。

您的问题和评论中关于使用指针的想法表明复制对象可能很昂贵,因此您还应该知道可以使用指针来提高效率,但您仍然需要应用上面的基本方案。

考虑:

template< typename T >
struct deref_less
{
  typedef std::shared_ptr<T> P;
  bool operator()( const P& lhs, const P& rhs ) { return *lhs < *rhs; }
};

std::priority_queue< std::shared_ptr< MyClass >,
                     std::vector< MyClass >,
                     deref_less< MyClass > > pq;

现在如果你想修改 的一个对象MyClass,你仍然需要

auto e = pq.top();
pq.pop();
e->modify( 42 );
pq.push(e);

但是如果MyClass复制成本很高,使用std::shared_ptr自定义比较器可能有助于使其更快。

于 2013-03-29T11:01:52.243 回答