FAQ Articles Links Personal

CircularList

 

Scope

Why would someone write a container ? Even if it provides an (obscure) feature, such as a Circular List does.

I wrote this article only for educational purposes. Nobody in his right mind should write a container from scratch when STL containers can be used instead, or at least rely on them in the implementation. However, there's plenty of people that write their own containers for various (false) reasons. Containers that are not exception safe, have a poor or over elaborate interface and cannot be used in conjunction with the STL algorithms.

This article is for anyone interested on how a STL container's guts might look like, how exception safety goes with containers and everything else you bump into while writing a container.

Introduction

A linked list is a container that stores its elements in linked nodes. The advantage of such a structure is fast middle insertions, fast begin-middle erase and fast reordering. The disadvantages are slow access to middle-end elements and extra memory usage.

Designing a Circular List

As the goal of the Circular List is to mimic a STL list, several design decisions have already been made:

The Circular List container must store a structure that contains the actual element to be stored and pointers to the next and previous such structure. The name for this structure is usually "Node". The Node's only responsibility is to manage the element it holds: the actual element we will store in the container.

As exception safety should never be an afterthought, there is an obvious need of a way to avoid memory leaks and container modifications in the presence of exceptions. Thus, we need a class that would acquire a node (that might be linked to other nodes) and free the memory used. I shall discuss this more in-depth later.

In order to maximize code reuse, and avoid having member functions with too many responsibilities, I decided to have an intermediary CLImpl (Circular List Implementation ) class that provides a small set of list operations. This class is not mandatory, but it helps making code simpler and even easier to explain.

Iterators are a harder issue here. An iterator for a Circular List could be incremented forever due to the very nature of this container. However, such iterators would be no good for some STL algorithms. They could be an infinite bag of hard to track bugs and would be counter-intuitive for many programmers. For instance, user-defined template functions that take a container as a template type and use it as a regular container would most probably cause terrible bugs.

The Circular List will provide two types of iterators: a regular iterator that iterates the container as if it were a plain list (not circular) and a circular_iterator which would iterate a Circular List properly. A circular_iterator will never be equal with CircularList::end(), thus you can always dereference this iterator. Conversions from iterator to circular_iterator will be done automatically. Converting it the other way should require it to be explicit in order to avoid passing circular_iterators by mistake to something requiring a regular iterator.

Implementing a Circular List: the Node class

The Node class will be responsible of managing the memory of the element it holds. The constraints it puts on the element are minimal:

These requirements are usually the requirements of any container. It should be able to construct an element, and destruction should not throw an exception for many good reasons.

template< typename T >

struct Node {

public:

Node( Node<T>* p, Node<T>* n, const T& v ); // the constructor for regular nodes

Node( Node<T>* p, Node<T>* n ); // the constructor for the end node

~Node();

Node<T>* prev;

Node<T>* next;

T* value;

private:

Node( const Node<T>& );

Node<T>& operator=( const Node<T>& );

};

Having the copy constructor and assignment operator private is not an easy design decision. Having them could save the trouble of copying nodes but, on the other hand, this could become troublesome as copying nodes to another Circular List requires changing the prev and next pointers as well, and this can be easily forgotten. Making them private and not defining them protects the user of class Node to make such errors, and makes it clear on how to copy nodes.

The implementation of the Node class is pretty basic. As mentioned in the comments, the two versions of the constructors are for creating regular and end nodes. The constructor that creates an end node initializes the T* value member with 0, making it a null pointer. This will be the marker for the end of the list. The destructor will free the memory held by value if necessary.

Implementing a Circular List: the NodeSentry class

As mentioned in Design, we need a way to avoid memory leaks and ensure strong exception safety where needed. For now, I shall concentrate on ensuring there are no memory leaks for now. What we need is a way of releasing the memory in in the linked nodes in case an exception is thrown. One way would be adding try..catch blocks wherever they're needed, such as:

void f() {

try {

Node<int>* node = new Node<int>(0, 0, 0);

node->next = new Node<int>(node, 0, 0);

// ... etc ...

}

catch(...) {

Node<int>* temp = node;

while( node ) {

node = node->next;

delete temp;

temp = node;

}

throw; // rethrow the exception

}

}

However, doing this in every function that needs to prevent leaking is tedious and prone to errors.

Another idea would be having a class that stores every Node pointer in a std::auto_ptr array. The destructor of this class would call each auto_ptr destructor in its array. The code would look like this:

void f() {

NoMoreMemoryLeaks< Node<T> > manager(2); // will manage two Nodes

Node<int>* node = new Node<int>(0, 0, 0);

manager.add( node );

node->next = new Node<int>(node, 0, 0);

manager.add( node->next );

// ... etc ...

} // the destructor of NoMoreMemoryLeaks will release all the memory held, even in the presence of exceptions

