为什么range构造函数的iTerator类型Priority_queue是错误的？

Question

代码如下。

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

并在此显示相应的编译器信息

 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.

默认构造函数是可以的。我试图通过目录 /usr/includs/c ++/7/bits/ 浏览代码，但仍然没有任何想法。请帮助指出问题是什么。谢谢。

Answer 1

[freq_cnt.begin（），freq_cnt.end（））是std :: pair＆lt＆const＆const＆int，int＆gt; lvalues的范围，int＆gt; :: iterator 值。

您可以使用C ++ 20的 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());

否则，您可以默认构造队列并推动每个元素：

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

但请考虑具有参考的队列：

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

Answer 2

这是因为将迭代器 dereferences的构造函数迭代器填充容器。

而是将实际的迭代器放入容器中：

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

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

您要做的事情与此相似：

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

for(auto it = freq_cnt.begin(); it != freq_cnt.end(); ++it) {
    h.push(*it);  // <- NOTE: dereferencing the iterator
}

进一步澄清。检查这个简化的示例：

#include <iostream>
#include <vector>

int main() {
    using myIt = std::vector<int>::iterator;

    std::vector<int> ints{1, 2, 3};

    myIt beg = ints.begin(); // beg is a `myIt` and *beg is an `int&`
    myIt end = ints.end();

    //std::vector<myIt> iterators(beg, end); // NOK: *beg is NOT a `myIt`, but an `int&`
    std::vector<int> ints_copy(beg, end);    // OK: *beg is an `int&`
}

您使用迭代器通过 dereferencing （*beg上面）填充容器。当使用迭代器时，您将获得IT 点的值。因此，当您将类型std :: vector＆lt; int＆gt; :: Iterator的迭代器放置时，您将获得对int的引用。

---

如果将迭代器包裹在迭代器中，则当重新推荐返回原始迭代器时，可以使用这些迭代器构建PRIRESITION_QUEUE。

示例：

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

然后

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())
);