0

このように定義されたマップがあります

std::map<int,int> myMap;

このマップを処理した後、(2 番目の値に基づいて) ヒープとして扱いたいと思います。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

マップ上に直接ヒープを作成することはできません。マップは既にキーでソートされており、別の部分ソートが必要です。すべてのマップ値をベクターにコピーして、そこからヒープを作成できます。

編集：

マップを変更してヒープを維持する必要がある場合は、インデックスの 1 つが実際にヒープを利用している場合に、マルチインデックス コンテナーのようなものを実装できます。

于 2014-03-18T12:19:52.647 に答える
0

@Andyに同意しました。マップは既にキーでソートされているため、直接ヒープを作成することはできません。同様の問題を解決するために、最初の要素としてマップ値、2 番目の要素としてキーを持つペアのベクトルを作成し、ヒープを作成しました。最大ヒープのコンパクター パラメーターは必要ありません。

例: マップ "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 に答える