Deque

One of the coolest data structures in the standard C++ library is the "deque". It keeps items close together like an array, which improves cache efficiency and like a linked list, it doesn’t need to perform a copy of all its items when it is enlarged beyond its current capacity. Despite this, it can be accessed by index like an array. It also supports fast removal or insertion of items both at the beginning and at the end of it and is thus usable as a stack or a queue.

Sadly, the deque data structure is missing in the .NET collection classes.

I discovered some deque implementations on the web, but those all seemed to be simple wrappers around .NET’s LinkedList<> class and not actual implementations of the deque data structure. So I decided to amend this situation:

Usage isn’t much different from a List<T> – here are some snippets:

Deque<string> strings = new Deque<string>();

// Adding to the end of a deque is fast. Even if the deque's block size is
// exceeded, unlike a List<> it doesn't need to copy its contents, so even
// in this case the spike is manageable.
for(int index = 0; index < 1024; ++index) {
  strings.AddLast("World");
}

// Adding to the beginning of a deque is also fast. The items do not have to
// be copied around in memory.
for(int index = 0; index < 1024; ++index) {
  strings.AddFirst("Hello");
}

// The deque can be very efficiently processed from one end to the other
while(strings.Count > 0) {
  Console.Write(strings.First);
  strings.RemoveFirst();
}

The deque is slightly slower than a List<> at some operations (accessing items by index, adding items with enough capacity remaining, removing items close to the middle) but eliminates most of the weak points of the List<> compared to the LinkedList<> class.

Features

• Fully implements the IList<> and IList interfaces
• Unit-tested code with 100% test coverage
• Efficient implementation and lightning-fast enumerators

Benchmarks

Update: I’ve written some benchmarks that test my Deque versus .NET’s List<> and LinkedList<> classes. Here are the results (each measured with 250,000 items)

AddLast()

This is one operation all of the data structures can do easily:

AddFirst()

This is one requires the List<T> to shift its whole contents but can be done natively by the Deque<T> and LinkedList<T>:

AddRandom()

This one is tricky: it inserts new items at random places. The List<T> needs to shift all contents after the insertion point. The Deque<T> will shift either the contents before the insertion point or after the insertion point (depending on which involves fewer items). The LinkedList<T> doesn’t need to shift at all, but reaching the index is tricky – my benchmark checks whether it’s shorter to follow links from the beginning of the list, from the end of the list or from a point where the last insertion took place.

The Deque class is part of the Nuclex.Support library from the Nuclex Framework. You can find the most recent release of the code on the framework’s CodePlex site: http://nuclexframework.codeplex.com/