# ReadMe for Collection Templates 1.5.0

Program: | Collection Templates for CodeSmith
Version: | 1.5.0
Released: | 1 March 2004
Author: | Christoph Nahr
Contact: | christoph.nahr@kynosarges.de
Website: | http://www.kynosarges.de

### Breaking Changes

This Collection Templates release requires CodeSmith version 2.5 (build 2.5.10 or later).

Version 1.4.0: The IncludeNamespaces property must be set to `false` when rendering multiple template instances to the same output file. All required namespaces must be declared manually in the CodeSmith custom tool or in your property XML file.

Version 1.3.0: The new IncludeInterfaces property (for all templates except IList.cst) defaults to `true` but must be set to `false` in order to reproduce the behavior of previous versions.

## Table of Contents

1. Introduction
2. Overview
3. Tutorial
4. Template Files
5. Performance
6. Version History
7. Known Issues

## 1. Introduction

The Collection Templates are a set of files that can be used with CodeSmith, a template-based .NET code generator by Eric J. Smith, to create a variety of strongly typed C# collections. CodeSmith currently requires a Microsoft Windows system with the Microsoft .NET Framework 1.1 installed. Please refer to the CodeSmith website for further details.

The collection template files and this ReadMe file are copyright © 2003–2004 by Christoph Nahr. However, some templates are based on preceding work by Chris Sells who wrote the CollectionGen package that was incorporated into version 2.0 of CodeSmith by Eric J. Smith. You may freely use, change, and redistribute any or all of the files that constitute the original distribution, but please document any changes and include credits to the persons listed above.

## 2. Overview

The directory to which the archive was unpacked contains the following C# template files:

- ArrayList.cst – strongly typed reimplementation of ArrayList with absolutely no type casting.
- DictionaryList.cst – strongly typed implementation of DictionaryList (my invention) with absolutely no type casting.
- Hashtable.cst – strongly typed wrapper around Hashtable, unfortunately with lots of internal type casting.
- IDictionary.cst – dictionary interfaces and pair structure required for DictionaryList, Hashtable, and SortedList.
- IList.cst – collection interfaces required for ArrayList, Queue, Stack, and IDictionary (and hence for the remaining collections).
- Queue.cst – strongly typed reimplementation of Queue with absolutely no type casting.
- SortedList.cst – strongly typed reimplementation of SortedList with absolutely no type casting.
- Stack.cst – strongly typed reimplementation of Stack with absolutely no type casting.

The template files do not necessarily offer the complete functionality of the corresponding standard library classes. Some of the more obscure methods and overloads may be missing. Contact me if you require such a feature, and I’ll see if I can implement it in a future version.

### Classes and Interfaces

Each template file provided by this package is either a class template or an interface template. The interface templates define strongly typed collection interfaces that are shared between all classes that use the same element type in some fashion. For instance, if an ArrayList and a hashtable’s Keys collection have the same element type, they will also implement the same strongly typed ICollection.

The following table shows the interfaces on which each class template relies:

- ArrayList.cst, Queue.cst, and Stack.cst – require one IList.cst for the same item type.
- DictionaryList.cst, Hashtable.cst, and SortedList.cst – require one IDictionary.cst for the same key type and item type.
- IDictionary.cst – requires one IList.cst for the key type and another IList.cst for the item type.

Note that the interface template IDictionary.cst itself requires two other interface instantiations. The Template Files section covers the requirements in more detail.

To simplify the creation of collections that don’t share element types with other collections, all required interfaces are automatically generated along with the collection class by default, and placed in the same output file.

However, this default behavior will lead to name clashes as soon as another collection class is generated that uses the same element type in some fashion. One solution would be to put the generated classes in different target namespaces but this may be undesirable, and would also prevent the sharing of strongly typed interfaces.

Instead, the optional property IncludeInterfaces (see Common Properties) should be set to `false` for all collection classes that require an interface which has already been generated for another collection class. Alternatively, you could set this property to `false` for all collection classes, and manually generate the required interfaces.

## 3. Tutorial