If an exception was thrown by the first node's creation, there would be no leak. If the second threw, the exception would cause the stack to unwind, and the destructor of the local variable manager will be called, thus freeing the memory held by the first node.

However, this is not a good idea because you not always know how many Node structures you will allocate. And, as you cannot use a STL container in conjunction with std::auto_ptr, changing the container of auto_ptr's from a plain array to a std::list is not an option.

We need a class that knows about Node's internals. Such a class would be, just like NoMoreMemoryLeaks a local variable destructed when stack unwinding is done, or at the function's exit point. Knowing Node's internals will allow it to delete all the nodes by only knowing the first Node by simply using the next member pointer.

template< typename T >

class NodeSentry {

public:

NodeSentry( Node<T>* p );

void release(); // sets the member ptr_ to 0

~NodeSentry();

private:

Node<T>* ptr_;

};

Here's how our function would look using NodeSentry:

void f() {

Node<int>* node = new Node<int>(0, 0, 0);

NodeSentry<int> sentry( node );

node->next = new Node<int>(node, 0, 0); // add ass many nodes as needed, as long as you add them using this way

}

The only requirement of NodeSentry is to link the new node as you create it, and not after. This is pretty reasonable though and quite natural too.

Implementing a Circular List: the CLImpl class

Except common container typedef's, the CLImpl class provides 4 constructors:

The CLImpl class also provides these common container operations:

It also does not encapsulate the member variables, as the only one using it will be the CircularList container. These members are:

Let's examine the most interesting functions inside CLImpl:

template< typename T > template< typename InputIterator >

CLImpl<T>::CLImpl( InputIterator first, InputIterator last ) : begin_( new Node<T>(0, 0) ), end_( begin_ ), size_( 0 ) {

NodeSentry<T> sentry( begin_ );

Node<T>* temp = begin_;

for(; first != last; ++first, ++size ) {

temp->next = new Node<T>( temp, 0, *first );

temp = temp->next;

}

begin_ = end_->next;

temp->next = end_;

end_->prev = temp;

sentry.release();

}

The idea is pretty simple. First, I create the end node, which will remain equal to the begin node in case first == last and store it in the NodeSentry instance. The for loop just creates a node for each iterator in the respective range. After that, the proper links are made the sentry is released from its duties as no exceptions was thrown. Note that if I wouldn't have done that, the sentry would have deleted all the allocated memory and the list would have been in an incoherent state (no end_ pointer, size_ wouldn't be as it should, etc).

The destructor is one of my favorites:

template< typename T >

CLImpl<T>::~CLImpl() {

NodeSentry<T> sentry( begin_ );

}

As I never call sentry.release(), the sentry's destructor will free all the memory starting from begin_, to the end_ node.

The insert and erase member functions are simple enough to be omitted from this article. The only thing you have to be careful about is avoid making any changes to your existing nodes until you create the new node in the case of insert because, even if that operation would throw, your container will not have changed any of its members, leaving it in a coherent state. The erase does not have this problem because if deleting the node would throw, you'd get far more problems than implementing this function.

Finally, the swap function is nothing more than calling std::swap (which doesn't throw) for each member in CLImpl.

Implementing a Circular List: the "normal" Iterator

I won't go in too much detail with this class, as it doesn't provide too much interest. Its interface, as expected provides:

In addition to that, it provides a private constructor which takes a Node<T> argument, used by the friend classes CLImpl and CircularList. In addition, the CircularIterator class is also a friend, for reasons that shall be discussed in the following section.

Implementing a Circular List: the Circular Iterator

The CircularIterator class has the same interface as the regular Iterator class. It does not provide the same private constructor nor does it have any friend classes. It does, however have a non-explicit constructor that takes a regular Iterator. This means you can pass a regular Iterator to a function that requires a CircularIterator and the compiler will automatically perform the conversion. The other way around isn't possible, but CircularIterator provides a way to manually convert it to a regular Iterator via a member function called toIterator().

What makes CircularIterator act properly is a differently implemented operator++ and operator-- that increment or decrement again if they pass by the end of the container. This is checked by a simple node_->value == 0 test.

Implementing a Circular List: the end

As the CLImpl helper class does most of the work, the functions here are usually under 3 lines of code. As there's no real interest in their implementations, I won't go any further with this. If you're interested, download the code and check it out.

Conclusion

The whole implementation of my CircularList container is a bit over 800 lines of code. It does not contain all the functions std::list does, namely:

Unlike STL containers, it does not use allocators. It definitely is a lot slower than std::list. The point of this article is to show you what exception safety means, how it can affect your design and, maybe just as important, convince you that using STL containers is almost always better than crafting your own.

 

You can download the code here.

 

References:

© Ciobanu Vladimir, 2004