STL reference and return values

[nelagnelag]

Hi,

I have become completely fried looking at this, but have two main questions about the following code:

- Do I risk accessing "dead memory" by passing parameters by reference into addNeighbors() ?
(this class will be kept in a map<int, Node> object inside a Network class)
I very much want to do this by reference for:
*speed
*memory efficiency
*access to neighbor Nodes

- What am I doing wrong when calling getNeighbors()?
(last lines of code)

Thanks very much for help.

Code follows:

#include<map>
#include<iostream>

using namespace std;

class Node {

private:

  int id;
  map<int, Node> neighbors;

public:

  Node() {
  }

  Node(int newID) {
    id = newID;
  }

  int getID() {
    return id;
  }


  int addNeighbor(Node &newNode) {

    int newID;
    newID = newNode.id;

    // if not already a neighbor, add                                                                                                         
    if (!isNeighbor(newID))
      neighbors[newID] = newNode;
  }


  map<int, Node> getNeighbors() {
    return neighbors;
  }


  bool isNeighbor(int searchID) {

    map<int, Node>::iterator it;
                                                                                                                                                                             
    it = neighbors.find(searchID);

                                                                                                  
    if (it == neighbors.end()) {
      return false;
    }

    //else                                                                                                                                    
    return true;
  }

};

int main() {

  Node n0(0), n1(1);
  n0.addNeighbor(n1);

  map<int, Node> neighbors = n0.getNeighbors();
  map<int,Node>::iterator NB;
  int id = n0.getID();

  for (NB = neighbors.begin(); NB != neighbors.end() ; NB++) {

    cout << id << "'s neighbor: " << NB->second.getID() << endl;

    //TODO:  problem seems to be here:                                                                                                        
    map<int, Node> neighborsList = NB->second.getNeighbors();

    cout << NB->second.getID() << " has " << neighborsList.size() << " neighbors" << endl;
  }
}

[Peter87]

Do I risk accessing "dead memory" by passing parameters by reference into addNeighbors() ?

No. It should work fine but you should prefer reference to const. Note that neighbors stores copies of nodes. Is that what you want?

What am I doing wrong when calling getNeighbors()?
What happens and what was you expecting?

[nelagnelag]

I don't understand your comment about reference vs. const, since I am not using const.

I don't think neighbors stores copies, since I am passing by reference. neighbors should be storing references.


[quote]What am I doing wrong when calling getNeighbors()?
What happens and what was you expecting?[\quote]

output of the above program:

0's neighbor: 1
1 has 0 neighbors

So, 1 should have 1 neighbor, but somehow I am not getting access to the neighbors map properly when I return it.

[Peter87]

int addNeighbor(const Node &newNode) if you use a reference to a const your code will work also for const objects. As it is now code like this doesn't work: n0.addNeighbor(Node(3));

You are only calling addNeighbor on n0 so I don't see how n1 could have a neighbour.

You can't store references in any container. If you don't want to store copies you should store pointers.

[nelagnelag]

Thanks!

I think I have most of it working now, using boost shared_ptr.
Unfortunately, now I am still having trouble with find()

**Can you please advise on how to make isNeighbor() work?**
So, the last 2 lines seem incorrect.

---

Output of code below is:

0 adding neighbor 1
0 adding neighbor 2
1 adding neighbor 0
2 adding neighbor 1
0's neighbors
1 has 1 neighbors
0
2 has 1 neighbors
1
NOT WORKING
is 1 a neighbor of 0? 0
is 0 a neighbor of 1? 0

// g++ -I /home/galen/src/boost_1_48_0/ testSharedPtr.cc                                                                                      
#include<set>
#include<iostream>
#include<boost/shared_ptr.hpp>

using namespace std;

// use typedef instead                                                                                                                        
#define NodePtr boost::shared_ptr<Node>

// TODO: should this extend shared_ptr?                                                                                                       
class Node {

private:

  int id;

  // TODO: implement find() or find_if()                                                                                                      
  // only overload < and == ??                                                                                                                
  // Need predicate function?                                                                                                                 
  set<NodePtr> neighbors;

public:

