时间戳

首页 > 解决方案 > 对于 `std::less_equal` 和 `std::greater_equal` 谓词，`std::nth_element` 失败

c++ - 对于 `std::less_equal` 和 `std::greater_equal` 谓词，`std::nth_element` 失败

问题描述

与自定义谓词或一起使用时，我刚刚从 GCC 9.1 和 clang 8.0得到分段错误：std::nth_elementstd::less_equalstd::greater_equal

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
  std::vector<int> vals{1, 2, 5, 1, 3, 2, 1};

  std::nth_element(begin(vals), begin(vals)+2, end(vals), std::greater_equal{});

  copy(cbegin(vals), cend(vals), std::ostream_iterator<int>(std::cout, "\n"));
}

相反，使用std::lessor时一切都按预期工作std::greater。

我相信我理解其背后的原因：作为一种优化，在假设谓词返回相等元素的情况下，内部使用了无保护循环（没有边界检查）。false我很惊讶我在文档中找不到该要求。

这是我在N4659中找到的内容：

// [...]

template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);

// [...]
  1. 要求： RandomAccessIterator应满足 ValueSwappable（20.5.3.2）的要求。类型*first应满足MoveConstructible（表 23）和MoveAssignable （表 25）的要求。
  2. 效果：在nth_element指向的位置的nth元素之后是如果整个范围都被排序的话将在该位置的元素，除非nth == last. 同样对于i范围内的[first, nth)每个迭代器和范围内的每个迭代器j，[nth, last)它都持有：!(*j < *i)or comp(*j, *i) == false.
  3. 复杂性： [...]。

从上面，我不能推断出谓词必须返回false相等元素的要求。

这是来自cppreference.comstd::nth_element的引述：

// [...]

template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );                   // (until C++20)

// [...]

[...]

comp - 比较函数对象（即满足Compare要求的对象），如果第一个参数小于（即排序在）第二个参数，则返回 <code>true。[...]

虽然less和before这两个词用斜体显示，但我觉得可以有更明确的提示。

以下是我的问题：

  1. 我是否正确，谓词必须返回false相等的元素？
  2. 我是否遗漏了标准中明确记录此要求的一些重要声明？
  3. 根据上面的答案：这个问题有什么可做的（阅读标准的更多部分、缺陷报告、错误报告或改进 cppreference.com 文档）？

标签： c++language-lawyerc++17std

解决方案

推荐阅读