The following sections describe the template files in detail, but we’ll start out with a quick tutorial that shows how to generate strongly typed collection classes. The tutorial assumes that all properties that are not explicitly mentioned have default values.

### 3.1 Create a strongly typed ArrayList for a reference type T

Instantiate ArrayList.cst with an ItemType of T. The following types are generated:

- The interfaces ITCollection, ITList, and ITEnumerator, all via IList.cst.
- The collection class TCollection which is the strongly typed ArrayList.

You can set the TargetNamespace property as desired to define the namespace in which the generated class and interfaces will reside. Should you choose to manually instantiate IList.cst, you must use the same TargetNamespace for both templates.

The name of the generated collection class can be changed using the ClassName property but I generally avoid doing this. The names of the generated interfaces cannot be changed regardless.

Example. Creating a strongly typed ArrayList of Button objects would generate the interfaces IButtonCollection, IButtonList, and IButtonEnumerator, and finally the collection class ButtonCollection. ButtonCollection implements IButtonCollection and IButtonList, and its GetEnumerator method returns an IButtonEnumerator. The generic version of all interfaces is also supported.

### 3.2 Create a strongly typed ArrayList for a value type T

Instantiate ArrayList.cst with an ItemType of T and set ItemValueType to `true`. The following types are generated:

- The interfaces ITCollection, ITList, and ITEnumerator, all via IList.cst.
- The collection class TCollection which is the strongly typed ArrayList.

Collection elements are treated as reference types by default. Setting the ItemValueType property to `true` slightly changes the generated code (and XML documentation) to accomodate the unique semantics of value types.

### 3.3 Create a strongly typed Hashtable for keys of type K and values of type V

Instantiate Hashtable.cst with a KeyType of K and an ItemType of V. The following types are generated:

- The interfaces IKCollection, IKList, and IKEnumerator, all via IList.cst.
- The interfaces IVCollection, IVList, and IVEnumerator, all via IList.cst.
- The interfaces IK VCollection, IK VDictionary, IK VList, and IK VEnumerator, as well as the strongly typed DictionaryEntry structure K VEntry, all via IDictionary.cst.
- The collection class K VDictionary which is the strongly typed Hashtable.

Set KeyValueType to `true` if K is a value type, and set ItemValueType to `true` if V is a value type.

Should you choose to manually instantiate IList.cst and IDictionary.cst, you must either use the same TargetNamespace for all templates, or you could target different namespaces with each IList.cst instance. In the latter case, you must (arbitrarily) adopt one namespace as the TargetNamespace for IDictionary.cst and Hashtable.cst, and use the ImportNamespace property of these two templates to import the other namespace.

Example. Creating a strongly typed Hashtable that maps String objects to Button objects would generate the following types:

- IStringCollection, IStringList, IStringEnumerator
- IButtonCollection, IButtonList, IButtonEnumerator
- IStringButtonCollection, IStringButtonDictionary, IStringButtonList, IStringButtonEnumerator, StringButtonEntry
- StringButtonDictionary

StringButtonDictionary implements IStringButtonCollection and IStringButtonDictionary; its elements are StringButtonEntry structures; its GetEnumerator method returns an IStringButtonEnumerator; its Keys list implements IStringCollection and IStringList and provides an IStringEnumerator; and its Values list implements IButtonCollection and IButtonList and provides an IButtonEnumerator. The generic version of all interfaces is also supported.

### 3.4 Create a strongly typed SortedList for keys of type K and values of type V, and a strongly typed ArrayList for elements of type K

Here we want to share strongly typed interfaces between classes, so we must take care to generate the shared interfaces only once. First, instantiate SortedList.cst with a KeyType of K and an ItemType of V. The following types are generated:

- The interfaces IKCollection, IKList, and IKEnumerator, all via IList.cst.
- The interfaces IVCollection, IVList, and IVEnumerator, all via IList.cst.
- The interfaces IK VCollection, IK VDictionary, IK VList, and IK VEnumerator, as well as the strongly typed DictionaryEntry structure K VEntry, all via IDictionary.cst.
- The collection class K VDictionary which is the strongly typed SortedList.

