priority_queue调用范围构造函数时迭代器类型错误原因

测试代码 #

#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.

问题表现 #

• 调用priority_queue默认构造函数时可正常编译
• 传入首尾迭代器调用范围构造函数时，会抛出迭代器类型相关的编译错误，查阅/usr/include/c++/7/bits/下的STL实现源码也无法定位问题根源

问题由两个核心原因导致：

1. 传入的迭代器区间元素类型与优先级队列存储类型不匹配
   priority_queue的范围构造逻辑是把迭代器区间[first, last)内所有解引用后的元素存入底层容器，再调整成堆结构。你定义的优先级队列存储类型是myIt，也就是unordered_map<int,int>::iterator（迭代器本身），但传入的freq_cnt.begin()、freq_cnt.end()是unordered_map的元素迭代器，这个区间里的元素是解引用得到的pair<const int, int>键值对，根本不是迭代器类型，本身就不符合存储要求。
2. GCC 7 版本libstdc++实现缺陷
   GCC 7.4 自带的libstdc++对priority_queue范围构造的实现有bug：当传入迭代器的value_type和队列存储类型不匹配时，不会直接抛出明确的类型转换错误，反而会在内部堆构建的类型检查环节，错误比对传入迭代器和底层容器迭代器的类型，最终抛出完全不相关的迭代器类型错误，很容易误导问题定位。

另外你的比较器cmpHelper的operator()没有加const修饰，范围构造时会调用make_heap调整堆结构，const语境下调用非const成员函数也会报编译错误。默认构造时队列为空，不会触发堆调整逻辑，所以不会暴露这个问题。

根据实际需求二选一即可：

• 如果需要在优先级队列中存储unordered_map的键值对，直接修改队列存储类型和比较器就行：

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

using namespace std;

class cmpHelper {
public:
    // 注意加const修饰
    bool operator()(const pair<const int, int>& l, const pair<const int, int>& r) const {
        return l.second > r.second;
    }
};

int main() {
    unordered_map<int,int> freq_cnt({{3,1},{2,4},{5,2}});
    // 存储类型改为pair，直接传元素迭代器即可
    priority_queue<pair<const int, int>, vector<pair<const int, int>>, cmpHelper> h(freq_cnt.begin(), freq_cnt.end());
    return 0;
}

• 如果确实需要存储unordered_map的迭代器（比如避免大对象拷贝、需要修改原map元素），就先构造一个存迭代器的区间，再传给优先级队列，同时修好比较器的const问题：

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

using namespace std;

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

class cmpHelper {
public:
    // 加const修饰
    bool operator()(const myIt& l, const myIt& r) const {
        return l->second > r->second;
    }
};

int main() {
    unordered_map<int,int> freq_cnt({{3,1},{2,4},{5,2}});
    vector<myIt> it_vec;
    for(auto it = freq_cnt.begin(); it != freq_cnt.end(); ++it) {
        it_vec.push_back(it);
    }
    // 传入存迭代器的vector的迭代器
    priority_queue<myIt, vector<myIt>, cmpHelper> h(it_vec.begin(), it_vec.end());
    return 0;
}

内容的提问来源于stack exchange，提问作者Truman Lyng