priority_queueの各要素を表示する方法、またはpush()時に再ソートされるかどうか知りたい

Question

事象

VScodeのデバッガを利用して、priority_queueに対してpush()したときに、ソートされる場合とされない場合があります。

■更新されない場合(13行目のステートメントのpushで更新）

■更新される場合(15行目のステートメントのpushで更新）

質問事項

• priority_queueはクラスとは違うため、どのように要素を出力したらよいのか教えてほしい。

//for (int i = 0;i < Q.size();i++) printf("%d des",Q[i]);だとエラーに当然なりました。

• priority_queueのソートタイミングがいつなのか知りたいが、（デバッガでも確認できず、）知りたい。

####　コード

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    // 例 1: Q に色々な操作を行う（x1 = 116, x2 = 110, x3 = 122, x4 = 2 となります）
    priority_queue<int, vector<int>, greater<int>> Q;
    Q.push(116); // この時点で、小さい順に {116}
		//for (int i = 0;i < Q.size();i++) printf("%d des",Q[i]);
    Q.push(145); // この時点で、小さい順に {116, 145}
    Q.push(122); // この時点で、小さい順に {116, 122, 145}
    int x1 = Q.top();
    Q.push(110); // この時点で、小さい順に {110, 116, 122, 145}
    int x2 = Q.top();
    Q.pop(); // この時点で、小さい順に {116, 122, 145}
    Q.pop(); // この時点で、小さい順に {122, 145}
    int x3 = Q.top();
    int x4 = Q.size();

    cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl;
    return 0;
}

Answer 1

priority_queue のハラワタを晒す方法:

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
class my_priority_queue : public std::priority_queue<_Ty, _Container, _Pr> {
public:
  const _Container& guts() const {
    return this->c; // コレがハラワタ。protectedメンバなので導出クラスなら晒せる。
  }
};

// ハラワタをプリントする
template<typename C>
void print(const C& cont) {
  for ( const auto& item : cont ) {
    std::cout << item << ' ';
  }
  std::cout << std::endl;
}

int main() {
    // 例 1: Q に色々な操作を行う（x1 = 116, x2 = 110, x3 = 122, x4 = 2 となります）
    my_priority_queue<int, vector<int>, greater<int>> Q;
    Q.push(116); // この時点で、小さい順に {116}
    print(Q.guts());
    Q.push(145); // この時点で、小さい順に {116, 145}
    Q.push(122); // この時点で、小さい順に {116, 122, 145}
    int x1 = Q.top();
    Q.push(110); // この時点で、小さい順に {110, 116, 122, 145}
    int x2 = Q.top();
    print(Q.guts());
    Q.pop(); // この時点で、小さい順に {116, 122, 145}
    Q.pop(); // この時点で、小さい順に {122, 145}
    int x3 = Q.top();
    int x4 = Q.size();
    cout << "---------------\n";
    cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl;
    return 0;
}

[追記]

priority_queueのソートタイミングがいつなのか知りたいが、（デバッガでも確認できず、）知りたい。

多くのpriority_queue実装は、
実は真面目にソートせずヒープで済ませることで処理時間を抑えています。

ひとつづつ取り出すことしかできないので、
「その時点でいちばん大きい(小さい)ひとつだけが特定できればいい」
ちゅーわけで、真面目にソートせんでもえぇのです。

Comments

[ratera]

なるほどおおおおおおです。
ヒープだから、ソートされてたりされてなかったりするんだ。
裏っかわの事情に考えを至らせることも大事ですね！勉強になります！ありがとうございます！

（ハラワタを出せるぷよぐらみんぐが早くできるようになりたい。。。どのくらいの経験を積めばいけるのか今のところさっぱりですががが！）

[episteme]

少なくとも priority_queue に関する限り、ヘッダ読めばその実装バレバレです。
ちーとキツいが眺めてみる価値はありますぜ。

[ratera]

へへ、これは良いことききやした。

なんやかんや初めてQ.push()の定義にお邪魔してみたところ、push_heapってめっちゃ書いてあったー。
その先は神々のおわす世界でしたが( ;∀;)、とりあえずどんなアルゴリズムが使われているかだけなら簡単にわかる！すごい！感謝です！

[episteme]

そのかわり、priorityの等しい複数の要素がpushされた場合、その順序は不定となります。

[ratera]

微修正ありがとうございます。

一番大きいもの（ツリー状の根に当たる部分）の順序のみ担保されていて、
それ以外については不定の場合があるという理解をしました！

まずは、ヒープソートを実際に手を動かしてならべ直したら、怪しい箇所をきちんと理解できる気がします。
たぶん木構造の深さが同じ個所は、順序は怪しそうな気がしています！

（int以外の比較できないものの話をされているのかもしれませんが、こちらはまた後日ぶちあたってから考えることにします。）

Answer 2

[余計なお世話]

priorityの等しい複数の要素がpushされた場合、その順序は不定となります。

の解説。

たとえば int値の 一の位を優先度として priority_queue を使うと:

#include <iostream>
#include <queue>

struct priority_compare {
  bool operator()(int x, int y) const {
    return x % 10 < y % 10;
  }
};

int main() {
  std::priority_queue<int,std::vector<int>,priority_compare> Q;

  // 10, 11, 12, ... 49 を Qに投げ込む
  for ( int i = 10; i < 50; ++i ) Q.push(i);

  // 優先度の高いものから取り出す
  while ( !Q.empty() ) {
    std::cout << Q.top() << ' ';
    Q.pop();
  }
}

期待する結果は 19, 29, 39, 49, 18, 28, ... なのですが
実際は:

19 39 29 49 38 18 28 48 37 17 47 27 36 16 46 26 45 15 35 25 24 14 44 34 33 43 13 23 22 32 12 42 41 21 31 11 10 40 20 30

優先度が等しい複数の要素がpush()した順に取り出されることはないんですわー

Comments

[ratera]

わーい、ありがとうございます！。

実際のところ、優先度順とはなんぞや？となっていました。
greater<int>などの場合は数の大きさなのであまり意識しなくてよかったので。

今回だと優先度と数値を持ったqueueがいくつもあって、まさに優先度がかぶるケースという話ですね！

別口の質問になりますが、priority_queueの[containerの概念](https://programming-place.net/ppp/contents/cpp/library/012.html
)や、頂いた以下の構造体の読み方など、文法入門書から外れるものは1時間くらい調べても理解にいたりません。

手持ちは柴田望洋先生のC++入門くらいなのですが、もし調べるたりステップアップするうえでオススメ書籍があれば教えていただけるとうれしいです！

>
struct priority_compare {
bool operator()(int x, int y) const {
return x % 10 < y % 10;
}
};

[episteme]

関数オブジェクトとかファンクタと呼ばれるもので、あたかも関数のようにふるまいます。

priority_compare pc;
bool result = pc(15,52); // 15%10 < 52%10 の結果(bool)を返す。