Calling std::vector::push_back() is changing previous elements in vector?

Question

First off, some boiled down code:

#ifndef UNDIRECTED_GRAPH_HPP
#define UNDIRECTED_GRAPH_HPP

#include <vector>
#include <iostream>

template <typename T>
struct undirected_graph
{
    struct node
    {
        T data;
    };

    struct edge
    {
        node& node0;
        node& node1;
    };

    ~undirected_graph() {
        for (auto n : nodes_) delete n;
        for (auto e : edges_) delete e;
    }

    const node& add_new_node(const T& data);

private:
    std::vector<node*> nodes_;
    std::vector<edge*> edges_;
};

template <typename T>
const typename undirected_graph<T>::node&
undirected_graph<T>::add_new_node(const T& data)
{
    node *n = new node { data };
    nodes_.push_back(n);
    for (auto x : nodes_) std::cout << x->data.pos.x << "," << x->data.pos.y << std::endl;
    return *n;
}

#endif

The problem exists in undirected_graph::add_new_node(const T& data). I added the output to console for debugging purposes, since I'm only using this class with my own data type so far. Everytime I'm calling this method, it seems the previous entries in thenodes_ vector are all being changed to the last element.

I figured it might have to do with the type of data I'm choosing to store in my graph, so I'm adding the part of the code that calls it as well:

// Somewhere in dungeon_generator.cpp ...
undirected_graph<const DungeonLayout::Room&> graph;

for (auto room : dungeon->rooms) {
    graph.add_new_node(room);
}

So either my method is flawed, or the way I'm calling it is flawed, or both. But I can't seem to figure out what is going wrong! Can someone please help me?

To illustrate the problem even further, I've added the output of a couple of calls to the method. The dungeons_->rooms container contains a bunch of rooms at randomly generated positions (denoted by their pos attribute)

2,2
9,9
9,9
3,2
3,2
3,2
2,6
2,6
2,6
2,6
9,3
9,3
9,3
9,3
9,3

I don't know whether it's causing your problem, but the class breaks the [Rule of Three](http://stackoverflow.com/questions/4172722) and will unleash chaos if you ever copy it. — Mike Seymour, Nov 14 '13 at 11:45
You are completely right. In an attempt to fix my problem, I changed the vectors to hold pointers to the heap instead of objects, unsuccesfully. This was late at night/early in the morning, so I hastily added the destructor and forgot about the other 2. Thanks for the heads up! — robrene, Nov 14 '13 at 11:50

score 2 · Accepted Answer · answered Nov 14 '13 at 11:44

2

Seems your storing references to the temporary variable room. Change

undirected_graph<const DungeonLayout::Room&> graph;

to

undirected_graph<DungeonLayout::Room> graph;

answered Nov 14 '13 at 11:44

Henrik

23,186
6
42
92

3

Or change the loop variable to `auto const &`, if you want to keep the reference semantics. – Mike Seymour Nov 14 '13 at 11:46
Thanks, this is absolutely correct! I was expecting `auto` to automatically use references, I guess I still have to learn more about these C++11 features. – robrene Nov 14 '13 at 11:51

Calling std::vector::push_back() is changing previous elements in vector?

1 Answers1