算法如何在STL中访问数据结构的组件

Question

标准模板库(STL)提供数据结构和算法。然而，并不是每一种算法都适用于每一种数据结构。假设STL支持使用数据结构D的算法A。

(a)如何建立A和D之间的联系。换句话说，A是如何访问D的组件的？举个例子。

(b) STL保证(即承诺)关于A与D的使用结果的某些内容。

( A) STL还提供各种“迭代器”来访问数据结构上的元素。有各种类型的迭代器，它们可以从一开始到最后线性地行进，有些可以向两个方向移动，还有一些可以自由地移动到D中的任何元素。

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

你好!我正在为一次理论考试学习。我想知道你们是否认为我在回答中遗漏了什么。

Answer 1

"(a) A和D之间的联系是如何建立的。换句话说，D的A存取组件是如何建立的?举例子。

它是通过迭代器完成的。迭代器是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::list或std::vector的元素，因此算法不关心数据结构，只要它们提供ForwardIterator。

"(b) STL保证(即承诺)关于使用A和D的结果的某些内容。保证是什么？

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

"A) STL还提供各种“迭代器”来访问数据结构上的元素。有各种类型的迭代器，它们可以从一开始到最后线性地行进，有些可以向两个方向移动，还有一些可以自由地移动到D中的任何元素。D支持的迭代器类型将决定使用D运行的A的类型。

您可以查看迭代器类别这里。

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

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