Now that we already have the IList.cst instance required for the strongly typed ArrayList, we must instantiate ArrayList.cst with an ItemType of K and an IncludeInterfaces property of `false`. Only a single type is generated:

- The collection class KCollection which is the strongly typed ArrayList.

This ArrayList implements the same strongly typed interfaces as the Keys collection of the SortedList, so either collection could be accessed as an IKCollection or an IKList. Likewise, another strongly typed ArrayList could be created for type V.

## 4. Template Files

This section provides reference information for all template files, and is divided into the following subsections:

1. Common Properties
2. ArrayList.cst
3. DictionaryList.cst
4. Hashtable.cst
5. IDictionary.cst
6. IList.cst
7. Queue.cst
8. SortedList.cst
9. Stack.cst

### 4.1 Common Properties

The following properties are available in all template files, except as noted, and always have the same effect.

Accessibility – an enumeration with the possible values Public, Protected, Internal, Protected Internal, and Private. The default is Public. This property determines the visibility of all types defined by a template file, except for private helper classes.

IncludeInterfaces (not with IList.cst) – an optional Boolean value that defaults to `true`. If set to `true`, the template file will generate all required interfaces; otherwise, they will be suppressed. In that case you must either manually generate the required interfaces, or have them generated automatically by another template.

IncludeNamespaces – an optional Boolean value that defaults to `true`. If set to `true`, the template file will generate all required `using` and `namespace` statements; otherwise, they will be suppressed. In that case you must ensure that the required statements are generated by other means. Specify the required namespaces in the CodeSmith custom tool, or add <import> elements to your property XML file. – Note: This property must be set to `false` when rendering multiple template instances to the same output file.

ItemNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which ItemType resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

ItemValueType – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that ItemType is a value type; otherwise, ItemType is assumed to be a reference type.

KeyNamespace (only with dictionary templates) – an optional string that defaults to a null reference. If provided, this property determines the namespace in which KeyType resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

KeyValueType (only with dictionary templates) – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that KeyType is a value type; otherwise, KeyType is assumed to be a reference type.

TargetNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which all types defined by a template file should reside. This namespace will be declared by a `namespace` statement if IncludeNamespaces is `true`.

#### Common Class Properties

The following properties are available in all template files that define collection classes, except as noted, and always have the same effect. These properties are not available in template files that define interfaces.

As of version 1.5.0, all class templates provide an optional Copy method to create a deep copy of the collection. This non-standard feature complements the standard Clone method which creates a shallow copy. – Note: The keys of dictionary collections are always duplicated as a shallow copy, even by the Copy method.

DeepCopy – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that a Copy method for deep copies should be generated.

DeepCopyItem – an optional string that defaults to “Clone”. This property determines the name of the ItemType method that creates a deep copy of a single collection element (or of its Value part for dictionary collections).

KeyCustomSearch (only with dictionary templates) – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that KeyType searches should be handled by custom routines instead of System.Array methods. Please refer to Performance for details. – Note: This property is available in Hashtable.cst for consistency but has no effect in that template file.

ItemCustomSearch – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that ItemType searches should be handled by custom routines instead of System.Array methods. Please refer to Performance for details. – Note: This property is available in Hashtable.cst and Queue.cst for consistency but has no effect in these template files.

### 4.2 ArrayList.cst

This class is a strongly typed reimplementation of the standard ArrayList. Type casting occurs only when the collection is accessed through generic interfaces. As of version 1.4.1, ArrayList.cst offers two additional non-standard features:

- A “unique” wrapper, in addition to the read-only and synchronized wrappers. This wrapper ensures that the collection contains no duplicate elements.

- An optional “key” that refers to one of the fields or properties of the ItemType class. Three new methods – ContainsKey, GetByKey, and IndexOfKey – and an optional indexer locate collection elements by their “key” value.

#### Additional Properties

ClassName – an optional string that defaults to “ItemTypeCollection”. This property determines the name of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the element type of the generated collection class.

KeyType – an optional string that defaults to a null reference. If provided, this property determines the type of the ItemType field or property to use as a “key” when locating collection elements.

KeyName – an optional string that defaults to “KeyType”. If provided, this property determines the name of the ItemType field or property to use as a “key” when locating collection elements.

