用列表创建堆会导致错误

Making a heap with list causes errors

以下代码:

std::list<int> list;
std::make_heap(list.begin(), list.end());

Live demo

导致一大堆错误,包括:

error: no match for 'operator-'

当我将 list 声明为 std::vector 时,我没有收到这些错误,为什么?

作为第一个和第二个参数传递给函数 std::make_heap 的两个迭代器必须是 RandomAccessIterator。列表迭代器不是 RandomAccessIterator,而 std::vectorstd::array 是。

在标准中,这是在 §25.1 的 make_heap 接口中指定的:

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

在 §25.1.5.5 中我们有:

If an algorithm’s template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall satisfy the requirements of a random-access iterator

最后,在 §24.2.7 中描述了随机访问迭代器:

A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, the following expressions are valid as shown in Table 111.