5

によって提供される対数の代わりに線形時間がかかるため、std::find(some_map.begin(), some_map.end())orを使用しないでください。同様のことが で発生します:ソート用の関数がありますが、イテレータはランダム アクセスではないため、を呼び出すことができません。std::lower_boundsome_map.lower_boundstd::liststd::list::sortstd::sort(some_list.begin(), some_list.end())

ただし、std::swapたとえば、 には標準コンテナーのオーバーロードがあるため、 の呼び出しはswap(some_map, other_map)O(n) ではなく O(1) を取ります。C++ 標準がマップとセットlower_boundの特殊なバージョンを提供しないのはなぜですか? find深い理由がありますか？

4

4 に答える 4

3

STL が従う規則は、自由関数アルゴリズムがイテレータで動作し、イテレータが属する範囲のタイプ (イテレータ カテゴリ以外) を気にしないジェネリックであるということです。特定のコンテナー タイプが使用するよりも効率的に操作を実装できる場合、std::algo(cont.begin(), cont.end())その操作はコンテナーのメンバー関数として提供され、 として呼び出されcont.algo()ます。

したがって、 と がありstd::map<>::lower_bound()ます。std::map<>::find()std::list<>::sort()

于 2014-03-07T20:16:05.530 に答える
2

これらのオーバーロードを提供しないのには、適切な "設計哲学" の理由があります。特に、STL コンテナとアルゴリズムの相互作用全体は、異なるイテレータの概念を通過するように設計されているため、これら 2 つの部分は独立したままであり、すべてのアルゴリズムをオーバーロードすることなく新しいコンテナ タイプを定義できます。すべてのコンテナをオーバーロードする必要のない新しいアルゴリズム。

これらの設計上の選択を超えて、これらのアルゴリズム (並べ替え、下限など) を/listなどの特別なコンテナーに対してオーバーロードできない非常に技術的な理由があります。その理由は、通常、イテレーターを親コンテナーに明示的に接続する理由がないためです。つまり、リスト コンテナーからリスト イテレーター (begin/end) を取得できますが、リスト イテレーターからリスト コンテナー (への参照) を取得することはできません。同じことが map / set イテレータにも当てはまります。イテレータは、親コンテナに対して「ブラインド」になるように実装できます。たとえば、次のようなコンテナmapsetlist通常、データメンバーとして、ヘッドノードとテールノードへのポインター、およびアロケーターオブジェクトが含まれますが、イテレーター自体 (通常はノードへのポインターのみ) は、ヘッド/テールまたはアロケーターについて知る必要はありません。前/次のリンクポインタをたどって、リスト内を前後に移動します。したがって、std::sortfor のオーバーロードを実装する場合は、listsort 関数に渡された反復子からリスト コンテナーを取得する方法はありません。そして、あなたが言及したすべてのケースで、それらの特別なコンテナーに適したアルゴリズムのバージョンは、「ブラインド」イテレーター レベルではなく、コンテナー レベルで実行する必要があるという意味で「集中化」されています。そのため、メンバー関数として意味があり、反復子からそれらに到達できないのはそのためです。

ただし、コンテナーに関係なくこれらのアルゴリズムを呼び出す汎用的な方法が必要な場合は、必要に応じてオーバーロードされた関数テンプレートをコンテナー レベルで提供できます。次のように簡単です。

template <typename Container>
void sort_container(Container& c) {
  std::sort(begin(c), end(c));
};

template <typename T, typename Alloc>
void sort_container(std::list<T, Alloc>& c) {
  c.sort();
};

template <typename Key, typename T, typename Compare, typename Alloc>
void sort_container(std::map<Key, T, Compare, Alloc>&) { /* nothing */ };

//... so on..

ここでのポイントは、既に STL コンテナーに結び付けられている場合、必要に応じてこの方法で STL アルゴリズムに結び付けることができるということです...ただし、C++ 標準ライブラリがこの種のコンテナーを強制することを期待しないでくださいコンテナとアルゴリズムの間の相互依存。誰もがそれらを望んでいるわけではないためです (たとえば、多くの人は STL アルゴリズムが本当に好きですが、STL コンテナは好きではありません (多くの問題があります))。

于 2014-03-07T21:45:07.343 に答える
2

そのような関数がイテレータのペアに関して機能するという単純な事実は、マップ/セット イテレータに特化した場合でも、かなりのオーバーヘッドを生成します。

それを念頭に置いて：

  • このような関数は、begin/end だけでなく、反復子の任意のペアで呼び出すことができます。

  • マップ/セットの反復子は通常、リーフノードへのポインターとして実装されますが、メンバーfind/の開始ノードはツリーlower_boundのルートノードです。

ルート ノードへのポインターが map/set オブジェクトのメンバーとして直接格納されるため、メンバー find と lower_bound を使用する方が適切です。

仮想の非メンバーfindは、2 つの入力ノード間で最も低い共通の祖先を見つけるためにツリーをトラバースする必要があります。その後、[first,last) の範囲のみを検索するように注意しながら、dfs を実行する必要があります。これは非常にコストがかかります。 .

はい、イテレータ内のルートノードを追跡し、関数が begin/end ペアで呼び出された場合に最適化できます...メンバー関数を避けるためだけですか?

于 2014-03-07T21:17:19.603 に答える