Using boost::iterator_facade<>

问题:

I have a linked list structure:

struct SomeLinkedList
{
    const char* bar;
    int lots_of_interesting_stuff_in_here;
    DWORD foo;
    SomeLinkedList* pNext;
};

It is part of an existing API and I cannot change it.

I would like to add iterator support. The boost::iterator_facade<> library seemed ideal for the purpose.

class SomeIterator
    : public boost::iterator_facade< SomeIterator, 
                                     const SomeLinkedList, 
                                     boost::forward_traversal_tag >
{
public:
    SomeIterator() : node_( NULL ) {};

    explicit SomeIterator( const SomeLinkedList* p ) : node_( p ) {};

private:
    friend class boost::iterator_core_access;

    void increment() { node_ = node_->pNext; };

    bool equal( SomeIterator const& other ) const { /*some comparison*/; };

    SomeLinkedList const& dereference() const { return *node_; };

    SomeLinkedList const* node_;
}; // class SomeIterator

The goal is to be able to use it in standard library functions like std::for_each

void DoSomething( const SomeLinkedList* node );

SomeLinkedList* my_list = CreateLinkedList();
std::for_each( SomeIterator( my_list ), SomeIterator(), DoSomething );

Unfortunately, I'm getting an error saying it's trying to pass the list by value rather than by pointer.

error C2664: 'void (const SomeLinkedList *)' : cannot convert parameter 1 from 'const SomeLinkedList' to 'const SomeLinkedList *'

How can I change SomeIterator to do to get this working correctly?

Thanks, PaulH

---

Edit: I've tried this:

class SomeIterator
    : public boost::iterator_facade< SomeIterator, 
                                     SomeLinkedList, 
                                     boost::forward_traversal_tag,
                                     SomeLinkedList* >
{
    // ...

but I get this complier error:

error C2664: 'boost::implicit_cast' : cannot convert parameter 1 from 'SomeLinkedList **' to 'boost::detail::operator_arrow_proxy<T>

---

Edit 2:

I've tried modifying the dereference type:

class SomeIterator
    : public boost::iterator_facade< SomeIterator, 
                                     const SomeLinkedList, 
                                     boost::forward_traversal_tag >
{
    // ...

    const SomeLinkedList* dereference() const { return node_; };

but, I get the original error:

error C2664: 'void (const SomeLinkedList *)' : cannot convert parameter 1 from 'const SomeLinkedList' to 'const SomeLinkedList *'

回答1:

When your iterator is dereferenced, it would return a const SomeLinkedList& however your DoSomething function is expecting a const SomeLinkedList*. Either alter the iterator to somehow return pointers when dereferenced or alter your DoSomething function.

---

EDIT in response to further discussion:

I haven't actually used boost::iterator_facade myself, but looking at additional code you posted it appears you might not have changed all the necessary parts at the same time.

Have you actually tried

class SomeIterator
    : public boost::iterator_facade< SomeIterator, 
                                     SomeLinkedList, 
                                     boost::forward_traversal_tag,
                                     SomeLinkedList* >
{

and

const SomeLinkedList* dereference() const { return node_; };

together?

Or if that doesn't work, then how about:

class SomeIterator
    : public boost::iterator_facade< SomeIterator, 
                                     SomeLinkedList*, 
                                     boost::forward_traversal_tag>
{

const SomeLinkedList* dereference() const { return node_; };

Alternatively, as davka suggested in a comment, what about solving the pointer vs reference issue by making a wrapper around DoSomething? Such as:

void DoSomethingWrapper( const SomeLinkedList& node )
{
    DoSomething(&node);
}

In fact, you could probably even keep the wrapper the same name as the function it wraps and just let overloading rules take care of when the pointer or reference version gets called.

回答2:

I have been trying to understand boost::iterator_facade. Searching for a simple example I found this (old) question and the single, accepted answer. I thought I would post the code I needed to get this example to work here, as the existing question and answer never really settle the issue.

In the first instance note that the 2nd parameter to for_each() is an end iterator. I found that a NULL iterator (not sure if this is the right terminology) as used in the original question code works well, but only if you finish off the the incomplete definition of .equal() as follows;

bool equal( SomeIterator const& other ) const { return node_ == other.node_; }

Apart from that simply changing the definition of the parameter of DoSomething() from ptr to reference, as mentioned in the accepted answer, is the key to getting this to compile and run. I've put some primitive test code below to illustrate.

void DoSomething( const SomeLinkedList& node )
{
    std::cout << "DoSomething " << node.foo << "\n";
}

int main()
{
    SomeLinkedList temp[5];
    memset(temp,0,sizeof(temp));
    temp[0].pNext = &temp[1];
    temp[1].pNext = &temp[2];
    temp[2].pNext = &temp[3];
    temp[3].pNext = &temp[4];
    temp[4].pNext = 0;
    temp[0].foo   = 0;
    temp[1].foo   = 1;
    temp[2].foo   = 2;
    temp[3].foo   = 3;
    temp[4].foo   = 4;
    SomeLinkedList* my_list = &temp[0];
    std::for_each( SomeIterator( my_list ), SomeIterator(), DoSomething );
    return 0;
}