  Node() {
  }

  Node(int newID) {
    id = newID;
  }

  ~Node() {
  }

  int getID() {
    return id;
  }

 int addNeighbor(NodePtr newNode) {

    int newID;
    newID = newNode->id;

    // if not already a neighbor, add                                                                                                         
    if (!isNeighbor(newID))
      neighbors.insert(newNode);
  }

  set<NodePtr> getNeighbors() {
    return neighbors;
  }


  bool isNeighbor(int searchID) {

    set<NodePtr>::iterator it;

    // check if this neighbor already in list                                                                                                 
    NodePtr searchNode(new Node(searchID));

    it = neighbors.find(searchNode);

    // if not found, add to neighbors                                                                                                         
    if (it == neighbors.end()) {
      return false;
    }

    //else                                                                                                                                    
    return true;
  }

  //overload == for find()                                                                                                                    
  bool operator== (NodePtr otherNode) {
    cout << "==: " << otherNode->id << " " << id << endl;

    return (otherNode->id == id);
  }

 //overload < in case we want to sort                                                                                                        
  bool operator< (NodePtr otherNode) {
    return (id < otherNode->id);
  }

};

int main() {

  // the nodes are pointers to Node objects                                                                                                   
  NodePtr n0(new Node(0));
  NodePtr n1(new Node(1));
  NodePtr n2(new Node(2));
  cout << n0->getID() << " adding neighbor " << n1->getID() << endl;
  n0->addNeighbor(n1);

  cout << n0->getID() << " adding neighbor " << n2->getID() << endl;
  n0->addNeighbor(n2);

  cout << n1->getID() << " adding neighbor " << n0->getID() << endl;
  n1->addNeighbor(n0);

  //  cout << n2->getID() << " adding neighbor " << n0->getID() << endl;                                                                      
  //  n2->addNeighbor(n0);                                                                                                                    

  cout << n2->getID() << " adding neighbor " << n1->getID() << endl;
  n2->addNeighbor(n1);

  set<NodePtr> neighbors = n0->getNeighbors();
  set<NodePtr>::iterator NB;

  int id = n0->getID();

  cout << id << "'s neighbors" << endl;

  for (NB = neighbors.begin(); NB != neighbors.end() ; NB++) {

    set<NodePtr> neighborsList = (*NB)->getNeighbors();

    cout << (*NB)->getID() << " has " << neighborsList.size() << " neighbors" << endl;
    cout << (*neighborsList.begin())->getID() << endl;
  }


 // http://www.engr.sjsu.edu/wbarrett/SortFind.htm                                                                                           
  cout << "NOT WORKING" << endl;
  cout << "is 1 a neighbor of 0? " << n0->isNeighbor(1) << endl;
  cout << "is 0 a neighbor of 1? " << n1->isNeighbor(0) << endl;

}

[nelagnelag]

Also, I'm not sure if my 2 overloaded functions are useful or correct.

thanks

[Cubbi]

Given a suitable comparator for your set, this could be made considerably simpler:

#include <set>
#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>

class Node;
typedef boost::shared_ptr<Node> NodePtr;
class Node {
  struct NodeComp {
      bool operator()(const NodePtr& p1, const NodePtr& p2) const
      {
          return p1->getID() < p2->getID();
      }
  };
  int id;
  std::set<NodePtr, NodeComp> neighbors;
public:
  Node() {}
  Node(int newID) : id(newID) {}
  int getID() const { return id; }
  void addNeighbor(NodePtr newNode) 
  {
      neighbors.insert(newNode);
  }
  const std::set<NodePtr, NodeComp>& getNeighbors() const
  {
      return neighbors;
  }
  bool isNeighbor(int searchID) const // not the most efficient, but the simplest
  {
      return neighbors.count(boost::make_shared<Node>(searchID));
  }
};

