5

我知道你永远不应该使用std::find(some_map.begin(), some_map.end())or std::lower_bound，因为它会花费线性时间而不是some_map.lower_bound. 类似的事情发生在std::list: 有std::list::sort排序功能，但你无法调用std::sort(some_list.begin(), some_list.end())，因为迭代器不是随机访问的。

但是，std::swap例如，标准容器具有重载，因此调用swap(some_map, other_map)需要 O(1)，而不是 O(n)。为什么 C++ 标准没有为我们提供地图和集合的专用版本lower_bound和？find有深层次的原因吗？

4

4 回答 4

5

我不认为有任何深刻的原因，但它比任何东西都更具哲学意义。标准算法的自由函数形式，包括您提到的那些，采用迭代器对来指示它们将遍历的范围。算法无法从这些迭代器中确定底层容器的类型。

提供特化或重载将背离此模型，因为您必须将容器本身传递给算法。

swap是不同的，因为它将所涉及的类型的实例作为参数，而不仅仅是迭代器。

于 2014-03-07T20:07:32.110 回答
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 容器/算法交互旨在通过不同的迭代器概念，使这两个部分保持独立，这样您就可以定义新的容器类型而不必为所有算法重载，这样您就可以定义新算法，而不必为所有容器重载。

除了这些设计选择之外，还有一个很好的技术原因，为什么这些算法（排序、下限等）不能为特殊容器（如listor map/ ）重载set。原因是迭代器通常没有理由显式连接到它们的父容器。换句话说，您可以从列表容器中获取列表迭代器（开始/结束），但不能从列表迭代器中获取（引用）列表容器。map / set 迭代器也是如此。迭代器可以被实现为对其父容器“盲目”。例如，像这样的容器list通常包含指向头和尾节点的指针以及分配器对象作为数据成员，但迭代器本身（通常只是指向节点的指针）不需要知道头/尾或分配器，它们只是有走上一个/下一个链接指针在列表中来回移动。因此，如果您要实现std::sortfor 的重载list容器，将无法从传递给排序函数的迭代器中检索列表容器。而且，在您提到的所有情况下，适用于这些特殊容器的算法版本是“集中的”，因为它们需要在容器级别运行，而不是在“盲”迭代器级别运行。这就是为什么它们作为成员函数有意义，这就是为什么你不能从迭代器中得到它们。

但是，如果您需要一种通用的方式来调用这些算法而不管您拥有的容器是什么，那么您可以根据需要在容器级别提供重载的函数模板。就这么简单：

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

这些函数应该根据迭代器对工作的简单事实将产生相当大的开销，即使专门用于映射/集迭代器。

请记住：

  • 可以使用任何一对迭代器调用此类函数，而不仅仅是开始/结束。

  • map/sets 的迭代器通常实现为指向叶节点的指针，而成员find/的起始节点lower_bound是树的根节点。

有一个成员 find 和 lower_bound 更好，因为指向根节点的指针直接存储为 map/set 对象的成员。

假设的非成员find必须遍历树以找到两个输入节点之间的最低共同祖先，然后执行 dfs - 同时仍然小心仅在 [first,last) 范围内搜索 - 这明显更昂贵.

是的，您可以跟踪迭代器内的根节点，然后优化是否使用开始/结束对调用函数......只是为了避免成员函数？

于 2014-03-07T21:17:19.603 回答