为什么不在 C++ 容器中实现 contains 函数？

Question

我最初的问题是：为什么在 C++ 中 contains() 函数在 Containers 中缺失？

所以我寻找了一个解释，我发现了一些有趣的东西，为什么一些其他功能没有在所有 Containers 中实现（主要是因为性能问题和便利性）。

我知道您可以使用 algorithm 库中的 find 函数，或者您可以使用 Iterator 编写自己的函数，但我无法理解的是 为什么在set中，例如，实现了contains函数（它被称为find），而在vector或queue中没有实现.

我也很清楚为什么 Container 类不像 Collections 在 Java 中那样共享一个公共接口（感谢 this 的回答）但是在这个如果我找不到为什么不在所有容器类中实现 contains() 函数的原因（或者至少在 vector 之类的容器中）。

谢谢

Answer 1

std::set 实现自己的 find 的原因是 "generic" std::find 进行线性搜索，而 std::set 可以做得更好而不是通过在 O(log₂ n ).

中搜索其树表示另一方面，

std::vector 和 std::list 不能比线性时间更快地搜索，因此它们依赖于 std::find 实现。

请注意，您仍然可以将 std::find 应用到 std::set 以进行线性搜索；它只是不如使用 set 自己的 find 成员函数那么有效。

std::set<int> s {1, 2, 3, 4, 5, 6};
auto res = std::find(s.begin(), s.end(), 3);
std::cout << *res << std::endl; // prints 3

Answer 2

因为这是一个糟糕的设计模式。如果您在线性容器上重复使用 "find"，则说明您的代码存在问题。平均和最坏情况下的时间复杂度仍然是 O(n)，这意味着您做出了错误的选择。

例如，std::map 和 std::unordered_map 具有 find 允许 O(logn) 和 O(1) 查找的成员函数。这是因为容器通过这些方法使用高效的项目查找：这就是应该使用容器的方式。

如果您权衡了所有选项，并确定线性容器是您数据的最佳模型，但确实需要在极少数情况下查找元素，std::find() 可以让您做到这一点。你不应该依赖它。我将其视为 Python 和 Java 中的反模式，以及 C++ 中的优势。

作为个人笔记，3年前，当我还是一个初学者时，我写了很多if mydict in list: do_something()。我认为这是个好主意，因为 Python 使列表项成员资格成为惯用的。我不知道更好。这导致我编写了糟糕的代码，直到我了解到为什么线性搜索与二进制搜索和哈希图查找相比效率如此低下。编程语言或框架应该支持好的设计模式，并阻止坏的设计模式。启用线性搜索是一种糟糕的设计模式。

Answer 3

出于某种原因，其他答案侧重于广义和 per-container find 方法的复杂性。但是他们无法解释 OP 的问题。缺少有用的实用方法的真正原因是来自不同文件的类在 C++ 中的使用方式。如果每个不包含任何特殊属性的容器都有 contains 方法执行线性复杂度的通用搜索，我们将遇到每个容器 header 也包含 <algorithm> 或每个容器 header 重新实现了它自己的 find 算法（这更糟）。在预处理器包含（即 copy-pastes）每个包含的 header 之后，每个翻译单元编译期间构建的相当大的文档会变得更大。编译将花费更多时间。并且相当隐秘的编译错误消息可能会变得更长。当 non-member 函数可以完成工作（并且只包含您将要使用的东西）时，不创建成员函数的旧原则存在是有原因的。

请注意，最近有一项针对 uniform call syntax 的提案可能允许将 mix-in 实用方法转换为类。如果它上线，可能会像这样编写扩展函数：

template< typename TContainer, typename TItem > bool
contains(TContainer const & container, TItem const & item)
{
     // Some implementation possibly calling container member find
     // or ::std::find if container has none...
}

::std::vector< int > registry;
registry.contains(3); // false

Answer 4

容器不共享 "common (inherited) interface"（如 Java）是有充分理由的，这也是 C++ 泛型如此强大的原因。既然可以为所有容器编写一次代码，为什么还要为每个容器编写代码呢？这是 STL 建立的主要原则之一。

如果使用依赖于公共 inherited 接口的成员函数的容器，则必须为每个容器编写一个 find 函数。那是浪费和糟糕的工程。好的设计表明，如果你只能在一个地方编写代码，你应该这样做，因为你只需要从那个地方删除错误，并且在一个地方修复错误可以修复所有地方的错误。

所以 STL 背后的理念是 将算法从 容器 [=] 中分离出来 40=] 这样你只需编写一次算法并且它适用于所有容器。一旦 algorithm 被调试，它被调试为 all 容器。

美中不足的是，一些容器由于其内部结构可以做出更有效的决策。对于这些容器，添加了一个 type specific 函数，它将利用这种效率。

但是大多数函数应该与容器分开。它被称为解耦，它在促进代码重用的同时减少了错误，通常比 多态性 更重要，后者是库喜欢 Java 容器使用（一个通用的继承接口）。

为什么不在 C++ 容器中实现 contains 函数？

Why not implement contains function in c++ Containers?

c++

containers

contains