title: boost::iterator_facade and std::find(...)
body: <p>Below is an implementation of an iterator_facade for a linked list node. It's pretty much the same as that presented in <a href="http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/iterator_facade.html" rel="nofollow noreferrer">the docs</a> except it has a Value* dereference type instead of Value&amp;.</p>
  
  <p>The problem is with using the iterators with std::find, it throws these compile errors for the find template.</p>
  
  <p><em>edit One</em></p>
  
  <p>Several noted that std::find would require a pointer value since the iterator_facade dereferences to a pointer. I had that thought too. The compile error produced in this case is</p>
  
  <p>Pass Pointer to find error:</p>
  
  <pre><code>it = find(begin, end, (n2));
  
  [100%] Building CXX object CMakeFiles/node_example.dir/main_example.cpp.o
  /usr/include/c++/4.2.1/bits/stl_algo.h: In function '_InputIterator std::find(_InputIterator, _InputIterator, const _Tp&amp;) [with _InputIterator = node_iter&lt;node&lt;int&gt; &gt;, _Tp = node&lt;int&gt;*]':
  /Users/jkyle/Projects/BoostIteratorExample/main_example.cpp:102:   instantiated from here
  /usr/include/c++/4.2.1/bits/stl_algo.h:327: error: no matching function for call to '__find(node_iter&lt;node&lt;int&gt; &gt;&amp;, node_iter&lt;node&lt;int&gt; &gt;&amp;, node&lt;int&gt;* const&amp;, boost::forward_traversal_tag)'
  make[2]: *** [CMakeFiles/node_example.dir/main_example.cpp.o] Error 1
  make[1]: *** [CMakeFiles/node_example.dir/all] Error 2
  </code></pre>
  
  <p><em>edit Two</em></p>
  
  <p>I should also note that I made my own find template that works, e.g.</p>
  
  <pre><code>template&lt;class ForwardIterator, class ValueType&gt;
  ForwardIterator find(ForwardIterator begin, ForwardIterator end, ValueType value)
  {
    while (begin != end)
    {
      if (*begin == value)
      {
        break;
      }
      ++begin;
    {
    return begin;
  }
  </code></pre>
  
  <p>Error Output:</p>
  
  <pre><code>[100%] Building CXX object CMakeFiles/node_example.dir/main_example.cpp.o
  /usr/include/c++/4.2.1/bits/stl_algo.h: In function '_InputIterator
  std::find(_InputIterator, _InputIterator, const _Tp&amp;) [with _InputIterator = 
  node_iter&lt;node&lt;int&gt; &gt;, _Tp = node&lt;int&gt;]':
  /Users/jkyle/Projects/BoostIteratorExample/main_example.cpp:102:instantiated from 
  here
  /usr/include/c++/4.2.1/bits/stl_algo.h:327: error: no matching function for 
  call to '__find(node_iter&lt;node&lt;int&gt; &gt;&amp;, node_iter&lt;node&lt;int&gt; &gt;&amp;, const node&lt;int&gt;&amp;, 
  boost::forward_traversal_tag)'
  make[2]: *** [CMakeFiles/node_example.dir/main_example.cpp.o] Error 1
  make[1]: *** [CMakeFiles/node_example.dir/all] Error 2
  make: *** [all] Error 2
  </code></pre>
  
  <p><em>edit Three</em></p>
  
  <p>There were some helpful answers that solve the immediate problem of iteration. However, my main concern is why my boost::iterator_facade is not behaving the same as what I'd expect from iterators for STL containers of pointers. Below is example code demonstrating the behavior I expect from an STL iterator for a container of pointers:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  #include &lt;cassert&gt;
  
  using namespace std;
  
  struct Foo
  {
    int bar;
  };
  
  int main ()
  {
    vector&lt;Foo *&gt; list;
    Foo *f1 = new Foo;
    f1-&gt;bar = 5;
    Foo *f2 = new Foo;
    f2-&gt;bar = 10;
    Foo *f3 = new Foo;
    f3-&gt;bar = 15;
  
    list.push_back(f1);
    list.push_back(f2);
    list.push_back(f3);
  
    // with the vector class, there is no need for comparator function for the iterator
    // to be properly dereferenced and compared
    vector&lt;Foo *&gt;::iterator it = find(list.begin(), list.end(), f2);
  
    assert(*it == f2);
    return 0;
  }
  </code></pre>
  
  <p>Example Source:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;boost/type_traits/is_convertible.hpp&gt;
  #include &lt;boost/utility/enable_if.hpp&gt;
  #include &lt;boost/iterator/iterator_facade.hpp&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  template &lt;class T&gt;
  struct node
  {
    node() : m_next(0) {}
  
    node(T *x)
      : m_value(x)
    {}
  
     // Each node manages all of its tail nodes
     ~node() { delete m_next; }
  
     // Access the rest of the list
     node* next() const { return m_next; }
  
     void append(node* p)
     {
         if (m_next)
             m_next-&gt;append(p);
         else
             m_next = p;
     }
  
  
    void print() const { cout &lt;&lt; *this-&gt;m_value &lt;&lt; endl; }
  
  private:
    T *m_value;
    node* m_next;
  
  };
  
  template &lt;class Value&gt;
  class node_iter
    : public boost::iterator_facade&lt;
          node_iter&lt;Value&gt;
        , Value
        , boost::forward_traversal_tag
        , Value*
      &gt;
  {
  private:
    struct enabler {};
  
  public:
    node_iter()
      : m_node(0) {}
  
    explicit node_iter(Value* p)
      : m_node(p) {}
  
    template &lt;class OtherValue&gt;
    node_iter(node_iter&lt;OtherValue&gt; const&amp; other, 
              typename boost::enable_if&lt;
                              boost::is_convertible&lt;OtherValue*,Value*&gt;, 
                              enabler&gt;::type = enabler() )
      : m_node(other.m_node) {}
  
  private:
    friend class boost::iterator_core_access;
    template &lt;class&gt; friend class node_iter;
  
    template &lt;class OtherValue&gt;
    bool equal(node_iter&lt;OtherValue&gt; const&amp; other) const
    {
        return this-&gt;m_node == other.m_node;
    }
  
    void increment()
    { m_node = m_node-&gt;next(); }
  
    Value* dereference() const
    { return m_node; }
  
    Value* m_node;
  };
  typedef node_iter&lt; node&lt;int&gt; &gt; node_iterator;
  typedef node_iter&lt; node&lt;int&gt; const &gt; node_const_iterator;
  
  
  int main ()
  {
    node&lt;int&gt; *n1 = new node&lt;int&gt;(new int(5)); 
    node&lt;int&gt; *n2 = new node&lt;int&gt;(new int(10));
    node&lt;int&gt; *n3 = new node&lt;int&gt;(new int(15));
  
    n1-&gt;append(n2);
    n2-&gt;append(n3);
  
    node_iterator it;
    node_iterator begin(n1);
    node_iterator end(0);
  
    it = find(begin, end, *n2);
  
    return 0;
  }
  </code></pre>