3

標準テンプレート ライブラリはコンパイラごとに異なる方法で実装されていると言われましたが、これは正しいですか?

(たとえば) セット コンテナーが赤黒木ではなく連結リストで実装されている場合、計算の複雑さ (時間と空間の両方) をどのように観察できますか?

私は何か見落としてますか？

4

5 に答える 5

11

すべての C++ コンパイラには、C++ 標準ライブラリの実装が付属しています。一部の実装は他の実装に基づいていますが、一部は独立しています。

ただし、それらはすべて標準を実装する必要があります。また、標準には、さまざまな機能に必要な特定の複雑な仕様があります。Aは純粋に連結リストとして実装するset ことはできず、それでもこれらの保証を満たします。したがって、C++ 標準ライブラリsetが連結リストとして実装されている場合、それは標準に違反しています。ifこれは、間違ったC++ コンパイラの実装と同じです。

于 2012-10-05T16:44:00.973 に答える
10

まず最初に、おそらくSTLではなくC++ 標準ライブラリを意味します。STL は、C++ が標準化される前に作成されたライブラリであり、C++ 標準ライブラリに大きな影響を与えました。

現在、C++ 標準は、実装が準拠すべき規則と定義を提供しています。特に、標準ライブラリは、さまざまな部分クラス定義と関数宣言、およびそれらが持つべきプロパティとして記述されています。実装は、標準の内容を正確に満たしている限り、選択した方法でライブラリを自由に実装できます。準拠する実装について標準が述べていることは次のとおりです (§1.4)。

クラスおよびクラス テンプレートの場合、ライブラリの Clauses は部分的な定義を指定します。プライベート メンバー (条項 11) は指定されていませんが、各実装は、ライブラリ条項の説明に従って定義を完了するためにそれらを提供する必要があります。

関数、関数テンプレート、オブジェクト、および値については、ライブラリ句が宣言を指定します。実装は、ライブラリ条項の記述と一致する定義を提供するものとします。

たとえば、std::list実装の複雑さが二重リンク リストの複雑さと等しくなるようにするには、そのメンバー関数に複雑さの要件が与えられます。たとえば、std::list::insert関数には次の要件が与えられます (§23.3.5.4、強調を追加)。

リストへの単一の要素の挿入には一定の時間がかかり、T のコンストラクターへの呼び出しは 1 回だけです。

これは必ずしも、二重リンク リストとして実装するstd::list 必要があるという意味ではありません。ただし、これは一般的な選択です。実装は、要件が満たされる (または、要件が満たされているように見える、as-if ルール) ようにのみ動作する必要があります。

于 2012-10-05T16:51:47.937 に答える
5

実際の標準の例は、明確にするのに役立つかもしれません。unordered_*これは、ハッシュ テーブルを標準に組み込むために特別に追加されたものであるため、良い例だと思います。この引用は草稿からのものですが、最終版はほぼ同様のものになると思います。

23.5.4.4 unordered_map修飾子

template <class P>
pair<iterator, bool> insert(P&& obj);
  1. 必須: value_type は から構築可能ですstd::forward<P>(obj)。
  2. 効果: コンテナ内に のキーと同等のキーを持つ要素がない場合にのみ、value_type に変換された obj を挿入しますvalue_type(obj)。
  3. 戻り値:bool返されたペア オブジェクトのコンポーネントは、挿入が行われたかどうかを示し、イテレータ コンポーネントは のキーと同等のキーを持つ要素を指しますvalue_type(obj)。
  4. 複雑さ: 平均ケース O(1)、最悪ケース O(size())。
  5. 備考: この署名は、 P が に暗黙的に変換可能でない限り、オーバーロードの解決に参加しないものとしvalue_typeます。

標準の他の部分では、ハッシュ テーブルとして実装することも効果的に要求されますが、重要な部分は、複雑な要件を作成することだと思います。

于 2012-10-05T16:54:02.700 に答える
3

短い答え: できません。作者はおそらく誤解しています。レッド ブラック ツリーは、ノード ベースのコンテナ (つまり、何らかの方法で相互にリンクされたノード) として実装されます。彼らのさまざまな操作。

長い答え: 実は、誤解があります。

C++ 標準には 2 つの (ある程度インターリーブされた) コンポーネントがあります。

  • C++ 言語自体
  • C++ 標準ライブラリ

コンパイラは、C++ 言語を実装するためにのみ必要です。実際、コンパイラと標準ライブラリの実装との間には、必ずしも 1 対 1 の一致があるとは限りません。

例:

  • Dinkumware は、C++ 標準ライブラリの独自の実装を提供する会社です。これは、Visual Studio C++ コンパイラと IDE にバンドルされている Microsoft に販売されています。
  • Clang は、ほとんどの Linux ディストリビューションで libstdc++ 実装を使用する C++ コンパイラであり、通常は gcc コンパイラにバンドルされています。LLVM プロジェクト (Clang をホスト) には独自の実装 (libc++ ライブラリ) がありますが、まだ多くの Linux ディストリビューションに移植されていません。

標準ライブラリの実装は、インターフェイス (どのクラス/メソッド、どのパラメーター、どの型など) の観点からだけでなく、複雑さの観点からも、多くの要件を満たす必要があります。ただし、実装は異なります。

例：std::string

  • libstdc++ (gcc に付属) ではstd::string、Copy-On-Write イディオムを実装しているため、クラスには共有クラスへのポインターが 1 つしか含まれていません。
  • 一方、Dirkumware 実装では、クラス内のスペースを再利用することによってstd::string( 経由で) メモリを動的に割り当てることなく、小さな文字列を格納することで構成される Small-String-Optimization を実装するため、クラスははるかに太くなります。new

どちらも同じインターフェースを実装していますが、大きく異なります。

例：std::sort

ソート アルゴリズムは、平均で N*log(N) 全体の複雑さだけが必要です。ただし、適切な実装では、IntroSort アルゴリズムまたは TimSort のバリエーションのいずれかを実装します。これらは、多くの一般的なケースで複雑さが低く、最悪の場合の複雑さが悲惨ではありません。

たとえば、libc++ の実装は、たとえば、私が引用した 3 つのライブラリの中で現在最も優れていると理解しています。

于 2012-10-05T18:46:32.017 に答える
1

(たとえば) セット コンテナーが赤黒木ではなく連結リストで実装されている場合、計算の複雑さ (時間と空間の両方) をどのように観察できますか?

シーワールド サン アントニオは、かつてアンハイザー ブッシュが所有していました。Anheuser-Busch がそれを買収したとき、テキサス州の奇妙な酒類法により、Anheuser-Busch は競合他社のビールのみをシーワールドで販売する必要があったでしょう。バッドを売るのは違法だったでしょう。したがって、それらの酒類法に対するブッシュの例外です。ブッシュの例外は、アンハイザー・ブッシュまたはシーワールドの名前を挙げませんでした。それは少し露骨すぎたでしょう。しかし、それにもかかわらず、シーワールドがバドを販売することを許可し、他のどこにも適用されませんでした. 立法者は、組織の名前を付けずに、非常に特定の組織を対象とする法律を作成することに非常に長けています。

同じことが標準作成者にも当てはまります。標準では、赤黒木はどこにもありませんが、要件は赤黒木を優先するように大幅に不正に設定されています。AVL ツリーでさえ、これらの厳しい挿入要件を満たすことができるとは思えません。AVL ツリーは、ルックアップをできるだけ高速にするために、挿入時にパフォーマンスを低下させます。検索に関しては、AVL ツリーは赤黒ツリーよりもさらに高速です。

于 2012-10-05T17:58:51.160 に答える