C++排序算法的容器版本

Question

我正在阅读 Stroustrup 的关于 C++ 的博客 (http://isocpp.org/blog/2014/12/myths-3)，期间发现了一段有趣的代码：

void do_my_sort(vector<double>& v)
{
  sort(v,[](double x, double y) { return x>y; });  // sort v in decreasing order
}

int main()
{
  vector<double> vd;
  // ... fill vd ...
  do_my_sort(v);
  // ...
} 

请注意，sort没有使用传统的sort(v.begin(), v.end(), ...)，Stroustrup解释道：

我使用了一个容器版本的sort()来避免明确定义迭代器。

然而，我在我的C++11编译器上尝试了相同的代码，但它无法编译。 我还在ideone上尝试了相同的代码，使用了C++14编译器，但它也无法编译，提示没有匹配的调用sort。

为什么会这样呢？

此外，Stroustrup接下来提到：

我可以进一步使用C++14比较对象：

sort(v,greater<>()); // 以递减顺序排序v

我在C++11中也像sort一样使用了类似于great<>()的比较器。为什么他说这是C++14比较对象？

- 1110101001

---

要使用std::sort，您可能需要#include <algorithm>。 - erenon

@erenon 我知道并且我已经做了那个。它仍然显示没有匹配的调用来排序。 - 1110101001

标准库中没有 sort 的容器版本，但希望很快会有：https://ericniebler.github.io/std/wg21/D4128.html - BenPope

Answer 1

他自己写的，不是标准的。因此你在标准库中找不到它。你可以这样实现它：

template <class Container, class Comp>
void sort (Container& cont, Comp comp) {
    using std::begin;
    using std::end;
    std::sort(begin(cont), end(cont), comp);
}

正如Clukester所指出的那样，还有boost::sort提供了这个功能。

- Baum mit Augen

---

哦，好的。我以为它是语言标准的一部分或者是最近引入的功能。如果他提到这是一个自定义函数就好了。 - 1110101001

为什么不在Comp模板中添加一个默认参数？class Comp = less<>？ - Mark

@Mark 没有理由不这样做，只是我觉得这与上面的问题无关。我喜欢保持简短和简单。 - Baum mit Augen

完全作弊 :) Stroustrup 不好！ - nbubis

Answer 2

我曾经在C ++11中使用像great<>()这样的比较器进行排序。为什么他说这是一个C ++14比较对象？

C++14比较函数对象有额外的能力，可以为其operator()方法和推断返回类型提供转发引用。 Function Objects集合的模板参数已更改为具有类型void的默认参数，并且使用该类型的特化。

template< class T = void >
struct greater
{
    constexpr bool operator()(const T &lhs, const T &rhs) const;
};

template<>
struct greater<void>
{
    template< class T, class U>
    constexpr auto operator()( T&& lhs, U&& rhs ) const
      -> decltype(std::forward<T>(lhs) > std::forward<U>(rhs));
};

- David G

Answer 3

Bjarne在博客中解释了这个sort()是什么。

I used a container version of sort() to avoid being explicit about the iterators. That is, to avoid having to write:

std::sort(v.begin(), v.end(), [](double x, double y) { return x > y; });

现在，C++20提供了std::ranges::sort，它也可以做到这一点：

std::vector<double> vd{ /* ... */ };

std::ranges::sort(vd);
// equivalent to ...
std::ranges::sort(vd.begin(), vd.end());

请注意，此解决方案适用于所有范围，例如std::array、std::span、std::vector等。

在C++14中模拟它的一种方法是：

// std::less<void> can be implemented in C++11 too
template <class Container, class Comp = std::less<void>>
void sort(Container&& cont, Comp comp = {}) {
    using std::begin;
    using std::end;
    std::sort(begin(cont), end(cont), std::move(comp));
}

注意：这与@BaummitAugen的解决方案非常相似，但它采用了转发引用，以允许对未作为左值传递的容器进行排序。

注意：如果Container是一个数组，使用cont.begin()和cont.end()调用std::sort将无法工作。

- Jan Schultke

Answer 4

也许他正在使用Boost的排序算法，而不是像人们预期的那样使用标准的排序算法。因此，应该使用boost::sort而不是std::sort。

- Clukester