Обтекание связанных списков в итераторах

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?

Спасибо, PaulH

---

Редактировать: 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;
};

Чтобы работать вместе с алгоритмами в стандартной библиотеке, вы должны определить немного больше, чем пыталось это сделать (например, typedefs, такие как value_type и reference_type). Это только для того, чтобы показать общую структуру.

Answer 2

Мой совет: удалите это и используйте существующую реализацию slist<>.IIRC, он будет в C ++ 1x, поэтому ваш компилятор (ы) может уже поддерживать его.Или это может быть в boost .Или возьми это из другого места.

Где бы вы ни получили, у вас есть все эти проблемы уже решены , вероятно очень хорошо проверено , следовательно без ошибок и быстро , и код, использующий его, легко распознаваем (глядя на это, многие из нас сразу увидят, что он делает, потому что он уже какое-то время существует и станет частью следующего стандарта).

В последний раз, когда я писал свой собственный список классов, до того, как STL стал частью стандартной библиотеки C ++.

Хорошо, так как вы застряли с имеющимся у вас API, вотчто-то, что могло бы помочь вам начать:

class MyObjectList
{
public:
    typedef SomeObject value_type;
    // more typedefs

    class iterator {
    public:
        typedef SomeObject value_type;
        // more typedefs

        iterator(SomeObject* pObj = NULL)
                                    : pObj_(pObj) {}
        iterator& operator++()        {if(pObj_)pObj_ = pObj_->next;}
        iterator  operator++(int)     {iterator tmp(*this);
                                      operator++();
                                      return tmp;}
        bool operator==(const iterator& rhs) const
                                      {return pObj_ == rhs.pObj_;}
        bool operator!=(const iterator& rhs) const
                                      {return !operator==(rhs);}
              value_type& operator*() {return pObj_;}
    private:
        SomeObject* pObj_;
    };

    class const_iterator {
    public:
        typedef SomeObject value_type;
        // more typedefs
        const_iterator(const SomeObject* pObj = NULL)
                                    : pObj_(pObj) {}
        iterator& operator++()        {if(pObj_)pObj_ = pObj_->next;}
        iterator  operator++(int)     {iterator tmp(*this);
                                      operator++();
                                      return tmp;}
        bool operator==(const iterator& rhs) const
                                      {return pObj_ == rhs.pObj_;}
        bool operator!=(const iterator& rhs) const
                                      {return !operator==(rhs);}
        const value_type& operator*() {return pObj_;}
    private:
        const SomeObject* pObj_;
    };

    MyObjectList()                   : list_() {GetObjectList(&list_;);}
    ~MyObjectList()                    {FreeObjectList(list_);}
          iterator begin()             {return list_ ?       iterator(list_)
                                                     :       iterator();}
    const_iterator begin() const       {return list_ ? const_iterator(list_)
                                                     : const_iterator();}
          iterator end  ()             {return       iterator(getEnd_());}
    const_iterator end  () const       {return const_iterator(getEnd_());}

private:
    SomeObject* list_;

    SomeObject* getEnd_()
    {
        SomeObject* end = list_;
        if(list_)
            while(end->next)
                end = end->next;
        return end;
    }
};

Очевидно, что это еще не все (например, я считаю, что константные и неконстантные итераторы тоже должны быть сопоставимы), но добавить их не сложнок этому.

Answer 3

Из того, что вы сказали, вы, вероятно, имеете БОЛЬШОЙ унаследованный код, использующий ваши типы struct SomeObject, но вы хотите хорошо поиграть с новым кодом и использовать контейнеры итераторов / stl.

Если это так, вы будетеВы не сможете (простым способом) использовать ваш новый созданный итератор во всей существующей кодовой базе, поскольку это изменит много кода, но вы можете написать шаблонный итератор, который, если ваш structs будет следовать тем жебудет работать шаблон с полем next.

Примерно так (я не проверял и не компилировал его, это всего лишь идея):

Предположим, у вас есть структура:

struct SomeObject
{
    SomeObject* next;
}

Вы сможете создать что-то вроде этого:

template <class T>
class MyIterator {
public:
//implement the iterator abusing the fact that T will have a `next` field, and it is accessible, since it's a struct
};

