priority_queue 解答ページ | Programming Place Plus C++編【標準ライブラリ】 第12章

トップページC++編

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 と更新されており、今後も 3年ごとに更新されます。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。

問題①

問題① 要素の型が std::string で、文字列の長さが短いものほど優先度が高い priority_queue を作成してください。


std::string を <演算子などで比較できますが、それだと文字の順序(たとえば、‘a’ は ‘b’ より前に来るとか)が、優先度に影響を与えてしまいます。ここでは文字数だけを問題にしたいので、独自の比較処理を定義しないといけません。

#include <iostream>
#include <queue>
#include <string>

class StringLengthCompare {
public:
    inline bool operator()(const std::string& a, const std::string& b) const
    {
        return a.length() > b.length();
    }
};


typedef std::priority_queue<std::string, std::vector<std::string>, StringLengthCompare> StringPrioQueue;

int main()
{
    StringPrioQueue strPrioQueue;

    strPrioQueue.push("xxx");
    strPrioQueue.push("xx");
    strPrioQueue.push("xxxx");
    strPrioQueue.push("yy");
    strPrioQueue.push("yyy");
    strPrioQueue.push("zzzzz");

    while (!strPrioQueue.empty()) {
        std::cout << strPrioQueue.top() << std::endl;
        strPrioQueue.pop();
    }
}

実行結果

xx
yy
yyy
xxx
xxxx
zzzzz

“xx” と “yy”、“xxx” と “yyy” のように、優先度が同じになるものがあります。登録順は x系が先になっていますが、出力結果では混在しちえるので、優先度が同じ場合にどちらが先に取り出されるかは不定です。


参考リンク


更新履歴

’2015/10/18 新規作成。



第12章のメインページへ

C++編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る