All elements in a c++ vector point to the same element

Question

I'm a complete beginner in c++ and everything has been going on well until now. I'm new to the idea of pointers (I'm from python), and I have this weird error.

So basically, I created this "SearchNode" class, and found below is one of it's methods "getChildren" which should return a vector of other SearchNode instances, representing the possible cells to which a Knight (chessboard) could travel from it's current state. (BFS)

That said, when I finish pushing into my vector, all the elements suddenly point to 1st element only. Could someone help me out here?

PS: it's a similar problem to c++ push_back doesn't work as it is supposed ... but unlike Angela (who's was writing her own compiler), I'm a total beginner in c++. Your help with be greatly appreciated.

UPDATE

I got rid of the int*, and used array for my state. I could now successfully search the graph (therefore the states are ok) and find the shortest path, but I couldn't seem to reconstruct the path.

To test, I started at {0,0} and could find {4,4}, but the path, according to the getPath method was {4,4}, {3,6}, {3,6}, {3,6} ... (infinite loop of {3,6}). Is there something wrong with my parent pointers, or my getPath function? Thanks for your support in advance.

//Search class
class SearchNode
{
public:
//Variables
SearchNode *m_parent;
array<int,2> m_state; //I don't understand typedef's yet, will use them when I'm clearer with them :)

//Normal Constructor
SearchNode(array<int,2>& state_, SearchNode *parent_=nullptr) :
m_state(state_),
m_parent(parent_)
{}


//Method to get Next reachable states. Returns instances of SearchNode.
vector<SearchNode> getChildren()
{
    int legalMoves[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};

    vector<SearchNode> children;
    children.reserve(8);
    for(int i=0; i<8; i++)
    {
        int x = (m_state[0] + legalMoves[i][0]);
        int y = (m_state[1] + legalMoves[i][1]);
        if( (x>-1) and (x<9) and (y<9) and (y>-1)) // Within the bounds of the board
        {
            array<int,2> childState = {x,y};
            SearchNode childNode = SearchNode(childState,this);
            children.push_back(childNode);
        }
    }
    return children;
}

void getPath()
{
    cout<<"\nPath: ";
    cout<<  this->print();
    SearchNode current = *this;
    unsigned int counter = 1;
    while((current.m_parent!=nullptr) and counter< 10)
    {
        counter++;
        cout<< (current.m_parent)->print();
        current = *(current.m_parent);
    }
    cout << (current.m_parent)->print();
}

string print()
{
    stringstream out;
    out << "{" << this->m_state[0] << "," << this->m_state[1] << "} ";
    return out.str();
}
};

Answer 1

Lots of mistakes and errors, I strongly suggest you turn up the warning level in your compiler so you can get more information. With GCC/G++/Clang, try "-Wall" or "-Wextra", as moshbear points out.

Your nodes never get assigned the "parent" value, you're creating a "shadow" local variable called "parent" and assigning that. To avoid common errors like this, use a prefix or postfix for member variable names to separate them from local names, e.g. "m_parent" or "_parent".

You don't assign default values in your constructor, you explicitly leave the values uninitialized.

SearchNode()
{
    //do nothing
}

and then you introduce this garbage data in your pointer-based constructor, what you probably want is

SearchNode() : parent(NULL), state(NULL) {}

Your copy constructor is a disaster. You need to read up on and understand pointers and local variables.

//Start Node constructor. Still looking for an equivalent for null.
SearchNode(int *state)
{
    int genericStartState[2] = {-1,-1};
    SearchNode blankParent = SearchNode();
    SearchNode genericStart = SearchNode(genericStartState,&blankParent);
    this->parent = &genericStart;
    this->state=state;
}

Firstly, "blankParent" here is a local variable containing random data because of your current copy constructor. Secondly, you're taking the address of it - of a private, local variable, which is about to stop existing when you hit the "}" at the end of the routine.

"genericStartState" is also about to go out of scope.

And aside from that, I don't think you want or need this particular constructor.

But fundamentally, the bug in your subject, is because you do the same thing in your assignment loop -- you use a temporary, local array to store the new values, and then pass a pointer to that to your constructor. Since you are taking the address, it will be the same every loop.

    int childState[2] = { x, y };
    SearchNode childNode = SearchNode(childState,this);

This is why all of your nodes have the same state - because they all point to the same memory location (edit: as pointed out by DyP, that side-effect isn't something you can count on, just an artefact of ordering in this case).

It might be easier for you to use simple array of ints rather than a pointer in your node structure.

Here's how the constructor side of things might look, if your compiler is VisualStudio 2012 or G++ 4.8 or Clang 4.2.

class SearchNode
{
public:
    typedef std::array<int, 2> State;

private:
    // I use the 'm_' convention for members, 'g_' for globals, 's_' for statics.
    SearchNode* m_parent;
    State       m_state;

public:
    //////////
    // Default ctor.
    SearchNode()
        : m_parent(nullptr) // C++11 constant meaning pointer with value 0
        , m_state({-1, -1}) // preferred but requires recent C++11 features
    {
        //m_state[0] = m_state[1] = -1; // had to do this instead for gcc 4.7.3
    }

    //////////
    // Normal ctor
    // I use the '_'-postfix convention for parameter names.
    SearchNode(SearchNode* parent_, const State& state_)
        : m_parent(parent_)
        , m_state(state_)
    {
    }

    //////////
    // Copy constructor.
    // We could do this, but it's the default behavior anyway.
    /*
    SearchNode(const SearchNode& rhs)
        : m_parent(rhs.m_parent)
        , m_state(rhs.m_state)
    {
    }
    */

    // Current C++11 compilers let us be explicit and do this:
    //SearchNode(const SearchNode& rhs) = default;

    // But it's the default behavior so we don't have to do this one at all.
};

The latest C++11 language changes (MSVC > 2012, GCC >= 4.8, Clang >= 4.1) would allow you to replace the first two constructors with

// Kill two birds with one stone and have default parameters on our normal ctor,
// replacing both the default and normal ctor with one function.
SearchNode(SearchNode* parent_ = nullptr, const State& state_ = { -1, -1 }))
    : m_parent(parent_)
    , m_state(state_)
{       
}

If you had a fully C++1y compatible compiler, you could boil all that down to:

class SearchNode
{
public:
    typedef std::array<int, 2> State;

private:
    // I use the 'm_' convention for members, 'g_' for globals, 's_' for statics.
    SearchNode* m_parent = nullptr; // c++1y keyword to replace 'NULL'
    State       m_state = { -1, -1 };

public:
    SearchNode() = default;
            SearchNode(const State& rhs_) = default; // not strictly required.
    SearchNode(SearchNode* parent_, const State& state_)
        : m_parent(parent_), m_state(state_)
        {}
};