2

标准模板库 (STL) 提供数据结构和算法。但是，并非每种算法都可以与每种数据结构一起使用。假设 STL 支持使用具有数据结构 D 的算法 A。

(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;

}

这里重要的一点是迭代器接口被用来访问std::listorstd::vector所以算法并不关心数据结构，只要它们提供ForwardIterators。

“(b) STL 保证（即承诺）关于将 A 与 D 一起使用的结果。保证是什么？”

对不起，这太笼统了，你问这个问题是什么意思？如果您指的是大 O 表示法，即渐近计算成本，是的。该标准承诺给定数据结构的每个算法的有界大 O 成本。这取决于算法和数据结构。例如std::advance，将迭代器推进多个步骤，保证O(1)为RandomAccessIterators 和O(n)其余步骤。

"A) STL 还提供了各种“迭代器”来访问数据结构上的元素。迭代器有多种类型，它们可以从头到尾线性移动，有的可以双向移动，有的可以自由移动到D 中的任何元素。D 支持的迭代器类型将决定可以使用 D 运行的 A 的类型。”

您可以在此处查看迭代器类别。

“B）如果 A 可以在 D 上运行，则 STL 保证完成 A 所需的时间复杂度 (O(n))。”

是的，这是正确的。该规范保证给定数据结构的操作的渐近计算成本。

于 2013-03-28T06:42:54.863 回答