KeyIndexer – an optional Boolean value that defaults to `false`. If set to `true`, this property indicates that a KeyType indexer should be generated. – Note: This will result in a compilation error if KeyType is Int32, and possibly cause unwanted implicit type conversions if KeyType is another numerical type.

#### Required Templates

An instance of IList.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – an ArrayList that is strongly typed for ItemType elements. This class implements ICloneable, ICollection, IList, IItemTypeCollection, and IItemTypeList. The GetEnumerator method returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

### 4.3 DictionaryList.cst

This class is my own invention. A generic version is available as part of the Toolbox .NET library. It’s basically an ArrayList that is strongly typed for DictionaryEntry elements and can therefore support a number of SortedList features. Unlike the SortedList class, a DictionaryList can hold multiple identical keys and always maintains the insertion order of its elements. On the downside, access by key is just as slow as access by value (linear time).

As with all other collection classes except for Hashtable, type casting occurs only when the collection is accessed through generic interfaces.

#### Additional Properties

ClassName – an optional string that defaults to “KeyType ItemTypeCollection”. This property determines the name of the generated collection class.

ImportNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which one of the required IList interfaces resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

KeyType – a required string that defaults to a null reference. This property determines the type of the Key parts of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the type of the Value parts of the generated collection class.

PairType – an optional string that defaults to “KeyType ItemTypeEntry”. This property determines the name of the pair structure provided by the required IDictionary template.

#### Required Templates

An instance of IDictionary.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – a DictionaryList that is strongly typed for PairType elements, KeyType keys, and ItemType values. This class implements ICloneable, ICollection, IList, IKeyType ItemTypeCollection, and IKeyType ItemTypeList. The GetEnumerator method returns an IKeyType ItemTypeEnumerator.

The Keys property of ClassName returns an IKeyTypeCollection, the GetKeyList method returns an IKeyTypeList, and the GetEnumerator method of either collection returns an IKeyTypeEnumerator.

The Values property of ClassName returns an IItemTypeCollection, the GetValueList method returns an IItemTypeList, and the GetEnumerator method of either collection returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

### 4.4 Hashtable.cst

This class is just a wrapper around the standard Hashtable, rather than a complete reimplementation. So when you use value types you should expect plenty of boxing and unboxing going on internally, even though it is hidden by the strongly typed wrapper, and performance is likely to be poor.

As of version 1.5.0, Hashtable.cst offers a read-only wrapper as an additional non-standard feature.

#### Additional Properties

ClassName – an optional string that defaults to “KeyType ItemTypeDictionary”. This property determines the name of the generated collection class.

ImportNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which one of the required IList interfaces resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

KeyType – a required string that defaults to a null reference. This property determines the type of the Key parts of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the type of the Value parts of the generated collection class.

PairType – an optional string that defaults to “KeyType ItemTypeEntry”. This property determines the name of the pair structure provided by the required IDictionary template.

#### Required Templates

An instance of IDictionary.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – a Hashtable that is strongly typed for PairType elements, KeyType keys, and ItemType values. This class implements ICloneable, ICollection, IDictionary, IKeyType ItemTypeCollection, and IKeyType ItemTypeDictionary. The GetEnumerator method returns an IKeyType ItemTypeEnumerator.

The Keys property of ClassName returns an IKeyTypeCollection whose GetEnumerator method returns an IKeyTypeEnumerator.

The Values property of ClassName returns an IItemTypeCollection whose GetEnumerator method returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

### 4.5 IDictionary.cst

This file contains a collection of strongly typed interfaces required for all collections that store key-and-value pairs. It also includes the strongly typed pair structure itself.

#### Additional Properties

ImportNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which one of the required IList interfaces resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

KeyType – a required string that defaults to a null reference. This property determines the type of the Key parts of the generated dictionary types.

ItemType – a required string that defaults to a null reference. This property determines the type of the Value parts of the generated dictionary types.

PairType – an optional string that defaults to “KeyType ItemTypeEntry”. This property determines the name of the generated pair structure.

#### Required Templates

