c++ - 为什么 std::map 没有 find/lower_bound 重载，std::list 没有 sort 重载？

Question

我知道你不应该使用 std::find(some_map.begin(), some_map.end()) 或 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)，而不是在)。为什么 C++ 标准不为 map 和集合提供 lower_bound 和 find 的专门版本？有什么深层原因吗？

Answer 1

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

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

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