Combining lists in iterators

Question

The set of APIs that I usually use matches the linked list template:

struct SomeObject { const char* some_value; const char* some_other_value; SomeObject* next; } LONG GetObjectList( SomeObject** list ); void FreeObjectList( SomeObject* list ); 

This API is not mine, and I cannot change it.

So, I would like to encapsulate their construction / destruction, access and add support for iterator. My plan is to do something like this:

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

My two questions are:

• How can I give MyObjectIterator access to the underlying SomeObject to access the next pointer in a linked list without revealing this implementation detail in MyObject ?

• In MyObjectList::begin() , how do I convert a SomeObject pointer to a MyObject link?

Thanks PaulH

---

Edit: The linked list APIs that I wrap are not mine. I can’t change them.

Answer 1

• You would make MyObjectIterator friend of MyObject . I do not see a better way. Indeed, I find it reasonable that iterators gain access to a special friend to carry out their duties.

• It seems you have not considered how and where your instance of MyObject will be stored. Or perhaps this is what comes out of this question. It looks like you will have to have a separate linked list of MyObjects in MyObjectList. Then at least MyObjectList::begin() can just grab the first MyObject your internal linked list of them. And if only operations that can modify or reorder this list occur only through the iterators that you provide, then you can not make these lists synchronize without any problems. Otherwise, if the API you are using has functions that take and manipulate the linked raw SomeObject list, you may have problems.

I can understand why you tried to design this scheme, but the presence of separate MyObject objects that point to SomeObjects, even through SomeObjects, make up the real structure of the list ... This is not an easy way to wrap the list.

The easiest alternative is to completely get rid of MyObject. Let your iterators work with SomeObject instances directly and return them when dereferencing. Sure that exposes SomeObject outside, especially its next member. But is this really a big enough problem to justify a more complex scheme to wrap it all up?

Another way to handle this might be to have MyObject privately inherit from SomeObject . Then, each instance of SomeObject can be disabled as a reference to an instance of MyObject and transmitted to the outside world in this way, thus hiding the details of the implementation of SomeObject and revealing only the necessary functions of public members. The standard probably does not guarantee that this will work, but in practice, since they will likely have the same memory layouts, you can handle it. However, I'm not sure that in fact I will ever try such a thing in a real program, unless absolutely necessary.

The last alternative that I can think of is to simply pass the data to a list of more convenient data structures after providing you with this API. And then, of course, transfer it back to the SomeObject source list only if you need to pass it back to the API. Just create your own SomeObjectData or whatever to save the lines and put them in std::list . Regardless of whether this is real for you, it really depends on how this data is used in the context of the API you mentioned. If there are other API functions that modify SomeObject lists, and you need to use them often, then constantly converting SomeObject lists to and from std::list<SomeObjectData> can be annoying.

Answer 2

First, of course, for real use, you almost certainly should not write your own linked list or iterator at all. Secondly, good links to linked lists (even those that have already been written, debugged, etc.) are also quite rare - with the exception of a few rather unusual circumstances, you should probably use something else (most often a vector) .

However, an iterator is usually a friend (or a nested class) of the class to which it provides access. It provides the rest of the world with an abstract interface, but the iterator itself has direct knowledge (and access) to the interiors of a linked list (or any other container) that it provides access to). Here's a general concept:

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

To work with the algorithms in the standard library, you need to define a little more than it tried (e.g. typedefs, e.g. value_type and reference_type). This is intended only to illustrate the general structure.

Answer 3

My advice: Remove this and use the existing implementation of slist<> . IIRC, it will be in C ++ 1x, so your compiler can already support it. Or it could be in boost . Or take it from somewhere else.

Wherever you are, you have all these problems already resolved , probably very well tested , therefore without errors and quickly , and the code using it is easily recognizable (looking at this, many of us would immediately see what it does , because it has been a while, and it will be part of the next standard).

The last time I wrote my own list class was before STL became part of the C ++ standard library.

Well, since you are stuck in the API you have, here is something that might interest you:

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

Obviously, there is more to this (for example, I believe that the iterators const and non-const should also be comparable), but this is not difficult to add to this.

Answer 4

From what you said, you probably have a BIG old code using struct SomeObject types, but you want to play well with the new code and use the iterators / stl containers.

If this happens, you cannot (in a simple way) use your newly created iterator in the entire database of obsolete codes, as this will change a lot of code, but you can write a template iterator that if your structs follows one template, having the next field will work.

Something like this (I have not tested and compiled it, this is just an idea):

Suppose you have your structure:

 struct SomeObject { SomeObject* next; } 

You can create something like this:

 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 a struct }; template <class T> MyIterator<T> createIterator(T* object) { MyIterator<T> it(object); return it; } 

If you implement your iterator correctly, you can use all STL algorithms with your old structures.

PS: If you have a script of some inherited code with such structures, I do it too, and I applied this workaround. It works great.

Answer 5

I have seen very good answers so far, but I am afraid that they might be “naked”.

Before dazzling to charge, consider the requirements.

• As you noticed, the structure is similar to a singly linked list, the C ++ 0x standard defines such a structure called forward_list . Read your interface, yours should come close.
• The type of iterator will be ForwardIterator.

I would like to expose one very unpleasant fact: who is responsible for memory?

I'm worried because the interface you provided does not have a copy object, so should we disable the copy constructor and assignment operator of our new list class?

The implementation is simple, enough on this page, even if the iterator does not correctly implement the features of the iterator in general, but I would think about completely discarding this idea and moving on to a better scheme:

• class MyObject { public: ... private: SomeObject mData; };
• Ending GetObjectList and returning deque<MyObject> , I think LONG returns the number of elements?