Two instances of IList.cst with sufficient Accessibility.

One instance must use identical ItemType, ItemNamespace, and ItemValueType properties. The other instance must use ItemType, ItemNamespace, and ItemValueType properties that are identical to the KeyType, KeyNamespace, and KeyValueType properties, respectively, of the IDictionary template.

At least one instance must use an identical TargetNamespace property. If the other instance uses a different TargetNamespace, the ImportNamespace property must be set to that namespace.

#### Generated Interfaces

IKeyType ItemTypeCollection – an ICollection that is strongly typed for PairType elements.

IKeyType ItemTypeDictionary – an IDictionary that is strongly typed for PairType elements, KeyType keys, and ItemType values. This interface is implemented by Hashtable.cst and SortedList.cst.

IKeyType ItemTypeList – an IList that is strongly typed for PairType elements. This interface is implemented by DictionaryList.cst.

IKeyType ItemTypeEnumerator – an IEnumerator that is strongly typed for PairType elements, KeyType keys, and ItemType values.

#### Generated Structures

PairType – a DictionaryEntry that is strongly typed for KeyType keys and ItemType values. This structure provides implicit conversions to and from DictionaryEntry objects.

#### Default File Name

The default name for the generated C# source file is “IKeyType ItemTypeDictionary.cs”.

### 4.6 IList.cst

This file contains a collection of strongly typed interfaces required for all other interfaces and collections in this package.

#### Additional Properties

ItemType – a required string that defaults to a null reference. This property determines the element type of all generated collection interfaces.

#### Required Templates

None.

#### Generated Interfaces

IItemTypeCollection – an ICollection that is strongly typed for ItemType elements.

IItemTypeList – an IList that is strongly typed for ItemType elements.

IItemTypeEnumerator – an IEnumerator that is strongly typed for ItemType elements.

#### Default File Name

The default name for the generated C# source file is “IItemTypeList.cs”.

### 4.7 Queue.cst

This class is a strongly typed reimplementation of the standard Queue. Type casting occurs only when the collection is accessed through generic interfaces.

#### Additional Properties

ClassName – an optional string that defaults to “ItemTypeQueue”. This property determines the name of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the element type of the generated collection class.

#### Required Templates

An instance of IList.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – a Queue that is strongly typed for ItemType elements. This class implements ICloneable, ICollection, and IItemTypeCollection. The GetEnumerator method returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

### 4.8 SortedList.cst

This class is a strongly typed reimplementation of the standard SortedList. Type casting occurs only when the collection is accessed through generic interfaces.

#### Additional Properties

ClassName – an optional string that defaults to “KeyType ItemTypeDictionary”. This property determines the name of the generated collection class.

ImportNamespace – an optional string that defaults to a null reference. If provided, this property determines the namespace in which one of the required IList interfaces resides. This namespace will be imported by a `using` statement if IncludeNamespaces is `true`.

KeyType – a required string that defaults to a null reference. This property determines the type of the Key parts of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the type of the Value parts of the generated collection class.

PairType – an optional string that defaults to “KeyType ItemTypeEntry”. This property determines the name of the pair structure provided by the required IDictionary template.

#### Required Templates

An instance of IDictionary.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – a SortedList that is strongly typed for PairType elements, KeyType keys, and ItemType values. This class implements ICloneable, ICollection, IDictionary, IKeyType ItemTypeCollection, and IKeyType ItemTypeDictionary. The GetEnumerator method returns an IKeyType ItemTypeEnumerator.

The Keys property of ClassName returns an IKeyTypeCollection, the GetKeyList method returns an IKeyTypeList, and the GetEnumerator method of either collection returns an IKeyTypeEnumerator.

The Values property of ClassName returns an IItemTypeCollection, the GetValueList method returns an IItemTypeList, and the GetEnumerator method of either collection returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

### 4.9 Stack.cst

This class is a strongly typed reimplementation of the standard Stack. Type casting occurs only when the collection is accessed through generic interfaces.

#### Additional Properties

ClassName – an optional string that defaults to “ItemTypeStack”. This property determines the name of the generated collection class.

