2

I'm having some issues understanding a problem I've mentioned in the comments below:

class Node {
    public:
        Node(int value): value(value), neighbors() {}
        int value;
        std::vector<std::shared_ptr<Node>> neighbors;
};

    std::vector<Node> nodes;
    nodes.reserve(50);
    for(int j = 0 ; j < 50; ++j) {
        nodes.push_back(Node(j));
    }
    for(int j = 1 ; j < 25; ++j) {
        nodes.at(0).neighbors.push_back(std::make_shared<Node>(nodes.at(j)));
    }

    //The following line is copying nodes.at(0) instead of just 
    //copying a reference to nodes.at(0). Why?
    nodes.at(15).neighbors.push_back(std::make_shared<Node>(nodes.at(0)));

    for(int j = 25 ; j < 50; ++j) {
        nodes.at(0).neighbors.push_back(std::make_shared<Node>(nodes.at(j)));
    }

    std::cout << nodes.at(15).neighbors.at(0).neighbors.size();
    //Prints out 24

    std::cout << nodes.at(0).neighbors.size();
    //Prints out 49

Why is the following line copying nodes.at(0) (which returns a reference to the first element of nodes vector) instead of storing a reference to it?

    nodes.at(15).neighbors.push_back(std::make_shared<Node>(nodes.at(0)));
user1553248
  • 1,184
  • 2
  • 19
  • 33
  • That's the way it's supposed to work. BTW: To make your question more precise, find out if `push_back` or `make_shared` actually copies your node. – Ulrich Eckhardt Feb 08 '16 at 07:38
  • 1
    *How* do you know it's copied? You are aware of that `std::make_shared` will create a `Node` instance, and invoke the new objects *copy-constructor* to initialize it using the node from `nodes.at(0)`? Is it that copy-construction you're talking about? – Some programmer dude Feb 08 '16 at 07:39
  • Do you know what `std::make_shared` does? – user253751 Feb 08 '16 at 07:39
  • See here: http://en.cppreference.com/w/cpp/memory/shared_ptr/make_shared `This function is typically used to replace the construction std::shared_ptr(new T(args...))` – Itamar Katz Feb 08 '16 at 07:40
  • Is there a way to use shared pointers without invoking the copy constructor? My intention was to have the neighbors vector store pointers to objects but I did not want to go with storing raw pointers (std::vector). – user1553248 Feb 08 '16 at 07:47
  • 1
    Note that if you're planning on adding any more nodes to `nodes` after this, you can't store pointers to the nodes at all! That's because `vector` is allowed to allocate new `Node`s, copy/move the old ones into the new ones, and then delete the old ones, and any pointers to the old ones become invalid at that point. – user253751 Feb 08 '16 at 07:50
  • You'd need to make `nodes` store `shared_ptr`s too. – Alan Stokes Feb 08 '16 at 07:58
  • What you're doing is, roughly, equivalent to `Node new_node = nodes.at(0)`. The only way to not use the copy-constructor would be to use the *copy* assignment operator (e.g. `Node new_node; new_node = nodes.at(0)`). If you want to initialize one object with another of the same class, then the copy-constructor is invoked. That's how C++ works. – Some programmer dude Feb 08 '16 at 08:00
  • And here it makes no sense using a vector of share pointers, not the way you do it anyway with creating new object. The usual is to have a vector of *raw* pointers and have each of them point to the *actual* node in `nodes`. But as mentions by @immibis that won't work well if you ever resize `nodes`. A better solution would be `neighbors` to be a vector of *indexes* into the `nodes` vector. – Some programmer dude Feb 08 '16 at 08:03
  • Note that if your graph has cycles then even using `shared_ptr` needs some care, because if there are cycles the objects will never be deleted. I n general you are better off storing the list of connections separate to the list of nodes. – M.M Feb 08 '16 at 08:14

3 Answers3

3

Nothing in your code stores references. Your code copies a node because you allocate a new node in std::make_shared and invoke the copy constructor.

  std::vector<Node> nodes;

It's local to your function. It would be impossible to keep either pointers (shared or not) or references to elements of this vector. Perhaps you want to use a vector of shared pointers instead:

 std::vector<std::shared_ptr<Node>> nodes;

Bear in mind that shared_ptr doesn't work well in presence of cyclic referenced. If your data structure is a general graph, then perhaps shared_ptr is not appropriate for storing neighbours. You may want to consider weak_ptr instead (you will have to keep a container of shared pointers to all nodes separately).

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
1

Vector always stores the copies. You can find more information here : Is std::vector copying the objects with a push_back?

Community
  • 1
  • 1
kiran
  • 37
  • 5
0
// The following line is copying nodes.at(0) instead of just 
nodes.at(15).neighbors.push_back(std::shared_ptr<Node>(&nodes.at(0))); 

// Notice I didn't call make_shared, because make_shared woul allocate anew Node,
// but you already have allocated your node in your nodes vector (which is global).

// 24 as expected
std::cout << nodes.at(0).neighbors.size() << std::endl;
// 24 as well
std::cout << nodes.at(15).neighbors.at(0)->neighbors.size() << std::endl;

//Insert another element
nodes.at(0).neighbors.push_back(std::make_shared<Node>(nodes.at(30)));

// 25 as expected
std::cout << nodes.at(0).neighbors.size() << std::endl;
// 25 as well
std::cout << nodes.at(15).neighbors.at(0)->neighbors.size() << std::endl;

Let me know If I understood your issue correctly.

You could instead use std::vector<std::shared_ptr<Node>>, and then just push

nodes.at(15).neighbors.push_back(nodes.at(0));

The other solution using a vector of shared ptr would be:

std::vector<std::shared_ptr<Node>> nodes;
nodes.reserve(50);

for (int j = 0; j < 50; ++j)
    nodes.push_back(std::make_shared<Node>(j));

for (int j = 1; j < 25; ++j)
    nodes.at(0)->neighbors.push_back(nodes.at(j));

nodes.at(15)->neighbors.push_back(nodes.at(0));

// 24 as expected
std::cout << nodes.at(0)->neighbors.size() << std::endl;
// 24 as well
std::cout << nodes.at(15)->neighbors.at(0)->neighbors.size() << std::endl;

//Insert another element
nodes.at(0)->neighbors.push_back(nodes.at(30));

// 25 as expected
std::cout << nodes.at(0)->neighbors.size() << std::endl;
// 25 as well
std::cout << nodes.at(15)->neighbors.at(0)->neighbors.size() << std::endl;
Jts
  • 3,447
  • 1
  • 11
  • 14