cannot push_heap on list<int>, works on vector

Question

I am trying to push_heap on a list<int>, but compilation fails complaining about the list iterator. If I change the list to a vector it works fine.

Looking at cpp reference I cannot figure out why list iterators would behave differently. Maybe someone can shed some light?

https://ideone.com/pk5iJG

#include <algorithm>
#include <functional>
#include <list>

using namespace std;

int main() {

    list<int> l;
    l.push_back(0);
    push_heap(l.begin(), l.end(), greater<int>());
    return 0;
}

error:

In file included from /usr/include/c++/6/bits/stl_pair.h:59:0,
                 from /usr/include/c++/6/utility:70,
                 from /usr/include/c++/6/algorithm:60,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h: In instantiation of ‘void std::push_heap(_RAIter, _RAIter, _Compare) [with _RAIter = std::_List_iterator<int>; _Compare = std::greater<int>]’:
prog.cpp:13:48:   required from here
/usr/include/c++/6/bits/stl_heap.h:200:28: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘int’)
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
                            ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:333:5: note: candidate: template<class _Iterator> decltype ((__x.base() - __y.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator-(const reverse_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:333:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_pair.h:59:0,
                 from /usr/include/c++/6/utility:70,
                 from /usr/include/c++/6/algorithm:60,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:200:28: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::reverse_iterator<_Iterator>’
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
                            ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:387:5: note: candidate: template<class _IteratorL, class _IteratorR> decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator-(const reverse_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:387:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_pair.h:59:0,
                 from /usr/include/c++/6/utility:70,
                 from /usr/include/c++/6/algorithm:60,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:200:28: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::reverse_iterator<_Iterator>’
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
                            ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1186:5: note: candidate: template<class _IteratorL, class _IteratorR> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
     operator-(const move_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1186:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_pair.h:59:0,
                 from /usr/include/c++/6/utility:70,
                 from /usr/include/c++/6/algorithm:60,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:200:28: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::move_iterator<_IteratorL>’
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
                            ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1193:5: note: candidate: template<class _Iterator> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
     operator-(const move_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1193:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_pair.h:59:0,
                 from /usr/include/c++/6/utility:70,
                 from /usr/include/c++/6/algorithm:60,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:200:28: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::move_iterator<_IteratorL>’
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
                            ^
In file included from /usr/include/c++/6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/6/algorithm:62,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:201:55: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’)
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                                               ~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:333:5: note: candidate: template<class _Iterator> decltype ((__x.base() - __y.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator-(const reverse_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:333:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/6/algorithm:62,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:201:55: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::reverse_iterator<_Iterator>’
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                                               ~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:387:5: note: candidate: template<class _IteratorL, class _IteratorR> decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator-(const reverse_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:387:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/6/algorithm:62,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:201:55: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::reverse_iterator<_Iterator>’
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                                               ~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1186:5: note: candidate: template<class _IteratorL, class _IteratorR> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
     operator-(const move_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1186:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/6/algorithm:62,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:201:55: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::move_iterator<_IteratorL>’
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                                               ~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/algorithm:61,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1193:5: note: candidate: template<class _Iterator> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
     operator-(const move_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1193:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/6/algorithm:62,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_heap.h:201:55: note:   ‘std::_List_iterator<int>’ is not derived from ‘const std::move_iterator<_IteratorL>’
       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
                                               ~~~~~~~~^~~~~~~~~~

Answer 1

From ISO C++14 standard at §25.4.6:

A heap is a particular organization of elements in a range between two random access iterators [a,b).

So the function requires an iterator which satisfies RandomAccessIterator concept but std::list<T>::iterator doesn't.

Answer 2

Because push_heap() requires a random access iterator.

Different C++ containers provide different kinds of iterators, with different properties, and different capabilities. std::list provides only a bidirectional iterator, which does not meet the requirements for a random access iterator. As noted in the link I cited, a random access iterator implements additional requirements beyond the ones implemented by bidirectional iterators.

As such, algorithms that require random access iterators cannot use bidirectional iterators.

Answer 3

The parameters to push_heap are random-access iterators, and std::list iterators are not random-access, only bidirectional.

• http://en.cppreference.com/w/cpp/algorithm/push_heap

Type requirements

• RandomIt must meet the requirements of RandomAccessIterator.