ItemType – a required string that defaults to a null reference. This property determines the element type of the generated collection class.

#### Required Templates

An instance of IList.cst with sufficient Accessibility and otherwise identical property values.

#### Generated Classes

ClassName – a Stack that is strongly typed for ItemType elements. This class implements ICloneable, ICollection, and IItemTypeCollection. The GetEnumerator method returns an IItemTypeEnumerator.

#### Default File Name

The default name for the generated C# source file is “ClassName.cs”.

## 5. Performance

The following discussion applies to all collection templates except Hashtable.cst which is simply a strongly typed wrapper around the standard Hashtable and therefore performs the same or slightly worse than the standard library class.

### 5.1 Technical Issues

The collection templates are algorithmically identical to the standard collection classes. The only difference is the fact that the template classes are strongly typed and therefore require no type casting, unless accessed through generic interfaces. This may cause a template collection to perform significantly better than a standard collection, depending on the collection’s element type(s).

There is another, more obscure influence on the performance of a .NET collection for a given type, namely the static methods of the System.Array class. We’ll first discuss these technical issues before moving on to performance recommendations. A table of benchmark results concludes this section.

#### Type Conversions

Type conversion between reference types is extremely fast in the .NET Framework. Strong typing may yield a small performance gain that will hardly matter in a real application. The only important benefit gained from collection templates with reference type elements is compile-time type checking (and more helpful IntelliSense suggestions if you’re using Visual Studio .NET).

Type conversion from value types to reference types and vice versa involves expensive operations known as “boxing” and “unboxing”, respectively. The standard collection classes perform lots of these operations because they are written for elements of type System.Object – a reference type. Strong typing completely avoids these operations which may improve benchmark performance by an order of magnitude. Any application that makes heavy use of value type collections should see a significant speedup after converting to collection templates.

#### Static Array Methods

The collection templates and the standard collection classes both rely on static methods of the System.Array class to quickly and conveniently manipulate one-dimensional arrays: Clear, BinarySearch, Copy, IndexOf, Reverse, and Sort.

All of these methods invoke native code routines for maximum performance. However, the BinarySearch, IndexOf, Reverse, and Sort methods may fall back on generic IL routines if the native routine returns an error. This appears to be the case whenever the array elements are not of a built-in value type, such as System.Int32.

The generic IL routines treat all array elements as instances of System.Object and use the standard methods Object.Equals and IComparable.CompareTo to compare elements. This results in a small overhead for reference types that offer strongly typed implementations of these comparison methods, and a very large overhead for user-defined value types which have to be boxed for every single comparison.

#### Custom Search Routines

To avoid this overhead, all class templates offer the ItemCustomSearch and possibly KeyCustomSearch properties that will replace all Array.BinarySearch and Array.IndexOf calls with a strongly typed C# reimplementation of the corresponding search algorithm. (There is currently no reimplementation of Array.Reverse and Array.Sort.)

Custom search routines are disabled by default to accomodate built-in value types. They are better handled by native code routines anyway; but on top of that, these types surprisingly do not offer strongly typed overloads of Object.Equals and IComparable.CompareTo which would cause the C# reimplementations to perform countless boxing operations.

(Using comparison operators instead of methods would have solved this problem for built-in value types but would in turn require all custom types to define all required operators before they could be used with the custom search routines.)

### 5.2 Recommendations

Any user-defined KeyType or ItemType should provide strongly typed overloads of Object.Equals, and also IComparable.CompareTo for KeyType classes, to avoid type casting as much as possible. This is necessary to fully realize the potential performance benefits of KeyCustomSearch and ItemCustomSearch.

#### Reference Types

Type conversion between reference types is extremely fast, so the runtime performance of template classes is roughly identical to that of standard library classes in this case. Setting the KeyCustomSearch and/or ItemCustomSearch properties to `true` will result in a small performance gain. It doesn’t matter if the reference type is provided by the standard library or defined by the user.

#### Standard Value Types

Boxing and unboxing is expensive, but the native code routines provided by the standard library outperform any C# reimplementation. Just set the KeyValueType and/or ItemValueType properties to `true` as appropriate. Do not set the KeyCustomSearch and/or ItemCustomSearch properties to `true`, or performance will collapse!

