I am confused about constant, constant references, references to constants, ... (including example code)

Question

I am trying to write a graph data structure implementation that I feel satisfied with. (Maintain adjacency lists as sets instead of linked lists.) Anyways, I tried to use references and iterators and wrote this:

#include <iostream>
#include <string>
#include <set>
#include <stack>

class Vertex {
    std::string name;
    std::set<Vertex> edges;
public:
    Vertex(std::string name) : name(name) {}

    std::string vertexName() const {
        return name;
    }

    std::set<Vertex> outEdges() const {
        return edges;
    }

    void addEdge(const Vertex& other) {
        edges.insert(other);
    }

    void removeEdge(const Vertex& other) {
        edges.erase(other);
    }

    int outDegree() {
        return edges.size();
    }
};

bool operator<(const Vertex& v1, const Vertex& v2) {
    return (v1.vertexName().compare(v2.vertexName()) < 0);
}

void DFS(const Vertex& v) {
    std::stack<Vertex*> stack;
    std::set<Vertex*> visited;


    stack.push(&v);             // error1
    visited.insert(&v);         // error2

    while (!stack.empty()) {
        Vertex* vert_ptr = stack.top();
        stack.pop();

        std::cout << vert_ptr->vertexName() << std::endl;

        //
        for (std::set<Vertex>::iterator iter = vert_ptr->outEdges().begin(); iter != vert_ptr->outEdges().end(); iter++) {
            if (visited.find(&(*iter)) != visited.end()) {      // error3
                stack.push(&(*iter));                           // error4
                visited.insert(&(*iter));                       // error5
            }
        }
    }
}

int main() {
    Vertex a = Vertex("a");
    Vertex b = Vertex("b");
    Vertex c = Vertex("c");

    DFS(a);

    getchar();
    return 0;
}

I am getting the following errors:

• error1: E0304 no instance of overloaded function "std::stack<_Ty, _Container>::push [with _Ty=Vertex *, _Container=std::deque<Vertex *, std::allocator<Vertex *>>]" matches the argument list
• error2: E0304 no instance of overloaded function "std::set<_Kty, _Pr, _Alloc>::insert [with _Kty=Vertex *, _Pr=std::less<Vertex *>, _Alloc=std::allocator<Vertex *>]" matches the argument list
• error3: E0304 no instance of overloaded function "std::set<_Kty, _Pr, _Alloc>::find [with _Kty=Vertex *, _Pr=std::less<Vertex *>, _Alloc=std::allocator<Vertex *>]" matches the argument list
• error4: E0304 no instance of overloaded function "std::stack<_Ty, _Container>::push [with _Ty=Vertex *, _Container=std::deque<Vertex *, std::allocator<Vertex *>>]" matches the argument list
• error5: E0304 no instance of overloaded function "std::set<_Kty, _Pr, _Alloc>::insert [with _Kty=Vertex *, _Pr=std::less<Vertex *>, _Alloc=std::allocator<Vertex *>]" matches the argument list

I am realizing that I do not understand references as well as I thought I did. I used google, and the hits I got reiterate what I understand about references, but do not touch on the part I do not understand (which is causing those errors).

I also dereferenced the iterators, and then used & to get the addresses of the actual objects the iterators are pointing to, and do not know if I am misunderstanding the way iterators work, or if it is just a problem with references.

I would appreciate it if someone could point me towards a good reference on all of this. :(

Answer 1

In your case void DFS(const Vertex& v) v is a reference to a var which is constant. In other words, you promised that the function will not modify the object.

std::stack<Vertex*> stack;
std::set<Vertex*> visited;

The above are containers of pointers to an object, which is not a constant and therefore is modifiable.

Here you are trying to violate an agreement. You are trying to allocate a pointer to a constant object v in a container which is intended for pointers to modifiable objects. If this is would have been allowed, you would be able to modify the value referenced by v through the pointer. So, it is not allowed and the compiler produces an error here.

stack.push(&v);             // error1
visited.insert(&v);         // error2

so, you needed to declare containers with pointers to the constants:

std::stack<const Vertex*> stack;
std::set<const Vertex*> visited;

now, the visited.find(&(*iter)) has to do with the implementation of the set::iterator. Apparently the value returned by operator '*' referenced a constant value, causing another conversion attempt from 'const' to non-const.

So, declaring stack and visited with const Vertex * argument should solve your compilation issues.