Why iterator type of priority_queue is wrong with range constructor?-CodePudding

The code is as following.

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

typedef unordered_map<int,int>::iterator myIt;

class cmpHelper {
    public:
    bool operator()(myIt l, myIt r){return l->second > r->second;}
};

int main(int argc, char* argv[]){
    unordered_map<int,int> freq_cnt({{3,1},{2,4},{5,2}});

    priority_queue<myIt,vector<myIt>, cmpHelper> h(freq_cnt.begin(), freq_cnt.end());
    //priority_queue<myIt, vector<myIt>, cmpHelper> h;
}

and hereunder shows corresponding compiler info

 g   --version
g   (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Default constructor is OK. And I tried to go through code under directory /usr/include/c /7/bits/, but still no any idea. Please help point out what the problem is. Thanks.

CodePudding user response：

[freq_cnt.begin(), freq_cnt.end()) is a range of std::pair<const int, int> lvalues, not unordered_map<int,int>::iterator values.

You can create a range of these iterators with C 20's std::ranges::iota_view:

auto its = std::ranges::iota_view{ freq_cnt.begin(), freq_cnt.end() };
priority_queue<myIt,vector<myIt>, cmpHelper> h(its.begin(), its.end());

Otherwise, you can default construct the queue and push each element:

priority_queue<myIt,vector<myIt>, cmpHelper> h;
for (auto it = freq_cnt.begin(); it != freq_cnt.end();   it) {
    h.push_back(it);
}

But consider instead having a queue of references:

using myValue = typename unordered_map<int,int>::value_type;
using myRef = std::reference_wrapper<myValue>;

class cmpHelper {
    public:
    bool operator()(const myValue& l, const myValue& r){return l.second > r.second;}
};

int main(int argc, char* argv[]){
    unordered_map<int,int> freq_cnt({{3,1},{2,4},{5,2}});

    priority_queue<myRef,vector<myRef>, cmpHelper> h(freq_cnt.begin(), freq_cnt.end());
}

CodePudding user response：

It's because the constructor that takes iterators dereferences the iterators to populate the container.

Put the actual iterators in the container instead:

std::priority_queue<myIt, vector<myIt>, cmpHelper> h;

for(auto it = freq_cnt.begin(); it != freq_cnt.end();   it) {
    h.push(it);
}

If you wrap your iterators in iterators that when dereferenced return the original iterators, you can construct the priority_queue using those.

Example:

template<class It>
struct iterator_iterator {
    using value_type = It;
    using difference_type = std::ptrdiff_t;
    using pointer = void;
    using reference = value_type&;
    using iterator_category = std::forward_iterator_tag;

    iterator_iterator(It it) : curr(it) {}

    iterator_iterator& operator  () {   curr; return *this; }
    iterator_iterator operator  (int) {
        iterator_iterator retval(*this);
          curr;
        return retval; 
    }
    
    bool operator==(const iterator_iterator& rhs) const {
        return curr == rhs.curr;
    }

    bool operator!=(const iterator_iterator& rhs) const {
        return curr != rhs.curr;
    }

    // this is used by the priority_queue's contructor:
    It operator*() { return curr; }

private:
    It curr;
};

then

unordered_map<int, int> freq_cnt({{3, 1}, {2, 4}, {5, 2}});

std::priority_queue<myIt, vector<myIt>, cmpHelper> h(
    iterator_iterator(freq_cnt.begin()),
    iterator_iterator(freq_cnt.end())
);