0

原点からの距離の昇順で並べ替えられた std::pair の並べ替えられたリスト

pair<float,float> origin;
list<pair<float,float> > points;
float distance=19.0f;

distance(19.0f) より大きい距離を持つリストの最初の要素を見つける方法は? リストバイナリ検索に適用するには? (反復は十分に効率的ではありません。リストは長いです) ? よりエレガントなソリューションはありますか?

4

6 に答える 6

3

リストは二分探索にはあまり適していません。これは、リスト内の要素に順番にしかアクセスできない(要素kから要素にしかアクセスできないk-1) ためです。そのため、リストを使用する必要がある場合は、より大きな最初の要素を直線的に検索する以外に選択肢はありません。よりもdistance。

二分探索を行いたい場合はvector、要素への直接アクセスを可能にするコンテナなどを使用できます (のようにmyvector[i])

于 2012-10-20T10:05:54.870 に答える
2

リンクされたリストで二分探索を行うことはできません。vectorまたはに置き換えることを検討してくださいmultiset。

于 2012-10-20T10:05:38.987 に答える
2

リンクされたリストでバイナリ検索を効率的に実行することはできません。これは、ランダム アクセス時間がO(n)であるのに対しO(1)、バイナリ検索が正しく機能するためには が必要だからです。

リストを反復処理する必要があります。別のデータ構造を選択しない限り、他に方法はありません。

于 2012-10-20T10:06:05.047 に答える
2

find_ifを使用します。前述のように、リスト内のランダムな要素にアクセスできないため、binary_searchon では使用できません。std::list

于 2012-10-20T10:07:39.283 に答える
1

boost::flat_set通常のベクトルの上に順序付けられたコンテナのセマンティクスを実装するものを使用できます。

于 2012-10-20T13:32:30.210 に答える