Modern C++チャレンジ ―C++17プログラミング力を鍛える100問

6章アルゴリズムとデータ構造

問題

　優先度付きキュー

優先度付きキューを表すデータ構造を書きなさい。優先度が最大の要素の取得が定数時間に、要素の追加削除が対数時間計算量になるようにしなさい。キューは新たな要素を末尾に挿入し、先頭から要素を削除します。デフォルトでは、キューは要素を比較するためにoperator<を用いますが、第1引数が第2引数より小さいとtrueを返す比較関数オブジェクトをユーザが与えることができるようにしなさい。実装では、少なくとも次の操作ができなければなりません。

• push()：新たな要素の追加
• pop()：先頭要素の削除
• top()：先頭要素へのアクセス
• size()：キューにある要素の個数
• empty()：キューが空かどうか

　リングバッファ

固定長のリングバッファ（ring buffer, circular buffer）を表すデータ構造を作りなさい。リングバッファでは、固定サイズを超えて要素が追加されると既存の要素を上書きします。クラスには次の機能が含まれます。

• デフォルトコンストラクタを禁止する
• 指定したサイズのオブジェクトの作成をサポートする
• バッファの容量と状態をチェックする（empty(), full(), size(), capacity() ...