boost::iterator_facade and std::find(...)

Question

Below is an implementation of an iterator_facade for a linked list node. It's pretty much the same as that presented in the docs except it has a Value* dereference type instead of Value&.

The problem is with using the iterators with std::find, it throws these compile errors for the find template.

edit One

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

Pass Pointer to find error:

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&) [with _InputIterator = node_iter<node<int> >, _Tp = node<int>*]':
/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<node<int> >&, node_iter<node<int> >&, node<int>* const&, 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

edit Two

I should also note that I made my own find template that works, e.g.

template<class ForwardIterator, class ValueType>
ForwardIterator find(ForwardIterator begin, ForwardIterator end, ValueType value)
{
  while (begin != end)
  {
    if (*begin == value)
    {
      break;
    }
    ++begin;
  {
  return begin;
}

Error Output:

[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&) [with _InputIterator = 
node_iter<node<int> >, _Tp = node<int>]':
/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<node<int> >&, node_iter<node<int> >&, const node<int>&, 
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

edit Three

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:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

struct Foo
{
  int bar;
};

int main ()
{
  vector<Foo *> list;
  Foo *f1 = new Foo;
  f1->bar = 5;
  Foo *f2 = new Foo;
  f2->bar = 10;
  Foo *f3 = new Foo;
  f3->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<Foo *>::iterator it = find(list.begin(), list.end(), f2);

  assert(*it == f2);
  return 0;
}

Example Source:

#include <iostream>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <algorithm>

using namespace std;

template <class T>
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->append(p);
       else
           m_next = p;
   }


  void print() const { cout << *this->m_value << endl; }

private:
  T *m_value;
  node* m_next;

};

template <class Value>
class node_iter
  : public boost::iterator_facade<
        node_iter<Value>
      , Value
      , boost::forward_traversal_tag
      , Value*
    >
{
private:
  struct enabler {};

public:
  node_iter()
    : m_node(0) {}

  explicit node_iter(Value* p)
    : m_node(p) {}

  template <class OtherValue>
  node_iter(node_iter<OtherValue> const& other, 
            typename boost::enable_if<
                            boost::is_convertible<OtherValue*,Value*>, 
                            enabler>::type = enabler() )
    : m_node(other.m_node) {}

private:
  friend class boost::iterator_core_access;
  template <class> friend class node_iter;

  template <class OtherValue>
  bool equal(node_iter<OtherValue> const& other) const
  {
      return this->m_node == other.m_node;
  }

  void increment()
  { m_node = m_node->next(); }

  Value* dereference() const
  { return m_node; }

  Value* m_node;
};
typedef node_iter< node<int> > node_iterator;
typedef node_iter< node<int> const > node_const_iterator;


int main ()
{
  node<int> *n1 = new node<int>(new int(5)); 
  node<int> *n2 = new node<int>(new int(10));
  node<int> *n3 = new node<int>(new int(15));

  n1->append(n2);
  n2->append(n3);

  node_iterator it;
  node_iterator begin(n1);
  node_iterator end(0);

  it = find(begin, end, *n2);

  return 0;
}

Answer 1

except it has a Value* dereference type

std::find does not know to dereference your pointer when it's looking for that item. Your iterator must either return a reference, or you need to pass a pointer in as the item you're looking for in find.

Answer 2

*begin returns a node<int>* which you are asking find to compare to a node<int>. Try passing n2 to find:

it = find(begin, end, n2);

Answer 3

currently you make std::find() compare 2 node<T>'s. One possible solution would add bool operator==(node<T> x) {return (this->m_value==x.m_value);} to your node class template.

Answer 4

The value_type exposed by your iterator is a pointer (Value*). That means all STL (and conformant) algorithms will see those pointers while iterating. I suggest you use find_if with a custom predicate object:

#include <functional>
#include <algorithm>

template <typename Value>
struct cmp_ind_impl : std::unary_function <Value*, bool>
{
    cmp_ind(Value* n) : n_(n) {}

    bool operator<(Value* n) const
    {
        return *n == *n_;
    }

    Value* n_;
};

template <typename Value>
cmp_ind_impl cmp_ind(Value* n)
{
    return cmp_ind_impl<Value>(n);
}

std::find_if(begin, end, cmp_ind(n2));

where the predicate (cmp_ind_impl) does the proper indirection work for you. The helper function (cmp_ind) is not really necessary but just simplifies the construction of that predicate (i.e. no template wizardry is required from the user).