在迭代器中包装链表

Question

我常用的一组 API 遵循链表模式：

struct SomeObject
{
    const char* some_value;
    const char* some_other_value;
    SomeObject* next;    
}

LONG GetObjectList( SomeObject** list );
void FreeObjectList( SomeObject* list );

这个 API 不是我的，我不能改变它。

所以，我想封装它们的构造/销毁、访问和添加迭代器支持。我的计划是做这样的事情：

/// encapsulate access to the SomeObject* type
class MyObject
{
public:
    MyObject() : object_( NULL ) { };
    MyObject( const SomeObject* object ) : object_( object ) { };
    const char* SomeValue() const 
    { 
        return NULL != object_ ? object_->some_value : NULL; 
    };
    const char* SomeValue() const 
    { 
        return NULL != object_ ? object_->some_other_value : NULL; 
    };

private:
    SomeObject* object_;
}; // class MyObject

bool operator==( const MyObject& i, const MyObject& j )
{
    return // some comparison algorithm.
};

/// provide iterator support to SomeObject*
class MyObjectIterator 
    : public boost::iterator_adaptor< MyObjectIterator, 
                                      MyObject*,
                                      boost::use_default,
                                      boost::forward_traversal_tag >
{
public:
    // MyObjectIterator() constructors

private:
    friend class boost::iterator_core_access;

    // How do I cleanly give the iterator access to the underlying SomeObject*
    // to access the `next` pointer without exposing that implementation detail
    // in `MyObject`?
    void increment() { ??? }; 
};

/// encapsulate the SomeObject* creation/destruction
class MyObjectList
{
public:
    typedef MyObjectIterator const_iterator;

    MyObjectList() : my_list_( MyObjectList::Create(), &::FreeObjectList )
    {
    };

    const_iterator begin() const
    {
        // How do I convert a `SomeObject` pointer to a `MyObject` reference?
        return MyObjectIterator( ??? );
    };

    const_iterator end() const
    {
        return MyObjectIterator();
    };

private:
    static SomeObject* Create()
    {
        SomeObject* list = NULL;
        GetObjectList( &list );
        return list;
    };

    boost::shared_ptr< void > my_list_;
}; // class MyObjectList

我的两个问题是：

1. 我如何干净地MyObjectIterator访问底层SomeObject以访问next链表中的指针，而不会在 中公开该实现细节MyObject？

2. 在 中MyObjectList::begin()，如何将SomeObject指针转换为MyObject引用？

谢谢，保罗

---

编辑：我包装的链表 API 不是我的。我无法改变它们。

Answer 1

首先，当然，为了实际使用，您几乎肯定不应该编写自己的链表或迭代器。其次，链表的良好用途（即使是已经编写、调试过的等等）也非常罕见——除了在一些非常不寻常的情况下，您可能应该使用其他东西（最常见的是向量）。

也就是说，迭代器通常是它提供访问权限的类的朋友（或嵌套类）。它为世界其他地方提供了一个抽象接口，但迭代器本身可以直接了解（和访问）链表（或它提供访问的任何容器）的内部结构。这是一个普遍的概念：

// warning: This is really pseudo code -- it hasn't been tested, and would 
// undoubtedly require a complete rewrite to even compile, not to mention work.
template <class T>
class linked_list { 

public:
    class iterator;

private:
    // A linked list is composed of nodes.
    // Each node has a value and a pointer to the next node:    
    class node { 
        T value;
        node *next;
        friend class iterator;
        friend class linked_list;
    public:
        node(T v, node *n=NULL) : value(v), next(n) {}
    };

public:

    // An iterator gives access to the linked list.
    // Operations: 
    //      increment: advance to next item in list
    //      dereference: access value at current position in list
    //      compare: see if one iterator equals another    
    class iterator { 
        node *pos;
    public:
        iterator(node *p=NULL) : pos(p) {}
        iterator operator++() { 
            assert(pos); 
            pos = pos->next; 
            return *this;
        }
        T operator*() { return pos->value; }
        bool operator!=(iterator other) { return pos != other.pos; }
    };

    iterator begin() { return iterator(head); }
    iterator end()   { return iterator(); }

    void push_front(T value) { 
        node *temp = new node(value, head); 
        head = temp;
    }

    linked_list() : head(NULL) {}

private:
    node *head;
};

要与标准库中的算法一起工作，您必须定义比这更多的定义（例如，像 value_type 和 reference_type 这样的类型定义）。这只是为了显示一般结构。