c++ 编译错误 "required from ' _InputIterator std::__find_if(_InputIterator, _InputIterator, _Predicate, std::input_iterator_tag) "

Question

我正在尝试挑战 leetcode 上的第 210 题，但我遇到了一个编译错误，我无法找出我的代码有什么问题。

错误是这样的

required from '_InputIterator std::__find_if(_InputIterator, _InputIterator, _Predicate, std::input_iterator_tag) 
[with _InputIterator = std::_Rb_tree_iterator<std::pair<const int, bool> >; 
_Predicate = __gnu_cxx::__ops::_Iter_equals_val<const int>]'

我把它复制到IDE里，试运行了，还是找不到问题，因为IDE没有显示是哪一行导致了编译错误。

问题需要找出一个人应该采取的类(class)顺序来完成所有类(class)，给定存储在 c++ 成对 vector 中的类(class)先决条件。

为了解决这个问题，我首先尝试将pair的 vector 转换为一个 vector >记录从一个点(course)到另一个节点(course)的边，并记录一个节点是否是另一个节点的儿子因此它不是树的根。我试着先找出图中是否有环。然后我使用 BFS 来搜索图并返回节点的访问顺序。

vis map用于记录在查找图中的环时是否访问过某个节点。 globalVis map用于记录之前其他节点发起的搜索是否访问过某个节点，因此不需要再次作为起始节点进行搜索。

请告诉我是哪一行代码导致了编译错误，以及如何纠正，谢谢。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        edges = vector<vector<int>>(numCourses,vector<int>());
        for(int i=0;i<prerequisites.size();i++){
            edges[prerequisites[i].first].push_back(prerequisites[i].second);
            isRoot[prerequisites[i].second]=false;
        }           
        for(int i=0;i<numCourses;i++){
            if(find(globalVis.begin(),globalVis.end(),i)==globalVis.end()){
                globalVis[i]=true;
                vis.clear();
                vis[i]=true;
                if(!checkStartNode(i))
                    return res;
            }
        }
        for(int i=0;i<numCourses;i++){
            if(find(isRoot.begin(),isRoot.end(),i)==isRoot.end()){
                toVisit.push(i);
            }
        }
        vis.clear();
        BFS(res);
        return res;
    }

    void BFS(vector<int>& res){
        while(toVisit.size()>0){
            int node = toVisit.top();
            vis[node]=true;
            toVisit.pop();
            res.push_back(node);
            for(int i=0;i<edges[node].size();i++){
                int nextNode = edges[node][i];
                if(find(vis.begin(),vis.end(),nextNode)==vis.end())
                    toVisit.push(nextNode);                
            }
        }
    }

    bool checkStartNode(int node){
        for(int i=0;i<edges[node].size();i++){
            int nextNode = edges[node][i];                               
            if(find(vis.begin(),vis.end(),nextNode)!=vis.end()){
                globalVis[nextNode]=true;
                if(vis[nextNode]==true)
                    return false;
                else{
                    vis[nextNode]=true;
                    if(!checkStartNode(nextNode))
                        return false;
                    vis[nextNode]=false;
                }
            }                
            else{
                vis[nextNode]=true;
                if(!checkStartNode(nextNode))
                    return false;
                vis[nextNode]=false;
            }
        }

    }

    stack<int> toVisit;
    vector<vector<int>> edges;
    map<int,bool> isRoot;
    map<int,bool> vis;
    map<int,bool> globalVis;
};

Answer 1

使用 std::map::find()而不是 std::find() .该映射具有键和值对作为值，您不能直接按您的值进行搜索。如果提供的话，最好使用容器类的成员函数而不是常用算法。

将所有出现的 find(map.begin(), map.end() value) 替换为:

if (find(globalVis.begin(), globalVis.end(), i) == globalVis.end()) {
    ...

与:

if (globalVis.find(i) == globalVis.end()) {
    ...

Demo

std::find() 可用于查找 (key,value) 对的精确匹配，例如:

if(find(vis.begin(), vis.end(), pair<const int, bool>(nextNode, true))!=vis.end()){
    ...

但是在您的代码中，您只是测试一个key 是否已经在 map 中并且您只需要通过key 进行搜索。