CODEWITHSUNDEEP
c++heapcontainers
Fuad
Fuad

Reputation: 1509

Making a heap with list causes errors

The following code:

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

Live demo

causes a whole bunch of errors, including:

error: no match for 'operator-'

When I declare list as std::vector, I do not get these errors, why?

Upvotes: 2

Views: 390

Answers (1)

Shoe
Shoe

Reputation: 76260

The two iterators passed as first and second arguments to the function std::make_heap has to be RandomAccessIterators. List iterators are not RandomAccessIterators while std::vector and std::array's are.

In the standard this is specified in the interface for make_heap at §25.1:

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

and in §25.1.5.5 we have that:

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

And finally, random access iterators are described in §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.

table for the requirements of random access iterators

Upvotes: 3

Related Questions