0

我有一张这样定义的地图

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 ......但我不确定。

我应该转到函数对象（从普通函数指针）吗？

有什么帮助吗？

4

2 回答 2

3

您不能直接在地图上创建堆。地图已按键排序，您需要不同的部分排序。您可以将所有地图值复制到一个向量并从中创建一个堆。

编辑：

如果您需要修改地图并维护堆，则可以在其中一个索引实际上由堆驱动时实现多索引容器之类的东西。

于 2014-03-18T12:19:52.647 回答
0

同意@Andy。地图已经按键排序，所以你不能直接在它上面堆。为了解决类似的问题，我创建了一个配对向量，其中映射值作为第一个元素，键作为第二个元素，然后创建堆。最大堆不需要任何压缩器参数。

例如：对于地图“map m”，使用下面的代码创建向量，然后创建堆。

for(it=m.begin(); it != m.end(); it++)
    v.push_back(make_pair(it->second,it->first));   

make_heap(v.begin(),v.end(),sort_v());

这将起作用，并且顶部元素将在任何时间点返回。

于 2016-04-27T20:34:23.780 回答