c++ - 在迭代器中包装链表

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 引用？

谢谢，保罗H

---

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

Answer 1

当然，首先，对于实际使用，您几乎肯定根本不应该编写自己的链表或迭代器。其次，链表的良好用途(即使是已经编写、调试等的链表)也很少见——除了在一些相当不寻常的情况下，您可能应该使用其他东西(最常见的是 vector )。

也就是说，迭代器通常是它提供访问权限的类的友元(或嵌套类)。它为世界的其他部分提供了一个抽象接口(interface)，但迭代器本身直接了解(和访问)它提供访问的链表(或任何容器)的内部结构)。这是一个一般概念:

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

要与标准库中的算法一起工作，您必须定义比这试图定义的更多的东西(例如，typedef，如 value_type 和 reference_type)。这只是为了展示一般结构。