質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.91%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 272

ratera

score 18

事象

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;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+3

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実装は、
実は真面目にソートせずヒープで済ませることで処理時間を抑えています。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/07 19:02 編集

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

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

    キャンセル

  • 2020/07/07 19:48

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

    キャンセル

  • 2020/07/07 20:57 編集

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

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

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

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

    キャンセル

+1

[余計なお世話]

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()した順に取り出されることはないんですわー

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/09 13:24

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

    実際のところ、優先度順とはなんぞや?となっていました。
    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;
    }
    };

    キャンセル

  • 2020/07/09 13:31

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

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

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