Loop through a vector contained within a class in C++ without copying affecting values?

Question

I am trying to write an algorithm to check if a graph is connected, (building a board game in which the map is contained as a graph where Regions are Vertices and Borders are edges).

Each region contains a vector of regions that are its neighbors (vector neighbors).

I build the map and check if its connected in the main() function here:

int main()
{
    Map map;
    Region r1("R1");
    Region r2("R2");
    Region r3("R3");



    r1.addNeighbor(r2);
    r2.addNeighbor(r1);
    r2.addNeighbor(r3);
    r3.addNeighbor(r2);

    map.addRegion(r1);
    map.addRegion(r2);
    map.addRegion(r3);

    map.traversal(r1);
    map.isConnected();

    return 0;
}

And here is my traversal() and isConnected() method implementation:

void Map::traversal(Region currentNode)
{
    visited.push_back(currentNode.getRegionName());
    Region* current = &currentNode;
    cout << (*current).getRegionName() << " loc: " << current << endl;
    for (auto const & neighbor : (currentNode).getNeighbors())
    {
        if (std::find(visited.begin(), visited.end(), neighbor.getRegionName()) != visited.end()) {
        }
        else {
            cout << (neighbor).getRegionName() << " neighbors: " << (neighbor).getNeighbors().size() << " location: " << &(neighbor) << endl;
            traversal(neighbor);
        }
    }
}

bool Map::isConnected()
{
    cout << visited.size() << endl;
    cout << regions.size() << endl;
    vector<string> regionList;

    for (int i = 0; i < regions.size(); i++)
    {
        regionList.push_back(regions[i].getRegionName());
    }
    if (visited.size() == regionList.size())
    {
        return true;
    }
    else
    {
        return false;
    }

}

The issue I have here is that for some reason, when I get the neighbors of nodes other than the starting node during the recursion of the traversal function, the function for some reason sometimes no longer remembers the neighbors of the current node being traversed (the output of the (neighbor).getNeighbors().size() will sometimes be equal to 0). Also, the address of the currentNode is not always the same as the address of the original object being referenced, leading me to believe that it is copying the object rather than directly pointing to its memory location.

Any help would be appreciated. I am still very new to C++ and the concept of pointers.

Here's the code for my Region class by request: Region.h

#pragma once
#include <string>
#include <vector>
using namespace std;

class Region
{
private:
    string owner;
    string regionName;
    int numTokens;
public:
    vector<Region> neighbors;
    void setOwner(string playerName);
    void setRegionName(string name);
    void setNumTokens(int num);
    void addNeighbor(Region r);
    vector<Region> getNeighbors() const;
    string getOwner() const;
    string getRegionName() const;
    int getNumTokens() const;
    Region();
    Region(string regionName);
    ~Region();

};

Region.cpp

#include "stdafx.h"
#include "Region.h"


Region::Region()
{
}

Region::Region(string name)
{
    regionName = name;
    owner = "none";
    numTokens = 0;
}

Region::~Region()
{
}

void Region::setOwner(string playerName)
{
    playerName = owner;
}

string Region::getRegionName() const
{
    return regionName;
}

int Region::getNumTokens() const
{
    return numTokens;
}

void Region::setRegionName(string name)
{
    regionName = name;
}

void Region::setNumTokens(int num)
{
    numTokens = num;
}

void Region::addNeighbor(Region r)
{
    neighbors.push_back(r);
}

vector<Region> Region::getNeighbors() const
{
    return neighbors;
}

string Region::getOwner() const
{
    return owner;
}

Answer 1

In

void Map::traversal(Region currentNode)

currentNode is passed by value. This means currentNode is independent of and (anywhere it matters) a copy of the Region provided as a parameter when invoking traversal. This is the different addresses you are noting with

cout << (*current).getRegionName() << " loc: " << current << endl; 

Fix with

void Map::traversal(Region & currentNode)

although

void Map::traversal(const Region & currentNode)

is preferred if you do not intend on changing currentNode inside the function (or as a result of the function). It prevents mistakes, and since you have promised not to change the provided Region, the compiler can take advantage of some tricks and optimizations.

The next boobytrap is

vector<Region> neighbors;

stores copies of whatever is placed in them, not the original. So

r1.addNeighbor(r2);

calls

