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

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

---

Edit: сопряженного список API, я упаковка не мои. Я не могу их изменить.

Answer 1

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

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

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

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

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

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

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

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

Таким образом, итератор обычно является другом (или вложенным классом) класса, к которому он предоставляет доступ. Он предоставляет остальной мир абстрактному интерфейсу, но сам итератор имеет непосредственное знание (и доступа) к внутренностям связанного списка (или любого другого контейнера), к которому он предоставляет доступ). Вот общее понятие:

// 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). Это предназначено только для иллюстрации общей структуры.

Answer 4

Из того, что вы сказали, у вас, вероятно, есть большой код устаревшего кода, который использует ваши struct SomeObject типы, но вы хотите хорошо играть с новым кодом и использовать контейнеры iterators/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 5

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

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

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

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

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

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

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