0

I have trying to implement graph algorithms in C++, but I am getting no instance of overloaded function "std::set<_Key, _Compare, _Alloc>::insert [with _Key=Node &, _Compare=std::less<Node &>, _Alloc=std::allocator<Node &>]" matches the argument list -- argument types are: (Node) -- object type is: std::set<Node &, std::less<Node &>, std::allocator<Node &>>C/C++(304) every time I use insert method for a set. Because I am new to C++, I was not able to understand this error despite some Googling and reading documentation.

Is possible to insert a reference into a set and what is the right way of doing so? If not, how should I be doing this instead?

This is a part of the code I have been trying to debug:

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

class Node {
  public:
    set<Node &> neighbours;
    int value;

    Node(int value_) { this->value = value_; }

    void addEdgeUndirected(Node &other) {
        if (neighbours.count(other) == 0) {
            neighbours.insert(other);
            other.neighbours.insert(this);
        }
    }

    void print() { cout << value << " "; }
};

class Graph {
    map<int, Node &> node_map;

  public:
    vector<Node &> bfs(Node &node) {
        vector<Node &> bfs_traversal; // to store all pointers of all
                                      // the visited nodes

        set<Node &> visited;

        queue<Node &> to_visit;
        to_visit.push(node);

        while (!to_visit.empty()) {
            Node &current = to_visit.front();
            to_visit.pop();
            visited.insert(current);
            for (Node neighbour : current.neighbours) {
                if (visited.count(neighbour) == 0) {
                    to_visit.push(neighbour);
                    visited.insert(neighbour);
                }
            }
            bfs_traversal.push_back(current);
        }

        return bfs_traversal;
    }
};
lightsaber
  • 29
  • 6
  • 1
    You can't have a vector of references: [answer](https://stackoverflow.com/a/8200749/980129) – Manuel Dec 04 '20 at 21:17
  • 1
    You cannot hold pure C++ references but you can hold reference wrappers via std::vector>. See https://en.cppreference.com/w/cpp/utility/functional/reference_wrapper – Secundi Dec 05 '20 at 00:13
  • Could you also tell which one is better to use here — reference wrappers or pointers in place of references? – lightsaber Dec 05 '20 at 11:21
  • 1
    It depends. For a public or even for most protected interfaces/interface like usage, raw pointers should generally be avoided as far as possible. Otherwise, there are not so many real differences here. A major difference is the additional possible nullptr-state for pointers that is not possibe for references/reference wrappers. And smart pointers on the other hand might have some overhead in doubt but won't be avoidable somehow as soon as your nodes/graph here for your example become abstract ones. – Secundi Dec 07 '20 at 07:32

0 Answers0