Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼


The C5 Generic Collection Library

Source Code Accompanies This Article. Download It Now.

Design Principles

For starters, we studied existing Java and Smalltalk collection libraries and drew up a list of design objectives:

  • The library should provide well-known collection abstractions such as lists, sets, bags (multisets), priority queues, double-ended queues, stacks, and dictionaries (finite maps).
  • The library should provide standard implementations of these, using data structures such as array lists, doubly linked lists, hash-based and comparer-based collections, and interval heaps.
  • Functionality should be orthogonal so that it can be freely combined.
  • The library should provide convenient but hard-to-implement functionality, such as persistent sorted collections and sublist views on hash-indexed linked lists.
  • The library should fit with existing C# concepts such as enumerables, the foreach statement, and events, and make good use of C# 2.0 features such as generic types and methods, the yield statement (iterator methods), nullable value types, and anonymous methods.
  • The functionality of a collection class should be completely characterized by the interfaces it implements. This permits "programming to interface, not to implementation." For instance, the classes ArrayList<T> and LinkedList<T> have the same functionality and implement the same interfaces.
  • Good asymptotic complexity is more important than nanosecond efficiency. Thus, existing operations on .NET's standard array list List<T> may be faster by a constant factor than operations on C5 ArrayList<T>, but other operations may simply be nonexistent, and therefore not efficiently implementable on List<T>.
  • The library should be tested and documented well enough to be widely usable. This includes documentation of the asymptotic running time of each operation on each collection implementation.

Figures 1 and 2 show the inheritance hierarchies of the collection types and dictionary types.

[Click image to view at full size]

Figure 1: The collection type hierarchy.

Figure 2: The dictionary type hierarchy.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.