1

STL 和提升优先级队列的接口包括

T const &   top () const;
void    pop ();

后者删除顶部元素。但是，如果我想在 pop() 之后继续使用该元素，并且想避免复制呢？例如，假设我有一个priority_queue<T> pq. 我想写

const T& first = pq.top();      
pq.pop();
const T& second = pq.top();
analyze(second);
analyze(first);      // first *after* second

不幸的是，一旦我 pop()，第一个引用就变得无效，所以我得到一个段错误。

我更喜欢 java's 之类的解决方案nextElement()，它返回top()并执行 a pop()，但仅当元素超出范围时才会删除该元素。这样我就不需要跟踪什么pop()和什么时候。但是，usingpriority_queue<shared_pointer<T> >似乎没有帮助，因为将 ref 指向 ashared_pointer并不会增加其 use_count。

如果它很重要，我更喜欢使用boost::fibonacci_heap它的高效push().

任何想法或指示？谢谢！

4

3 回答 3

0

您是否允许使用支持 std::move 的编译器？

int main()
{       
    std::priority_queue<std::string> str_q;
    str_q.push("aaa");
    str_q.push("bbb");
    str_q.push("ccc");
    std::string strs[3];

    strs[0] = std::move(const_cast<std::string&>(str_q.top()));
    std::cout<<str_q.top()<<std::endl;
    str_q.pop();
    strs[1] = std::move(const_cast<std::string&>(str_q.top()));
    std::cout<<str_q.top()<<std::endl;
    str_q.pop();
    strs[2] = std::move(const_cast<std::string&>(str_q.top()));
    std::cout<<str_q.top()<<std::endl;
    str_q.pop();

    for(auto const &data : strs){
        std::cout<<data<<std::endl;
    }            

    return 0;
}

编辑答案，因为返回类型是 std::string const&，它不能被移动，至少我们抛弃了 constness。

于 2013-03-30T02:21:16.213 回答
0

如果你愿意承担增加的成本，use count那么据我所知，我boost::shared_ptr会这样做std::shared_ptr：

#include <iostream>
#include <vector>
#include <memory>
#include <queue>
#include <boost/shared_ptr.hpp>

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

int main()
{
   //std::priority_queue< std::shared_ptr<int>, std::vector< std::shared_ptr<int> >, deref_less< int >  > pq ;
   std::priority_queue< boost::shared_ptr<int>, std::vector< boost::shared_ptr<int> >, deref_less< int >  > pq ;

    boost::shared_ptr<int>
      sp1( new int(10)),
      sp2( new int(11)),
      sp3( new int(3))
      ;

      pq.push(sp1) ;
      pq.push(sp2) ;
      pq.push(sp3) ;

      std::cout << *pq.top() << std::endl ;

      std::cout << sp2.use_count() <<std::endl ;

      //std::shared_ptr<int> sp4( pq.top() ) ;
      boost::shared_ptr<int> sp4( pq.top() ) ;

      std::cout << sp2.use_count() <<std::endl ;

      pq.pop() ;

      std::cout << sp2.use_count() <<std::endl ;
      std::cout << *sp4 << std::endl ;
}

在线std版本在这里

于 2013-03-30T03:02:27.910 回答
0

使用fibonacci_heap，您可以使用有序迭代器并将元素保留在堆中，直到完成。

auto it = heap.ordered_begin();
const T& first = *it;  // picking up ref to first element
const T& second = *++it;  // and to second element
analyze(first, second);
heap.pop();  // and now drop them
heap.pop();
于 2013-03-30T03:24:12.283 回答