2

標準テンプレート ライブラリ (STL) は、データ構造とアルゴリズムを提供します。ただし、すべてのデータ構造ですべてのアルゴリズムを使用できるわけではありません。STL がアルゴリズム A とデータ構造 D の使用をサポートしているとします。

(a) A と D の間のリンクはどのように確立されますか。つまり、A はどのようにして D のコンポーネントにアクセスするのでしょうか? 例を上げてください。

(b) STL は、A を D で使用した結果について何かを保証 (約束) します。保証とは何ですか?

A) STL には、データ構造の要素にアクセスするためのさまざまな「反復子」も用意されています。イテレータにはさまざまなタイプがあり、最初から最後まで直線的に移動できるものもあれば、両方向に移動できるものもあれば、D 内の任意の要素に自由に移動できるものもあります。D でサポートされているイテレータのタイプによって、A のタイプが決まります。 D を使用して実行できます。

B) A が D で実行できる場合、STL は A を完了するのにかかる時間の複雑さ (O(n)) を保証します。

こんにちは！私は理論試験のために勉強しています。ここでの回答で何かを見逃したと皆さんが思っているのではないかと思っていました。

4

1 に答える 1

0

「(a) A と D の間のリンクはどのように確立されますか。つまり、A はどのように D のコンポーネントにアクセスしますか?例を挙げてください。」

これはイテレータを介して行われます。イテレータは、STL のアルゴリズムとデータ構造の間の接着剤です。私の例では c++11 を使用します。

std::vector<int> vec{1, 5, 3, 4};
std::list<int> l{1, 4, 8, 3};

auto foundInVecItem = std::find(vec.begin(), vec.end(), 3);
//Note: same algorithm used for different data structure.
auto foundInVecItem = std::find(l.begin(), l.end(), 3);

これが機能std::findするのは、検索に使用しているデータ構造について想定していないためです。ForwardIteratorこの概念を実装に使用します。ここでイテレータのカテゴリを確認できます。

std::find次のようなものを実装できます（学習用であるため単純化されています）：

template <class ForwardIterator>
ForwardIterator find(ForwardIterator b, ForwardIterator e,
                    typename ForwardIterator::value_type v) {
    while (b != e) {
      if (*b == v) {
        return b;
      }
    }
    return e;

}

ここで重要な点は、 iterator インターフェイスがstd::listorの要素にアクセスするために使用されているstd::vectorため、アルゴリズムが s を提供する限り、データ構造を気にしないことForwardIteratorです。

「(b) STL は、A を D で使用した結果について何かを保証します (つまり、約束します)。保証とは何ですか?」

すみません、これは一般的すぎます。その質問はどういう意味ですか? ビッグ O 表記、つまり漸近的な計算コストのことを言っているのであれば、そうです。標準では、データ構造が与えられると、アルゴリズムごとに制限付きの Big O コストが約束されます。アルゴリズムとデータ構造に依存します。たとえばstd::advance、イテレータをいくつかのステップだけ進める は、 s およびそれらの残りの部分であることが保証されてO(1)いRandomAccessIteratorますO(n)。

"A) STL には、データ構造の要素にアクセスするためのさまざまな "反復子" も用意されています。さまざまな種類の反復子があり、最初から最後まで直線的に移動できるものもあれば、両方向に移動できるものもあれば、自由に移動できるものもあります。 D の任意の要素。D がサポートする反復子の型によって、D を使用して実行できる A の型が決まります。"

ここでイテレータのカテゴリを確認できます。

「B) A を D で実行できる場合、STL は A を完了するのにかかる時間の複雑さ (O(n)) を保証します。」

はい、そうです。この仕様は、データ構造が与えられた操作の漸近的な計算コストを保証します。

于 2013-03-28T06:42:54.863 に答える