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

Question

下面是链表节点的 iterator_facade 的实现。它与文档中介绍的几乎相同< /a> ，但它具有 Value* 取消引用类型而不是 Value&。

问题在于将迭代器与 std::find 一起使用，它会引发 find 模板的这些编译错误。

编辑一个

一些人指出 std::find 需要一个指针值，因为 iterator_facade 取消引用指针。我也有这样的想法。在这种情况下产生的编译错误是

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

我还应该注意，我制作了自己的有效查找模板，例如

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

有一些有用的答案可以解决迭代的直接问题。然而，我主要关心的是为什么我的 boost::iterator_facade 的行为与我期望的 STL 指针容器迭代器的行为不同。下面的示例代码演示了我期望 STL 迭代器对指针容器的行为：

#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;
}

示例来源：

#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

迭代器公开的 value_type 是一个指针 (Value*)。这意味着所有 STL（和一致的）算法在迭代时都会看到这些指针。我建议您将 find_if 与自定义谓词对象一起使用：

#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));

其中谓词 (cmp_ind_impl) 为您提供正确的间接工作。辅助函数（cmp_ind）并不是真正必要的，只是简化了该谓词的构造（即不需要用户使用模板魔法）。

Answer 2

除非它具有 Value* 取消引用类型

std::find 不知道在查找该项目时取消引用您的指针。您的迭代器必须返回一个引用，或者您需要传递一个指针作为您在 find 中查找的项目。

Answer 3

*begin 返回一个 node*，您要求 find 与 node 进行比较。尝试传递 n2 来查找：

it = find(begin, end, n2);

Answer 4

目前，您使 std::find() 比较 2 个 node。一种可能的解决方案是添加
bool operator==(nodex) {return (this->m_value==x.m_value);} 到您的节点类模板。