#### Custom Value Types

As above, except that there are no native code routines that we could use. Set the KeyValueType and/or ItemValueType properties and the corresponding KeyCustomSearch and ItemCustomSearch properties to `true` for maximum performance.

### 5.3 Benchmark Results

This section shows the benchmark results I’ve obtained on my system for several different ways to represent a simple collection of items.

- String is the reference type System.String and represents performance for all kinds of reference type.

- Int32 is the built-in value type System.Int32 and represents performance for value types that enjoy special support by the C# compiler and the .NET Framework.

- ValidString is the value type Toolbox.StringTbx.ValidString which is a simple wrapper around System.String provided by version 2.0.3 of my Toolbox .NET library. ValidString represents performance for value types that do not enjoy any special compiler or Framework support.

For each item type, I tested three collection classes: the standard library ArrayList, a standard fixed-size array, and a collection class generated by the ArrayList.cst template that shipped with version 1.2.0 of the Collection Templates package. Each timed section consists of the following actions:

1. Call Add to add the specified number of (random) elements to the empty collection. For fixed arrays, we simply set each array element to the desired value.
2. Call IndexOf to determine the index of each collection element.
3. Call Sort to sort the collection, and then call BinarySearch to determine the index of each collection element.
4. Use a foreach loop to call GetEnumerator and iterate over all collection elements.
5. Call RemoveAt to remove all elements from the collection, starting at the highest index. For fixed arrays, we simply set each array element to a null or zero value.

The tests were run in release mode with optimization enabled. Fast dummy operations (integer exclusive-or) were performed in each loop to prevent the C# or JIT compiler from “optimizing away” the instructions we’re interested in. The results showed little deviation in dozens of repetitions.

Times are given in seconds, and as an inverse percentage compared to ArrayList. Timing was performed by csUnit 1.8.8 which was also used to unit-test the collection templates. Benchmark and unit testing sources are available on request.

Items | Count | ArrayList | Fixed Array | Template
--- | --- | --- | --- | ---
String | 25,000 | 11.547 sec | 100% | 11.500 sec | 100% | 10.250 sec | 113%
Int32 | 50,000 | 36.656 sec | 100% | 2.375 sec | 1543% | 2.406 sec | 1524%
ValidString | 10,000 | 6.250 sec | 100% | 16.938 sec | 36.9% | 1.969 sec | 317%

#### Observations

The template class always performs at least as well as the faster of the two standard classes, ArrayList or fixed array. It is interesting to note that the memory reallocations which are required for ArrayList and ArrayList.cst, but not for fixed arrays, do not seem to impact performance at all.

String. As expected, all three classes perform about the same. System.String offers a CompareTo method (even a strongly typed one) which allows the use of custom search routines, resulting in a small performance edge for the template class.

Int32. Frequent boxing and unboxing causes extremely poor performance for the standard ArrayList. The fixed array and the template class both avoid this problem and perform equally well.

ValidString. Performance is again much better for the template class than for the standard ArrayList which is bogged down by boxing/unboxing operations. Surprisingly, ArrayList performs better than a fixed array in this case. This is likely because ArrayList already stores its elements in “boxed” format, thus saving some time when the static Array methods fall back on their generic search routines.

## 6. Version History

