1

I am trying to create a graph. I am modelling the edges as a std::pair of the connected vertices and the weights of the edges connecting these vertices. I am inserting this edge through another graph class which holds all these vertices as a std::set.

The way I am going about it is as follows:

Here's the vertex class :

class Vertex {
public:
    friend std::ostream &operator<<(std::ostream &os, const Vertex &v);
    Vertex(char c) : ID_(c) {}
    bool operator==(const Vertex &rhs) const {
        return (this->ID_ == rhs.ID_);
    }
    bool operator<(const Vertex &rhs) const {
        return (this->ID_ < rhs.ID_);
    }

    char ID_;
    std::vector<std::pair<Vertex, int>> neighbors;
};

Here's the graph class which holds the vertices:

class Graph {
public:
    friend std::ostream &operator<<(std::ostream &os, const Graph &g);
    Graph(); 
    Graph(char c[]);
    void insertVertex(char c);
    void insertEdge(char ID1, char ID2, int weight);

protected:
    std::set<Vertex> vertices_;
};

And here's my edge insertion method:

void Graph::insertEdge(char c1, char c2, int w) {
    auto it1 = vertices_.find(c1);
    auto it2 = vertices_.find(c2);
    auto p1 = std::make_pair(*it1, w);

    if(it1 != vertices_.end())
        it1->neighbors.push_back(p1);  // Fails here
}

Does the -> operator return the object that the iterator points to, or does it return something like a const reference to it?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Jib Ran
  • 11
  • 2
  • @JeJo there is a constructor that converts char to vertex so it's fine. – Marcin Poloczek Aug 21 '21 at 22:36
  • What do you mean by "it fails"? – hegel5000 Aug 21 '21 at 22:41
  • My bad, fails to compile there where I try to access the attribute of the object pointed by the iterator. – Jib Ran Aug 21 '21 at 22:43
  • 1
    You should include the compilation error message in the question. – hegel5000 Aug 21 '21 at 22:44
  • 2
    Note that `insertEdge()` is not using `c2`/`it2` for anything meaningful, and `std::make_pair(*it1, w)` is undefined behavior if `c1` does not already exist in the set (`it1` is the `end` iterator). There is no reason to use `*it1` at all in this code, use `c1` or `c2` instead as needed. – Remy Lebeau Aug 21 '21 at 22:45
  • I deduced that its a compiler error from the error message the editor (VS code) shows when you hover the cursor over a red-underlined piece of code. – Jib Ran Aug 21 '21 at 22:45
  • Your `Vertex` class is neither moveable nor copyable, so neither is ``, but an operation on a vector that may modify it `std::pair`. However `push_back` (or any other operation that may modify the size of the backing array used by the vector) requires the elements of the vector to be copyable or movable, since the operation may require the data to be moved to a new, larger array, if the capacity changes... Furthermore if the `==` operator is implemented for a combination of types, I'd expect the `!=` operator to be implemented for the same combination as well... – fabian Aug 21 '21 at 22:54
  • Sorry, I don't follow what makes `Vertex` unmovable and uncopyable? – Nathan Pierson Aug 21 '21 at 22:58
  • Same question as Nathan. I was eventually after making that particular attribute mutable, able to push_back. – Jib Ran Aug 22 '21 at 22:13

1 Answers1

0

I think I found the problem. std::set cant be modified, atleast not directly. To make its elements modifiable, I did something like this:

mutable std::vector<std::pair<Vertex, int>> neighbors;

Basically making the attribute of the element that I want to modify in the set mutable.

Thanks to this answer : https://stackoverflow.com/a/7340470/14635766

Jib Ran
  • 11
  • 2
  • 2
    The compilation errors are there for a reason, and using `mutable` to get around it is a dangerous thing to do. `set` prevents you from modifying the elements is because if you modify them, the `set` won't know this and can't update its internal bookkeeping (e.g. `it1->ID_ = ...`). You seem to actually want a `map` or `unordered_map`, not a `set`, as that will allow you to modify the value. If you must use `set`, you should [`extract`](https://en.cppreference.com/w/cpp/container/set/extract) the node and modify it, then send it back to the `set`; that way it knows about the changes. – Justin Aug 21 '21 at 23:15
  • Thanks a lot! Although, since I am fairly new to this datastructure, what is the idea/application(s) behind making a set un-modifiable? My reason for using set was to use any datastructure that prevents duplicate elements from getting in. But the reason I didnt want to use a map was I didnt know what keys I should assign. – Jib Ran Aug 21 '21 at 23:36
  • And in this case, when I make the std::map of the neighbors (the attribute of the object in the set) mutable, does it also mean that the elements held by the std::map are also mutable? In which case, its worth the pain to shift from std::set to std::map and figure out the keys. – Jib Ran Aug 21 '21 at 23:40
  • 1
    _what is the idea behind making a set un-modifiable?_ The elements in a `set` are implicitly sorted (usually by being stored in some sort of tree). If you could change them, then the `set` would have to be rebuilt every time you did so. _are the elements held by the `std::map` mutable?_ The values are, the keys (for the same reason as the elements in a `set`) are not. – Paul Sanders Aug 22 '21 at 00:32
  • So the elements that dont affect the sorting process, if they are made mutable, it doesnt matter right? – Jib Ran Aug 22 '21 at 22:10
  • 1
    I wouldn't rely on that, personally. – Paul Sanders Aug 23 '21 at 01:14