title: Programming a simple object oriented graph in C++
body: <p>I am really trying to be a better programmer, and to make more modular, organized code. </p>
  
  <p>As an exercise, I was trying to make a very simple <code>Graph</code> class in C++ with <code>STL</code>. In the code below, my <code>Node</code> object does not compile <a href="https://stackoverflow.com/questions/1155142/why-do-i-get-an-error-in-forming-reference-to-reference-type-map">because the commented line results in a reference to a reference in <code>STL</code></a>. </p>
  
  <pre><code>#include &lt;set&gt;
  
  class KeyComparable
  {
  public:
    int key;
  };
  
  bool operator &lt;(const KeyComparable &amp; lhs, const KeyComparable &amp; rhs)
  {
    return lhs.key &lt; rhs.key;
  }
  
  class Node : public KeyComparable
  {
  public:
    // the following line prevents compilation
    // std::set&lt;Node &amp;&gt; adjacent;
  };
  </code></pre>
  
  <p>I would like to store the edges in a <code>set</code> (by <code>key</code>) because it allows fast removal of edges by key. If I were to store <code>list&lt;Node*&gt;</code>, that would work fine, but it wouldn't allow fast deletion by <code>key</code>. </p>
  
  <p>If I use <code>std::set&lt;Node&gt;</code>, changes made through an edge will only change the local copy (not actually the adjacent <code>Node</code>). If I use <code>std::set&lt;Node*&gt;</code>, I don't believe the <code>&lt;</code> operator will work because it will operate on the pointers themselves, and not the memory they index. </p>
  
  <p>I considered wrapping references or pointers in another class, possibly my KeyComparable class (according to the linked page, this is how boost handles it).</p>
  
  <p>Alternatively, I could store the <code>std::list&lt;Node*&gt;</code> and a <code>std::map&lt;int, iterator&gt;' of locations in the</code>std::list`. I'm not sure if the iterators will stay valid as I change the list. </p>
  
  <p>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 <code>C</code>-style in every language I use, and actually become a good programmer.</p>
  
  <p>What do you think is the <strong>best</strong> way to handle this problem? Thanks a lot. </p>