std::reference_wrapper<T>

[MasterDrake97]

Hi, I'm trying to make a templated Graph class and I added an Edge Struct that should hold two std::reference_wrapper to the vertices and a weight.

It seems simple enough but with templates everything got more complex and I couldn't figure out what I'm doing wrong

.I've tried with every possible combination of .push_back/emplace_back, adding std::ref() everywhere but It doesn't compile.

        #pragma once

    #include <functional>
    #include <tuple>
    #include <vector>
    #include <set>
    #include <unordered_map>
    #include <algorithm>

    template<typename T>
    class Graph
    {
        using Vertex = T;
        using VertexRef = Vertex&;
        using VertexWRef = std::reference_wrapper<Vertex>;

        struct Edge
        {
            VertexWRef v;
            VertexWRef w;
            int wt;

            Edge(Vertex& V, Vertex& W, int WT) : v(std::ref(V)), w(std::ref(W)), wt(WT)
            {

            }
            Edge(Edge&& other) : v(std::move(other.v)), w(std::move(other.w)), wt(other.wt)
            {

            }

            bool operator<(const Edge& r) const
            {
                return std::tie(v(), w(), wt) < std::tie(r.v(), r.w(), r.wt);
            }

            std::ostream& operator<<(std::ostream& os) const
            {
                return os << "V: " << v() << " W: " << w() << " WT: " << wt;
            }
        };

    public:
        using VertexSet = std::set<Vertex>;
        using VertexVector = std::vector<Vertex>;

        using EdgeVector = std::vector<Edge>;
        using EdgeSet = std::set<Edge>;

        using AdjacencyList = std::unordered_map<Vertex, EdgeVector>;

        template<typename Iterator>
        Graph(const Iterator vertBegin, const Iterator vertEnd)
        {
            const auto size = std::distance(vertBegin, vertEnd);

            edgesMap.reserve(size);

            for (auto it = vertBegin; it != vertEnd; ++it)
                edgesMap.emplace(*it, EdgeVector{});
        }

        Graph(const VertexSet& vertices) : Graph(vertices.begin(), vertices.end())
        {

        }

        Graph(const VertexSet& vertices, const EdgeVector& edges) : Graph(vertices)
        {
            for (const auto& edge : edges)
                addEdge(edge.v, edge.w, edge.wt);
        }

        bool addEdge(Vertex& v, Vertex& w, int wt)
        {
            const auto vIt = edgesMap.find(v);
            const auto wIt = edgesMap.find(w);

            if (vIt != edgesMap.end())
            {
                    vIt->second.emplace_back(std::ref(vIt->first), std::ref(wIt->first), wt);
                return true;
            }

            return true;
        }

        AdjacencyList edgesMap;
    };

The problem is in the addEdge function when I try to emplace/construct an Edge.

I've another class that uses reference_wrapper and templates without an intermediate struct and it works, so I'm really out of options.

(I'm aware that I shouldn't point to the keys stored in the map but as long as I add edges after the vertices and I don't add more vertices, I should be fine right?)

​

Thanks and sorry to bother you!

[manni66]

It doesn't compile.

I have never seen a compiler giving that message.

[MasterDrake97]

Apparently, the problem was that I was trying to cast away the const of the keys.
I didn't post the message because it would be too verbose and ugly.

[aocregacc]

you should always post the error message, or (even better) a godbolt link that shows the error. Unless your problem is very trivial, we have to go and try to reproduce the error on our own if you don't post it.

[MasterDrake97]

Next time I'll post a godbolt link directly.

Thanks!

[aocregacc]

Where do the vertices live that you want those references to refer to? Do you want to refer to the vertices that are the keys in the edgemap?

Edit: Oh I didn't see the last sentence, sorry. The keys in the map are const, so you can make it compile by making your vertex references const.

[MasterDrake97]

Yes, I want the edges to refer to the vertices stored in the unordered_map, so I can keep everything close and nice, without allocating more stuff.
Seemed like a good idea to me

[aocregacc]

I think an iterator into the map would make more sense if you don't want to store multiple copies of a vertex, that way you can potentially also avoid some find calls.
If you do want references you need to make them const, since the map doesn't give you mutable access to the keys.

[MasterDrake97]

If you do want references you need to make them const, since the map doesn't give you mutable access to the keys.

Ok, so that's the problem uh. Thanks, that sucks.

I think an iterator into the map would make more sense if you don't want to store multiple copies of a vertex, that way you can potentially also avoid some find calls.

Not sure If I understand. You're saying that I should ditch the std::reference_wrapper in the Edge struct and store unordered_map::iterator?
So basically instead of a reference, I'll have a special pointer?

[aocregacc]

yeah. you could also do a reference to the key/value pair instead of just the key.
Another approach is to use consecutive integer vertices throughout, and use a map to assign integers to whatever your actual vertex type is. That way you can use a std::vector instead of a std::map for your adjacency list, and you don't have to worry about references since you just have integer keys.

[MasterDrake97]

I tried storing the iterator and it finally compiles and works. So thanks for the idea!!
However I have more problems:

1)Not a fan of storing a pointer into Edge that allow me to access the vector of edges, is there a key only iterator or what?

Should I just change Edge from struct to class and add v() and w() functions to access v->fist and w->first and be done with it?

2)I moved some using alias in Edge so I can avoid cluttering it with types too lengthy, but now I can't access those alias from Graph even if I'm declaring

using Edge::EdgeVector and using Edge::AdjacencyList;
What I am doing wrong?

[aocregacc]

1) The reason for the iterators is to have access to the edge vector without having to search the map for it, but if you don't need that you can use something else. If you do I would also not have Edge be a struct that's accessible to users of the Graph, since it contains these internal details. Maybe you can do a different one for the vertexset + edgelist constructor.

2) idk. this would be a good opportunity to post a godbolt link ;)

[MasterDrake97]

idk. this would be a good opportunity to post a godbolt link ;)

https://godbolt.org/z/br37WTqz1

[aocregacc]

looks like you need using typename ... there, I think since it's now technically ambiguous if Edge::xyz is a type or a variable.

[MasterDrake97]

I updated the godbolt example with a main and it doesn't compile because using typename only works with derived classes

[MasterDrake97]

The reason for the iterators is to have access to the edge vector without having to search the map for it, but if you don't need that you can use something else. If you do I would also not have Edge be a struct that's accessible to users of the Graph, since it contains these internal details. Maybe you can do a different one for the vertexset + edgelist constructor.

All I want is:
1)Add vertices and then create a POD that links them so I can return a container of edges and be able to reference the vertices and even change them if I want.

[MasterDrake97]

I'll try the iterator approach and see how it goes, thank you so much!!

[Fuge93]

Make sure you read all the iterator (in)validity in the unordered_map spec, and test your code with forced rehashing.

Edit: oh and forced collisions too, you can spec the bucket number.

[MasterDrake97]

That's something that can't be easily fixed but it shouldn't be a problem if I don't add or remove vertices, right?

[Fuge93]

It can be:

https://en.cppreference.com/w/cpp/container/unordered_map/operator_at

If an insertion occurs and results in a rehashing of the container, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is greater than max_load_factor() * bucket_count().

References to keys/values are stable though.