int main(){
  NodePtr n0 = boost::make_shared<Node>(0);
  NodePtr n1 = boost::make_shared<Node>(1);
  NodePtr n2 = boost::make_shared<Node>(2);
  std::cout << n0->getID() << " adding neighbor " << n1->getID() << '\n';
  n0->addNeighbor(n1);
  std::cout << n0->getID() << " adding neighbor " << n2->getID() << '\n';
  n0->addNeighbor(n2);
  std::cout << n1->getID() << " adding neighbor " << n0->getID() << '\n';
  n1->addNeighbor(n0);
  std::cout << n2->getID() << " adding neighbor " << n1->getID() << '\n';
  n2->addNeighbor(n1);
  std::cout << n2->getID() << " adding neighbor " << n1->getID() << '\n';
  n2->addNeighbor(n1);

  int id = n0->getID();
  auto neighbors = n0->getNeighbors();
  std::cout << id << " has " << neighbors.size() << " neighbors. They are: \n";

  for (auto nb = neighbors.begin(); nb != neighbors.end() ; nb++)
  {
    auto neighborsList = (*nb)->getNeighbors();
    std::cout << "   " << (*nb)->getID() << ", which has " << neighborsList.size() << " neighbors: ";
    for(auto i = neighborsList.begin(); i!=neighborsList.end(); ++i)
        std::cout << (*i)->getID() << ' ';
    std::cout << '\n';
  }
  std::cout << std::boolalpha 
       << "is 0 a neighbor of 1? " << n1->isNeighbor(0) << '\n'
       << "is 1 a neighbor of 0? " << n0->isNeighbor(1) << '\n'
       << "is 2 a neighbor of 0? " << n0->isNeighbor(2) << '\n'
       << "is 3 a neighbor of 0? " << n0->isNeighbor(3) << '\n';
}

demo: http://ideone.com/nK7eo

Note that it's bad design to have the ownership of each node shared equally by all of its neighbors: this simple example has a memory leak because there are cycles of shared pointers pointing at each other.

I would rather have a master container of nodes (possibly of shared pointers to nodes), and each node would hold a set of non-owning raw (possibly weak) pointers to its neighbors, or perhaps a set of IDs of its neighbors, or some other way of quickly uniquely identifying them.

[nelagnelag]

Hi Cubbi, thanks very much.

Hm, one problem is that STL containers can't contain standard C++ pointers, since they don't meet the requirements of STL container objects (copyable, etc.).

I have been looking for a solution that lets each node have access to the memory locations of its neighbors, but using the STL for convenience. This has been surprisingly difficult.

If I store a vector of neighbor IDs as integers in each node, I break the object-oriented model a little, and waste memory, so pointers would be very nice if they can be made to work properly.

[sohguanh]

Hm, one problem is that STL containers can't contain standard C++ pointers, since they don't meet the requirements of STL container objects (copyable, etc.).

I believe STL containers can contain standard C++ pointers. It is just that if you intend to use this container in some algorithms etc, you have to do extra work as the elements inside the container are pointers and not the actual objects themselves. You need to explicitly tell the algorithms how to do matching, comparing the objects they pointed to instead of pointers themselves etc.

This is extremely tricky but the benefit is you do save a lot of memory space and that counts when this container has many elements.

[nelagnelag]

thanks Sohguanh!

Not sure how I got the impression that raw pointers can't be put in STL containers (or maybe I wanted to avoid (de)allocation issues).

Can you give me a hint about how to do the comparisons in this case? Is this the overloading of < and == operation that I have seen in various places?

[sohguanh]

Can you give me a hint about how to do the comparisons in this case? Is this the overloading of < and == operation that I have seen in various places?

Yes. And also the copy constructor and assignment operator overloading. You just need to check which algorithm you are using with the container and then code accordingly.

If you just use it to contain and then iterate through and invoke pointer pointed to object member function, you can take easy way out and no need to do the above.

[nelagnelag]

I don't quite understand your second comment above and how that differs from the 1st option...?

thanks

[sohguanh]

What I am saying is if your use of the container of pointers is restricted to just insert and iterate through the elements to call member function, you don't have to spend effort to do operator overloading as discussed. But if you intend to use the STL algorithm which take parameters like your container, then you need to do the proper operator overloading so the algorithm can work "properly".