template <class T>
MyIterator<T> createIterator(T* object) {
   MyIterator<T> it(object);
   return it;
}

Если вы правильно реализуете свой итератор, вы сможете использовать все алгоритмы STL со своими старыми структурами.

PS .: Если вы находитесь в сценарии некоего устаревшего кода с такого рода структурами, я тоже так делаю, и я реализовал этот обходной путь.Отлично работает.

Answer 4

До сих пор я видел несколько очень хороших ответов, но боюсь, что они могут быть "голыми".

Прежде чем ослепительно зарядиться, давайте рассмотрим требования.

• Как вы заметили, структура похожа на односвязный список, стандарт C ++ 0x определяет такую ​​структуру, которая называется forward_list. Прочитайте его интерфейс, ваш должен приблизиться.
• Типом итератора будет ForwardIterator.

Я хотел бы раскрыть один очень раздражающий факт: кто отвечает за память?

Я обеспокоен тем, что в предоставленном вами интерфейсе нет copy, поэтому мы должны отключить конструктор копирования и оператор присваивания нашего нового класса списка?

Реализация проста, на этой странице достаточно, даже если iterator не реализует должным образом черты итератора в целом, но я бы решил полностью отказаться от этой идеи и перейти к более совершенной схеме:

• class MyObject { public: ... private: SomeObject mData; };
• Завершение GetObjectList и возвращение deque<MyObject>, я думаю, LONG возвращает количество элементов?

Answer 5

1. Вы бы сделали MyObjectIterator другом MyObject.Я не вижу лучшего способа.И действительно, я думаю, что итераторы получают разумный доступ к друзьям, необходимый им для выполнения своих обязанностей.

2. Похоже, вы не рассматривали, как и где ваш экземпляр MyObjectбудут храниться.Или, возможно, это то, из-за чего возникает этот вопрос.Кажется, у вас должен быть отдельный связанный список MyObjects в вашем MyObjectList.Тогда, по крайней мере, MyObjectList::begin() может просто получить первый MyObject из вашего внутреннего связанного списка из них.И если единственные операции, которые могут изменять или переупорядочивать этот список, когда-либо выполняются только через предоставленные вами итераторы, то вы можете без проблем синхронизировать эти списки без особых проблем.В противном случае, если в используемом вами API есть функции, которые берут необработанный связанный список SomeObject и манипулируют им, у вас могут возникнуть проблемы.

Я понимаю, почему вы 'мы пытались спроектировать эту схему, но наличие отдельных объектов MyObject, которые указывают на SomeObject, даже через сами объекты SomeObject, составляют реальную структуру списка .... Это не простой способ обернуть список.

Самая простая альтернативапросто чтобы покончить с MyObject полностью.Позвольте вашим итераторам работать непосредственно с экземплярами SomeObject и возвращать их при разыменовании.Конечно, это делает SomeObject открытым, особенно его элемент next.Но действительно ли это достаточно большая проблема, чтобы оправдать более сложную схему, чтобы обернуть все это?

Другим способом решения проблемы может быть MyObject частное наследование от SomeObject.Затем каждый экземпляр SomeObject может быть передан как ссылка на экземпляр MyObject и таким образом передан внешнему миру, скрывая, таким образом, детали реализации SomeObject и выставляя только нужные публичные функции-члены.Стандарт, вероятно, не гарантирует, что это сработает, но на практике, поскольку они, скорее всего, будут иметь точно такие же схемы памяти, что вы сможете избежать этого.Тем не менее, я не уверен, что я когда-либо попробовал бы такое в реальной программе, если бы в этом не было крайней необходимости.

Последняя альтернатива, которую я могу придумать, - это просто перенести данные в список более удобных данных.структуры после того, как вам дал этот API.И затем, конечно, перенести его обратно в необработанный список SomeObject, только если необходимо передать его обратно в API.Просто сделайте свой собственный SomeObjectData или что-то еще, чтобы сохранить строки и поместите их в std::list.Насколько это возможно для вас, зависит от того, как эти данные используются в контексте упомянутого вами API.Если есть другие функции API, которые изменяют списки SomeObject, и вам нужно часто их использовать, то постоянное преобразование списков SomeObject в std::list<SomeObjectData> и обратно может быть раздражающим.