Boost.Heapが採択されてた - Faith and Brave

いつの間にかレビューが行われて結果が出てました。
Boost.Heapは、プライオリティキューの実装で、std::priority_queueと比べて以下の特徴があるそうです：

このライブラリのレビュー結果は以下：

Tim BlechmannのHeapライブラリのレビューが完了した。

多くの人々がメーリングリスト上やCode Collaboratorツールなどで問題点をコメントしたが、4票のみが提出された。しかし、寄せられたコメントからは、リジェクトすべきような設計上、実装上の問題は見つからなかった。結果として：

Boost.HeapライブラリをBoostに採択する

投票は以下のメンバによって行われた：
Phil Endecott
Daniel Russel
Thomas Klimpel (条件付き)
Andrew Sutton

レビューの課程で受け取った他のコメントでは、対処すべき技術的な問題などが挙げられたが一般に肯定的だった。レビュー中に発見された技術的な問題に対処した最終バージョンは、完全に受け入れられる。

以下は、技術的な懸念事項の要約である：

ペアリングのヒープは、製品コードで使用できない可能性がある、スタックオーバーフローに関する既知の問題を持っている。再帰の問題が十分に解決できないなら、データ構造が非常に強い警告ラベルを持つべきだ(たとえば、実験用ディレクトリに置くなど)。

b_heap vs d_ary_heap vs priority_queueのパフォーマンスは、もっとよく特徴付けされる必要がある。どのような状況下でどれが他より優れているのか。もしb_heapが他より優れているという説得力があるシナリオが見いだせないなら、それは同じく実験用ディレクトリに置かれる必要がある。

ヒープのコンセプトは、レビューツールに関するコメントにしたがって再考される必要がある。コンセプトはまた、操作だけでなくインタフェースのセマンティクスを記述する必要がある。

ヒープの安定性の実装についてのコメントがいくつかあった。3つの選択肢が判明した：(例は出せないが)"自然に安定した"ヒープ、現在のカウンタベースのアプローチ、およびチェーンのアプローチ。再考の実装戦略についての合意はない。カウンタベースのアプローチは、おそらくほとんどのアプリケーションで十分だが、それは普遍的に望ましいものではない。代替戦略のより徹底的な調査を推奨する。これはライブラリドキュメントの"Future Work"セクションに記述することで許容できる。

Mergeableヒープの概念は、少なくてもO(n)でマージできるものとO(log n)の時間内にマージできるものを区別する必要がある。提案された解決は、マージを一般的なヒープアルゴリズムとして書き、メンバ関数mergeを呼び出すことによってMergeableヒープを特殊化することだ。また、mergeは破壊的に行う必要があるため、mergeとclearが必要とされるべきではない。

ドキュメントはヒープデータ構造の設計(たとえばコンセプト)や、mutableヒープ、ベストプラクティスなどについて大幅に改善する必要がある。それはまた、別のヒープのための理論とパフォーマンスの比較を提供する必要がある。

ドキュメントに、ベンチマークツールのドキュメントを含めてほしい。これはユーザーがホストまたはターゲットのアーキテクチャ上でさまざまなヒープの実装を評価することに有益である可能性がある。

このライブラリの長期的に考慮されるべき他の提言があった。

Thorsten Ottosenは、std::stack、std::queueおよびstd::priority_queueの線に沿って、b_heapとb_ary_heapのパラメータ化が可能なコンテナアダプタを作ることを提案する。その後の議論には、そうすることでいくつかの非実用性があること、すなわち他のポリシー(例えば、安定性)を無効にすることができる。

Phil Endecottは、他のメモリ構造のヒープ構造の定式化をサポートするために、(ランダムアクセス)Rangeで動作する、より一般的なアルゴリズムの面でいくつかのヒープ(b_heapとd_ary_heap)を書き換えることを提案した。これを行うことは、Thorstenの要求を満たすヒープの定義に役立つだろう。

私はPhilの提案を調査することを強く勧める。しかしこれはacceptの障壁ではない。この機能はライブラリの将来的なリビジョンで追加される可能性がある。

Timの仕事と、レビュー投稿を確認することに時間がかかってしまったが、コミュニティのメンバに感謝したい。また、辛抱強く私たちの質問に対処してくれたTimに再度感謝する。