# Copy of struct's 'instance' is added to vector instead of real instance

20 Reputation points
2023-11-29T17:54:00.1166667+00:00

Hello everyone!

I tried implementing a generic Graph, where each Node has a adjacency list of Nodes that it is connected too. The adjacency list is implemented through a vector. The graph stores its nodes in a vector.

I noticed that eventhough the Adjacency lists of the created node is not empty, the inserted node in the nodes vector of the graph has an empty adjacency list.

I figured that the problem is that some sort of copy of the node is added to the vector instead of the node reference given to the function, but I don't know how to fix it.

``````#include <iostream>
#include <vector>

using namespace std;

template <typename K>
struct Node{
K key;
vector<Node<K>> AdjList;

Node(K key) : key(key) { }
~Node() = default;

void addNodeToAdjList(Node<K>& node){
AdjList.push_back(node);
}
};

template <typename K>
class Graph{
private:
int NumberOfNodes;
vector<Node<K>> nodes;

public:
Graph() : NumberOfNodes(0) { }
Graph(int N) : NumberOfNodes(N) { }
~Graph() = default;

void addNode(Node<K>& node){
nodes.push_back(node);
}
void addEdge(Node<K>& node1, Node<K>& node2){
if(!isNodeInGraph(node1))
addNode(node1);
if(!isNodeInGraph(node2))
addNode(node2);
if(!node1.isNodeInAdjList(node2))
node1.addNodeToAdjList(node2);
cout << "The node1 has node2 in AdjList " << node1.AdjList.empty() << endl;
cout << "Now lets look at the nodes we added to the vector nodes" << endl;
for(auto n : nodes)
cout << "This is node " << n.key << " with Adjacency List empty = " << n.AdjList.empty() << endl;
}
};

``````
C++
C++
A high-level, general-purpose programming language, created as an extension of the C programming language, that has object-oriented, generic, and functional features in addition to facilities for low-level memory manipulation.
3,634 questions
{count} votes

Accepted answer
1. 160 Reputation points
2023-11-29T19:59:50.0966667+00:00

Hello,

What happens when you do that:

``````    addNode( node1 );
node1.addNodeToAdjList( node2 );
``````

Because `nodes` is a `vector<Node<K>>`, that adds a copy of `node1` in the `nodes` `vector`,
Then the copy of `node2` is added to the `node1.AdjList`, but `node1` is not the node just inserted in the `nodes` `vector`. So the node in `nodes` `vector` still have an empty `AdjList`!

You write it, you must store reference to nodes in the vectors, not nodes values.

A `vector<>` cannot store reference, it stores values. You can use in place `std::vector<std::reference_wrapper<Node<K>>>`.

``````#include <iostream>   // for std::cout
#include <vector>     // for std::vector<>
#include <functional> // for std::reference_wrapper<>

template<typename K>
struct Node {
K  key;
std::vector<std::reference_wrapper<Node>>  adjList;

Node( K const& key ) : key{key} { }
~Node() = default;

void  addNodeToAdjList( Node& node ) {
adjList.push_back( node );
}
bool  isNodeInAdjList( Node const& node )const {
return  std::find( adjList.begin(), adjList.end(), node ) != adjList.end();
}
friend bool operator==( Node const& x, Node const& y ) {
return  &x == &y;
}
};

template<typename K>
class Graph {
private:
std::vector<std::reference_wrapper<Node<K>>>  nodes;

public:
Graph() = default;
~Graph() = default;

void  addNode( Node<K>& node ) {
nodes.push_back( node );
}
bool  isNodeInGraph(Node<K>const& node)const {
return  std::find(nodes.begin(),nodes.end(),node) != nodes.end();
}
void  addEdge( Node<K>& node1, Node<K>& node2 ) {
if ( !isNodeInGraph( node1 ) )
addNode( node1 );
if ( !isNodeInGraph( node2 ) )
addNode( node2 );
if ( !node1.isNodeInAdjList( node2 ) )
node1.addNodeToAdjList( node2 );
}
void  show_nodes()const {
endl( std::cout << "The node List :" );
for ( auto const&  rwn  :  nodes ) {
std::cout << "This is node " << rwn.get().key;
if ( rwn.get().adjList.empty() )
endl( std::cout << " adjacency List is empty" );
else {
std::cout << " adjacent List : ";
for ( auto const&  rwn  :  rwn.get().adjList )
std::cout << "node " << rwn.get().key << ", ";
endl( std::cout );
}
}
}
};

int  main() {
using  Type = int;
Graph<Type>  graph;
Node<Type>  n1{1}, n2{2}, n3{3}; // Nodes ARE HERE
graph.addEdge( n1, n2 );
graph.addEdge( n1, n3 );
graph.show_nodes(); // the Nodes in graph are effectively n1 n2 n3
}
``````

But the `reference_wrapper<>` is a reference so implies that all nodes are still alive somewhere to be referenced.
We can use in place `std::vector<std::unique_ptr<Node<K>>>` in the `graph` becoming the owner of all nodes, and `std::vector<std::reference_wrapper<Node<K>>>` staying in the `AdjList` of `Node<K>` to have a single owner of each `Node`.