void Region::addNeighbor(Region r)

which is also pass by value (r is a copy of r2) and

neighbors.push_back(r);

places a copy of r into the vector. End result is r1 does not really know r2, it knows a copy. Modifying r2 after the copy does not effect the copy. You are trapped. You must store pointers.

Region needs to look something more like

class Region
{
private:
    string owner;
    string regionName;
    int numTokens;
public:
    vector<Region *> neighbors; // change here
    void setOwner(string playerName);
    void setRegionName(string name);
    void setNumTokens(int num);
    void addNeighbor(Region * r); // change here
    vector<Region *> getNeighbors() const; // change here
    string getOwner() const;
    string getRegionName() const;
    int getNumTokens() const;
    Region();
    Region(string regionName);
    // ~Region(); not required.

};

Unrelated: Region contains no resources that are not self managed and as a result can take advantage of The Rule of Zero. You can safely remove its destructor. Yes. I know it contains a vector of raw pointers. More on this below.

This can lead you into a memory management nightmare, so you have to make sure you have ownership of those Regions everyone is pointing at nailed down.

Ownership is basically "Who's responsible for the clean-up? Who makes sure what's being pointed at is freed when its no longer required?"

In the case of your example,

Region r1("R1");

Is an Automatic variable. It manages it's own lifetime. It is released when it goes out of scope. You can

r1.addNeighbor(&r2); //pass raw pointer to r2

and r2 will be destroyed on schedule right before r1, which if you think about it is kinda dangerous. r1 still holds a pointer to r2, but r1 is also going out off scope, so you'd need to do something stupid in the destructor or go multi threaded. Region doesn't need a destructor, so you're safe, and if you are multi threaded a whole new set of assumptions are required, like why are you going out of scope in main while you still have threads running?

But what about less trivial cases where you're adding and removing Regions and reshaping the graph dynamically?

This gets ugly fast.

Often people will elect to go with a smart pointer in neighbors to manage the memory for them. Doesn't work well in your case. Doesn't work well for them in a lot of cases, either.

vector<unique_ptr<Region>> (one-and-only-one pointer) doesn't make any sense because there can be many Regions all pointing at the same Region. So much for uniqueness.

shared_ptr also doesn't make sense because r1 points to r2 and r2 points back to r1. Direct action will have to be taken to eliminate the cycle and this mostly defeats the point of a smart pointer. What if you forget or get derailed by an exception?

There are games one can play with weak_ptr, but in a bidirectional graph who is the shared and who is the weak?

Opinion Warning: I favour Regions using raw pointers and a master list of Regions (vector<unique_ptr<Region>> again, but this time it works) as a member of a Graph class that manages access, insertion, removal, and all the other manipulations the same way you would with a linked list managing the linked nodes.

There may be sharper solutions out there that I'm not seeing.

Edit: Here's one based on M.M.'s comment

class Region
{
private:
    string owner;
    string regionName;
    int numTokens;
public:
    vector<string> neighbors; // change here. If you have large numbers of neighbours 
                              // consider using a std::set in place of the vector
    void setOwner(string playerName);
    void setRegionName(string name);
    void setNumTokens(int num);
    void addNeighbor(const string & name); // change here. Accepting const reference 
                                           // reduces unnecessary copying. May want
                                           // to use the same trick for other methods 
                                           // receiving a string
    const vector<string> & getNeighbors() const; // change here. Returning const 
                                                 // reference reduces unnecessary copying
    string getOwner() const;
    string getRegionName() const;
    int getNumTokens() const;
    Region();
    Region(string regionName);
    // ~Region(); not required.

};

This assumes regionName is unique and uses it as the key to access the Region from a master list that looks something like map<string, Region> masterlist;. masterlist manages storage for all of your Regions. Remove a Region from it and If the regionName cannot be found in masterlist you don't have to worry about invalid pointers, you just take note and remove it from neighbors.

Remember to be careful with the subscript operator. In masterlist[name] if name cannot be found, a Region will be default constructed for it and stored. Prefer to use the find method if you are looking for a Region that should exist.

If you have a fixed number of regions, consider using a simple array or std::array in place of the map for masterlist and use the index of the Region in the array as the identifier in place of string.

Supplemental reading: What's the difference between passing by reference vs. passing by value?