priority_queueを、その基になるコンテナを消去してクリアできますか？

Question

次のコードは:: PRIORITY_QUEUEはstdと内部std::vectorのclear()

#include<iostream> 
#include<queue> 
using namespace std; 
template<class type> 
struct mypq :public priority_queue<type> { 
    void clear(){ 
     this->c.clear(); 
    } 
}; 
mypq<int>pq; 
int main() { 
    for(int i=0;i<10;++i) 
     pq.push(i); 
    pq.clear(); 
    for(int j=-5;j<0;++j) 
     pq.push(j); 
    while (!pq.empty()){ 
     cerr<<pq.top()<<endl; 
     pq.pop(); 
    } 
} 

を呼び出しclear() Iは、G ++、MSVC++と打ち鳴らすでそれを試験した場合、それは予想される出力を生成し提供する継承します

-1 
-2 
-3 
-4 
-5 

を

しかし、これは保証されていません。つまり、内部ベクトルをクリアすることは、priority_queueが空でない場合はpop()を呼び出すのと同じです。私はスワップや空のpriority_queueを使ってそれを割り当てるなどの他の方法を知っていますが、このコードがうまくいくとすれば、ベクトルの割り当てられたメモリが再利用可能であるので効率的です。だから私はこのコードが移植性があるのか​​、いつもうまくいかないのだろうかと思います。

Answer 1

非常に良い質問です。私は厳密なが正しい方法であることを保証するとは思われませんが、それはあると考えるいくつかの理由があります。

例えば、operator=のためのドキュメントを考えてみます。

コピー代入演算子を。内容を の内容のコピーで置き換えます。効果的にc = other.c;を呼び出します。他のキューは、異なるサイズのものであってもよいので、（暗黙 宣言）

、これは本質的に大きさに依存しない内部状態が存在しないことを意味します。さらに、空のキューを割り当てることは、本質的にコンテナを空のキューに置き換え、それ以外は何もしないことを意味する。

これを念頭に置いて、優先度キューの合理的な実装では、キューのサイズを除いて状態を維持する必要はほとんどありませんので、基になるコンテナをクリアすることは有効であると見なすことができます待ち行列を空にする方法。

Answer 2

しかし、私は内部ベクトルをクリアすることは、priority_queueが空でないときにpop()を呼び出すのと同じであることを保証していません。

これは同じではないためです。 A std::priority_queueは厳密な弱い順序で注文するように特別に設計された容器アダプターです。キューに含めるコンテナのタイプを指定しない場合（この例では指定しない）、デフォルトのタイプはstd::vectorです。

したがって、空でない優先順位キューで呼び出すと、キューから一番上の要素が削除され、基になるコンテナでclear()を呼び出すと、一番上だけでなくすべての要素がキューから削除されます。

Iは、スワップとしてそれをオフまたは空PRIORITY_QUEUEを使用して割り当てる他の方法を知っているが、私はこのコードがうまく機能することができる場合、ベクターに割り当てられたメモリが再利用可能であるので、それがより効率的であろうと思います。だから私はこのコードが移植性があるのか​​、いつもうまくいかないのだろうかと思います。referenceによると、基礎となるcメンバオブジェクトがそのように、あなたが（逸話、それは古いバージョンでg++ 4.2.1上で動作つまり、this->c.clear();を呼び出すと、ポータブルである必要があり、コンパイラ間で保証する必要がありますされている方法にアクセスして、保護されて

OpenBSDの）

効率に関する限り、それは多少依存します。 this->c.clear();対q = priority_queue <int>();のようなものを使用すると、メモリの使用量や複雑さが異なることはありませんが、確認するには異なるプラットフォームでテストする必要があります。しかし、this->c.clear();対while(!q.empty()) { q.pop(); }のようなものを実行すると、はより効率的になります。メモリ効率の点で

、プライオリティキューのpop機能は、基礎となるコンテナpop_back関数を呼び出し、そしてpop_backもclearどちらも基本的なベクトルのcapacityに影響を与え、そのために持っていたことにする任意の「貯蓄」は本当に存在しません方法;これにより、特定の必要性がある場合にベクトルをサイズ変更して容量を増減することができます。

ただ、プライオリティキューpop機能が基礎となるコンテナpop_back関数を呼び出して、空の容器にpop_backを呼び出すと未定義の動作であることを覚えておいてください。

希望に応じることができます。