18

我想知道为什么 STL 不会重载它们的算法函数，这样我就可以通过简单地提供一个容器而不是采用更冗长的方式来传递 begin + end 迭代器来调用它们。我当然理解为什么我们还想使用迭代器对来处理容器/数组的子序列，但是，几乎所有对这些方法的调用都使用了整个容器：

std::for_each(myVector.begin(), myVector.end(), doSomething);

我会发现只写更方便，可读性和可维护性

std::for_each(myVector, doSomething);

STL 不提供这些重载是否有原因？[编辑：我不是要用这个受限制的接口替换接口，而是要提供一个基于容器的 iterface！] 他们会引入歧义吗？我正在考虑这样的事情：

template<typename _Container, typename _Funct>
inline _Funct for_each(_Container c, _Funct f) {
    return for_each(begin(c), end(c), f);
}

我错过了什么吗？

4

7 回答 7

18

它们确实为许多算法引入了歧义。很多<algorithm>样子

template<class iterator>
void do_something(iterator, iterator);

template<class iterator, class funct>
void do_something(iterator, iterator, funct);

如果添加额外的重载

template<class container, class funct>
void do_something(container, funct);

编译器将很难弄清楚是什么do_something(x, y)意思。如果x和y相同type，它将同时匹配iterator = type和container = type, funct = type。*)

C++11 试图用能够识别容器和迭代器之间区别的“概念”来解决这个问题。然而，事实证明这些“概念”过于复杂，无法将其纳入标准，因此这些重载也没有。

*) 编译器在这里不同意，Comeau 编译器声称它是模棱两可的，g++ 4.5 和 MSVC 10 调用第一个函数。

在评论中进行了非常长时间的讨论之后，这是一个无法按预期工作的示例 - 使用也可以兼作谓词的容器适配器。

#include <iostream>
#include <vector>

template<class iterator>
void test(iterator, iterator)
{
   std::cout << "test iterator\n";
}

template<class iterator, class predicate>
void test(iterator, iterator, predicate)
{
   std::cout << "test iterator, predicate\n";
}

template<class container, class predicate>
void test(const container& cont, predicate compare)
{
   std::cout << "test container, predicate\n";

   test(cont.begin(), cont.end(), compare);
}

template<class container>
class adapter
{
public:
   typedef typename container::iterator   iterator;

   adapter(container* cont) : cont(cont)
   { }

   iterator begin() const
   { return cont->begin(); }

   iterator end() const
   { return cont->end(); }

   bool operator()(const iterator& one, const iterator& two)
   { return *one < *two; }

private:
   container* cont;
};

int main()
{
   std::vector<int>   v;

   adapter<std::vector<int>>   a(&v);

   test(a, a);

}

输出：

测试迭代器

http://ideone.com/wps2tZ

于 2012-12-22T15:18:57.780 回答
10

不幸的是，这是一个更普遍的问题。也就是说，迭代器旨在击败那些蹩脚的 C API 和 Java 风格的“将算法作为每个单独容器的方法”的解决方案。它们是第一代通用解决方案，毫无疑问，经过反思，它们不如我们花了 20 年思考后获得的其他可能的通用解决方案好。

添加这些容器重载只是解决问题空间的一小部分。它甚至可能在未来让事情变得更糟。解决方案是范围，C++ 正在寻求尽快引入范围。

于 2012-12-22T14:37:08.613 回答
3

要理解这一点，我认为必须了解 C++ 算法的哲学。我们先问这个问题：

为什么 C++ 算法被实现为自由函数而不是成员函数？

那么答案非常简单：避免实现爆炸。假设你有M容器和N算法，如果你将它们实现为容器的成员，那么就会有M*N实现。这种方法有两个（相关的）问题：

  • 首先，它没有利用代码重用。大多数实现将被重复。
  • 其次，实施爆炸，这是上述情况的直接后果。

C++ 通过将它们实现为自由函数来解决这些问题，因此您只有N实现。在容器上运行的每个算法都采用一对定义范围的迭代器。如果您想要采用容器的重载，而不是一对迭代器，那么标准必须为每个算法提供这样的重载，并且会有一些2*N实现几乎违背了 C++ 将算法与容器分离的目的首先，这些功能中有一半没有做另一半做不到的事情。

所以我认为这不是什么大问题。只是为了避免一个单一的参数，为什么要实现N更多的功能（这也对其使用施加了一些限制，例如您不能将指针传递给它）？但是，如果程序员想要在他们的实用程序中使用这样的函数，他们可以随时与基于标准算法的许多其他函数一起实现它们！

你评论说：

好吧，2*N 实现实际上只有 N 个实现。其他 N 个是内联重载，它们直接调用算法的“真实”版本，因此它们只是标题。提供容器重载并不会破坏将算法与容器分离的目的，因为（如您在我的示例中所见）它们可以使用模板来处理所有类型的容器。

基于这种逻辑，人们可以很好地争论M*N算法。那么也让它们成为成员函数（并在内部调用自由函数）？我相信很多 OOP 人会更喜欢

auto result = container.accumulate(val);

超过

auto result = std::accumulate(container.begin(), container.end(), val);
于 2012-12-22T14:45:57.663 回答
3

这是 Herb Sutter 博客中的相关答案：为什么没有基于容器的算法。它显示了反例，就像 Bo Persson 在上面的回答中所做的那样。

于 2014-10-01T03:41:20.197 回答
2

有一个Range Operators 库旨在解决这个问题。详细程度被削减了好几次。

您的示例将如下所示：

auto newVector = myVector * doSomething;

是的，doSomething- 没有括号。

来自 shell 的熟悉习语（使用 std 算法）：

auto t = vector<int>{3,2,1,4} | sort | unique;
于 2012-12-22T14:49:24.817 回答
0

应该指出的是，定义自己的琐碎包装器以添加容器化版本非常容易。

例如：

template<typename Container, typename Func>
Func for_each(Container& c, Func f) {
    return std::for_each(c.begin(), c.end(), f);
}

现在您可以拨打您想要的简单电话。没有歧义，因为您的包装器不在 std 命名空间中。您可以定义采用 const Container& 的重载。如果您想要调用 C++-11 const 迭代器方法的版本（例如 cbegin()），我认为您需要以不同的方式命名包装器。我使用 for_each_const。

于 2015-03-15T01:46:32.223 回答
0

显然，正如其他用户所提到的，这是一个棘手的问题，所以很遗憾已经很久了，标准库中仍然没有解决方案。但是，已经有可用的范围库，例如 Boost::Range 和 Adob​​e Source Libraries 中的一个，它们不仅提供了您在问题中描述的界面的简单性，而且还提供了一些更高级的功能。

您的示例与 Boost 完美配合（我们在using namespace boost::range::adaptors下面）：

boost::for_each(myVector, doSomething);

我们还可以myVector快速轻松地切片：

boost::for_each(myVector | sliced(10, 20), doSomething)

我们甚至可以myVector与另一个压缩，按谓词过滤，并在一个简单的语句中对结果对的每个其他元素进行采样（这需要您在 doSomethingElse 中解压缩由 生成的元组boost::combined）：

boost::for_each( boost::combined(myVector, myOtherVector) | strided(2), doSomethingElse)

于 2017-05-22T19:31:20.967 回答