C++ vector copy elements?

Question

I would like to use a dynamic array in C++ (something like an ArrayList or a Vector in Java.)
In this example are the t1, t2... objects are copied or only its address is added to the vector?
Do I need to implement a copy constructor for Node class or will the default constructor make a "proper" copy (because there is a pointer in the class)?
Or should I just declare a vector<Node*> instead of this to avoid copying?
And do I have to implement a destructor to delete the other_node pointer or may it be used by the program and still be stored in the vector?

#include <vector>

using namespace std;

class Node {
public:
    int id;
    Node* other_node;
};

int main(int argc, char** argv) {
    vector<Node> nodes;
    Node t1;
    t1.id = 0;
    t1.other_node = NULL;
    Node t2;
    t2.id = 1;
    t2.other_node = &t1;
    Node t3;
    t3.id = 2;
    t3.other_node = &t2;
    Node t4;
    t4.id = 3;
    t4.other_node = &t1;
    nodes.push_back(t1);
    nodes.push_back(t2);
    nodes.push_back(t3);
    nodes.push_back(t4);
    for (vector<Node>::iterator it = nodes.begin(); it != nodes.end(); it++) {
        if (it->other_node) {
            printf("%d (other.id: %d)\n", it->id, it->other_node->id);
        } else {
            printf("%d (other.id: NULL)\n", it->id);
        }
    }
    getchar();
    return 0;
}

Answer 1

In your example vector<Node> will store copies of your nodes, so t1,t2 will be copied.

Also, the default copy constructor for Node will make a "shallow" copy. Thus

Node* head = new Node();
Node* next = new Node();
head->other_node = next;
Node* other_head = new Node(*head);

*(other_head->other_node) is the same Node as *(head->other_node) It's up to you to decide if that is the behavior you want.

Regarding destructors: You should only delete/free memory that your class instance allocated, unless you have a compelling reason to take ownership of the memory. In the case of your list, in general since your list did not allocate the memory pointed by other_node it should not delete it.

Performance wise, since your Node is fairly inexpensive to copy (an int and a pointer), storing a copy is okay. If your Node class did a deep copy, then it would be better from a performance stand point to use vector<Node*>

Answer 2

std::vector and the other C++ standard library containers have value semantics, in other words they expect to hold actual objects rather than pointer to objects. So, whenever you put an object into a standard library container, the container copies it. Value semantics have certain implications like the automatic clean up on destruction of the container causing a memory leak if your container holds pointers to objects; in that particular case you need to manually delete the pointed-to objects yourself.

My recommendation would be that if you have objects that are either cheap to copy or expensive to copy but don't get copied often, put them into the container as a value. If you require the container to hold polymorphic objects or frequently copied, expensive to copy objects, hold them in the container either using a boost::shared_ptr<> or use the appropriate boost::ptr_xxx container like a boost::ptr_vector.