candidate function not viable: 1st argument ('const Node *') would lose const qualifier

Question

I am writing a DiGraph (directed graph) class with the c++ built in unordered_map<Node*, unordered_set<Edge>> data structure, where Node and Edge are two structs I defined myself. And in the class I wrote a containsNode() method to search if a Node is in the graph. This is the containsNode() method body:

bool DiGraph::containsNode(const Node * n) const {
    auto::const_iterator it = digraph.find(n);
    return (it == digraph.end());
}

digraph is the private member of DiGraph of type unordered_map<Node*, unordered_set<Edge>>.

However, the compiler generates the following error:

error: no matching member function for call to 'find'
auto::const_iterator it = digraph.find(n);
candidate function not viable: 1st argument ('const Node *') would lose const qualifier
const_iterator find(const key_type& __k) const {return __t...

However, if I declare the method as bool DiGraph::containsNode(Node* n) const {...} (the only difference being that the const keyword removed from the argument list) then there is no compilation error.

I checked the C++ documentation and saw that the find() method declaration in the unordered_map container has the const keyword:

std::unordered_map::find
    const_iterator find(const Key& key) const;

Therefore I think there shouldn't be a compilation error, so why do I get one?

Araldo

Answer 1

find() looks like this: find(const T& key) If T is Node*, then Node* must be const. But note, the pointer must be const, NOT the value pointed at which containsNode(const Node * n) will give you. find() will give no assurances that the value pointed at by n will go untouched, and that violates const Node * n.

You are in a right pickle, my friend. Since your key is the pointer, you probably can't use a copy of the pointed-at value, different address, nor can you assign it to a non-const pointer that can be used by find. You can cast, but so much for respecting the const! Rethink how you are doing this, is my advice.

Bit easier to visualize with a set. Less overhead, same results.

#include <set>
using namespace std;

class A
{

};

set<A*> test;

void func1(A *const  a) // pointer is const
{
    test.find(a); //Compiles, but not what you want.
    A b;
    a = &b; // Doesn't compile. Can't change where a points 
    *a = b; // compiles. Value at a is open game
}

void func2(const A *  a) // value is const
{
    test.find(a); //doesn't compile
    A b;
    a = &b; // compiles. Can change where a points
    *a = b; // does not compile. Can't change what a points at
    test.find((A*)a); //Compiles, but holy super yuck! Find a better way!
}

int main()
{
    A a;
    func1(&a);
    func2(&a);
}

Aleris

Yeah, you are totally right. So I guess I'd better use a Node instead of a Node* as the key value to ensure the const qualifier. Thank you very much! – Araldo

I'm quite rusty with C++ and I'm running into the same issue while writing code for a graph. If the question's author should "rethink how they are doing this," I'm curious – what is the "C++ way" of representing graph? How would a collection of edges be represented if using a node pointer as the key for a map or multimap is problematic? – Computation