c++ - 不能在 list<int> 上进行 push_heap，适用于 vector

Question

我正在尝试 push_heap在 list<int> 上，但编译失败提示列表迭代器。如果我将列表更改为 vector ，它就可以正常工作。

查看 cpp 引用资料，我无法弄清楚为什么列表迭代器会有不同的行为。也许有人可以阐明一些想法？

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;
}

错误:

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

push_heap 的参数是随机访问迭代器，std::list 迭代器不是随机访问的，只是双向的。

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

Type requirements

• RandomIt must meet the requirements of RandomAccessIterator.