c++ - std::map 上的 make_heap 具有用户定义的比较和随机访问迭代器

Question

我有一个这样定义的 map

std::map<int,int> myMap;

处理完这个映射后，我想把它当作一个堆(基于第二个值)。我决定使用 std::make_heap 函数……定义如下……

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

因为这个函数需要定义一个比较函数...我是这样做的

bool compare(const std::pair<int,int> &frst, const std::pair<int,int> &scnd)

现在有了这个设置，我就这样调用 make_heap

std::make_heap(myMap.begin(), myMap.end(),compare);

但这给了我编译错误...

/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_heap.h: In function ‘void std::make_heap(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = std::_Rb_tree_iterator<std::pair<const int, int> >]’:
maxRepeatingNumber.cc:48:   instantiated from here /usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_heap.h:357: error: no match for ‘operator-’ in ‘__last - __first’
/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include e/c++/4.1.2/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/ c++/4.1.2/bits/stl_heap.h:360: error: no match for ‘operator-’ in ‘__last - __first’
/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_heap.h:364: error: no match for ‘operator+’ in ‘__first + __parent’
/usr/lib/gcc/i386-redhat-linux/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)

编译错误提示我它们可能是因为 make_heap 需要 random_access_iterator... 但我对此不确定。

我应该转向函数对象(从普通函数指针)吗？

有什么帮助吗？

Answer 1

您不能直接在 map 上制作堆。 map 已经按键排序，您需要不同的部分排序。您可以将所有映射值复制到一个 vector 并从中创建一个堆。

编辑:

如果您需要修改您的映射并维护堆，您可以在其中一个索引实际上是堆驱动的情况下实现诸如多索引容器之类的东西。