Programming a simple object oriented graph in C++

Question

I am really trying to be a better programmer, and to make more modular, organized code.

As an exercise, I was trying to make a very simple Graph class in C++ with STL. In the code below, my Node object does not compile because the commented line results in a reference to a reference in STL.

#include <set>

class KeyComparable
{
public:
  int key;
};

bool operator <(const KeyComparable & lhs, const KeyComparable & rhs)
{
  return lhs.key < rhs.key;
}

class Node : public KeyComparable
{
public:
  // the following line prevents compilation
  // std::set<Node &> adjacent;
};

I would like to store the edges in a set (by key) because it allows fast removal of edges by key. If I were to store list<Node*>, that would work fine, but it wouldn't allow fast deletion by key.

If I use std::set<Node>, changes made through an edge will only change the local copy (not actually the adjacent Node). If I use std::set<Node*>, I don't believe the < operator will work because it will operate on the pointers themselves, and not the memory they index.

I considered wrapping references or pointers in another class, possibly my KeyComparable class (according to the linked page, this is how boost handles it).

Alternatively, I could store the std::list<Node*> and a std::map<int, iterator>' of locations in thestd::list`. I'm not sure if the iterators will stay valid as I change the list.

Ages ago, everything here would just be pointers and I'd handle all the data structures manually. But I'd really like to stop programming C-style in every language I use, and actually become a good programmer.

What do you think is the best way to handle this problem? Thanks a lot.

Seth Carnegie · Accepted Answer · 2012-03-17 19:01:19Z

9

As you have deduced, you can't store references in STL containers because one of the requirements of items stored is that they be assignable. It's same reason why you can't store arrays in STL containers. You also can't overload operators without at least one being a user-defined type, which makes it appear that you can't do custom comparisons if you store pointers in an STL class...

However, you can still use std::set with pointers if you give set a custom comparer functor:

struct NodePtrCompare {
    bool operator()(const Node* left, const Node* right) const { 
        return left->key < right->key;
    }
};

std::set<Node*, NodePtrCompare> adjacent;

And you still get fast removals by key like you want.

edited Mar 17, 2012 at 19:01

answered Mar 17, 2012 at 16:18

Seth Carnegie

75.3k22 gold badges185 silver badges252 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user Over a year ago

+1 Good answer. Is there any additional benefit to wrapping the comparison function in a struct (aside from the nicer syntax than function pointers)?

Seth Carnegie Over a year ago

@Oliver not that I know of really, it's just the only way to do it in this case. I would prefer having globally accessible operator< though when you can, because it makes instances comparable without having to instantiate a struct.

Collectives™ on Stack Overflow

Programming a simple object oriented graph in C++

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related