Released | Version | Description
--- | --- | ---
2004-03-01 | 1.5.0 | Added template file Queue.cst Added DeepCopy and DeepCopyItem properties to class templates Moved ItemValueType and KeyValueType to Context group Moved common script methods to separate file CommonScript.cs DictionaryList, SortedList: Clone duplicates synchronized wrappers DictionaryList, SortedList: Devirtualized Contains… methods Hashtable: Added ReadOnly wrapper, fixed CopyTo method Stack: Pop correctly clears reference to deleted element
2004-01-19 | 1.4.1 | ArrayList: Added IsUnique property and Unique method, based on a post by Joost in the CodeSmith forums ArrayList: Added KeyName, KeyType, and KeyIndexer properties, with corresponding indexer and methods ArrayList: Devirtualized Contains and ContainsKey methods
2003-12-22 | 1.4.0 | ArrayList: Added InnerArray to fix AddRange(ClassName) for read-only and synchronized wrappers DictionaryList: Added InnerKeys/Values to fix AddRange(ClassName) and Equals for synchronized wrapper Fixed Accessibility propagation if IncludeInterfaces is `true` Namespaces are always declared if IncludeNamespaces is `true`, even when re-instantiating the same compiled template
2003-11-21 | 1.3.2 | Added default output file names to all templates
2003-11-02 | 1.3.1 | ArrayList: Added methods Reverse(), Reverse(Int32, Int32), Sort(IComparer), and Sort(Int32, Int32, IComparer)
2003-10-09 | 1.3.0 | Added IncludeInterfaces and IncludeNamespaces properties Changed IList.Item (DictionaryList) and IEnumerator.Current (DictionaryList, SortedList) to return boxed DictionaryEntry Revised overview and tutorial sections of ReadMe file
2003-09-28 | 1.2.3 | Added #region directives for overloads and private methods/classes Added line breaks as necessary, removed all trailing whitespace
2003-08-03 | 1.2.2 | Eliminated duplicate namespace imports (thanks to Ben Mackie!) Added script methods Start/EndNamespace to all templates IDictionary.IKeyItemEnumerator.Entry: Fixed XML comment
2003-07-24 | 1.2.1 | Added documented version checking to all enumerator properties
2003-06-24 | 1.2.0 | Added properties ItemCustomSearch and KeyCustomSearch Added object casts for null comparisons of KeyType and ItemType Added section on performance considerations to ReadMe file ArrayList.AddRange: Fixed premature capacity increase ArrayList.BinarySearch: This method actually works now… ArrayList: Added method RemoveRange DictionaryList.AddRange: Fixed premature capacity increase Stack: Inverted direction of CopyTo, GetEnumerator, and ToArray
2003-06-16 | 1.1.0 | Added template file Stack.cst
2003-06-11 | 1.0.1 | ArrayList, DictionaryList, SortedList: Fixed null reference exceptions
2003-06-10 | 1.0.0 | Initial release of Collection Templates

## 7. Known Issues

If IncludeInterfaces is set to `true`, all required interface template files must be in the same directory as the parent template. By default all template files are unpacked to the same directory, so this is only an issue if you have deliberately placed some template files in a different directory.

If defined, KeyNamespace and ItemNamespace are imported with `using` statements. All dictionary templates therefore require that KeyType and ItemType have different names; it is not sufficient that they reside in in different namespaces.

The enumerator properties Current, Entry, Key, and Value should buffer their return values and ignore changes to the underlying collection until the next call to MoveNext or Reset. However, all collection templates except Hashtable.cst use simpler implementations without buffering that fail when the underlying collection was changed. This should not be a problem with typical `foreach` loops; and in my opinion, it’s also the behavior one would intuitively except.

If KeyCustomSearch or ItemCustomSearch are `false`, the standard BinarySearch routines will explicitly request the interface method IComparable.CompareTo and ignore any non-interface method of the same name. Conversely, when these properties are `true`, the custom BinarySearch routines will attempt to directly invoke CompareTo on a KeyType or ItemType object. Therefore, these routines will not compile if the only available CompareTo method is an explicit interface implementation of IComparable. – Note that the usual and recommended case is an implicit (public) implementation of CompareTo which will work fine with either property setting.

ArrayList: ItemType must define a CompareTo method if ItemCustomSearch is `true`, or the custom BinarySearch method won’t compile. Set ItemCustomSearch to `false` if your ItemType does not provide a CompareTo method, or add a mock CompareTo method to ItemType if you don’t need BinarySearch.

ArrayList: If KeyType is defined, the generated key indexer (if any) and the ContainsKey, GetByKey, and IndexOfKey methods use the == operator of the KeyType class, so make sure to properly define this operator if you override Object.Equals for this class.

DictionaryList: The methods Contains, Equals, and IndexOf use the == and != operators of the KeyType and ItemType classes, so make sure to properly define these operators if you override Object.Equals for either class.