Introduction

NGenLib is a .Net library written in C# with an STL-like design that offers generic data structures, algorithms and utility classes.

Download the latest version.

News

15/06/2004: NGenLib 0.1 for VS2005 CTP May 2004 or Beta 1

NGenLib 0.1 is the first NGenLib release.

It includes iterators, with support for vectors and linked lists, basic, sorting-related and heap algorithms, and some mathematical functionality.

A few NUnit tests are available, mostly for sorting algorithms.

Help wanted!

If you think this project is cool or you have a great idea on how to improve it, don’t hesitate to make a proposal or send your changes!

NGenLib, while already containing some significant functionality, is still in an early stage, so contributions are greatly needed.

Contact

You can contact me personally using my SourceForge mail address (lucabar AT users.sf.net).

A mailing list is available.

NGenLib documentation

Introduction

NGenLib is a .Net library written in C# with an STL-like design that offers generic data structures, algorithms and utility classes.

This document assumes that you are familiar with the SGI STL design and presents NGenLib functionality by comparing it with similar STL functionality.

License

MIT license.

About the source code

The source code contains a Visual Studio 2005 Community Technology Preview solution with 2 projects:

• NGenLib: the NGenLib library assembly.
• NGenLibTests: NUnit tests (very incomplete)

About the documentation

The present document is the only available documentation, with the exception of the source code.

When NDoc starts supporting generics, MSDN-like generated documentation will probably become available.

Running tests

See http://www.mattberther.com/2004/04/000459.html to add .Net 2.0 support to NUnit (note: the version number in that page is old, replace it with the current one - to get it, look in c:\windows\microsoft.net\framework and find the newest v2.0.* folder containing csc.exe).

NGenLib equivalents of STL entities

Concepts

Concepts are modeled by an interface with the Conceptual attribute and a property within it with the Concept attribute.

The interface defines all the possible operations that could make sense on the type and the property refines that.

Conceptual interfaces do not support any of their functions by default: only those with the Supported attribute are supported.

A concept is specified as a series of attributes representing the addition of attributes to other functions of the interface or to their parameters.

When using a conceptual interface, it is possible to declare a concept requirement with the RequireConcepts attribute; using this attribute, however, is quite cumbersome, so most conceptual interfaces provide helper static classes containing “C” attributes that allow to require concepts with less typing (e.g. [Iter.C(“Fwd”)]).

Iterators

Iterators implement the IIter<TO, TI> interface, where TO is the object type and TI is the type of the iterator itself. They must be value types because value types are much more efficient and are naturally suited to be used for this.

Having the iterator type as a generic parameter to IIter may seem an odd design choice, but it is required because some functions return or accept iterator parameters and encoding them as interfaces would require boxing. Furthermore, this choice and the value type choice mean that algorithms using iterator will be generated for every iterator type, allowing iterator functions to be inlined.

Virtual iterator

A virtual iterator is an iterator of class VirtIter<TO, TI> implementing IIter<TO>, which is derived from IIter<TO, IIter<TO>>. Virtual iterators allow you to refer to an iterator of any type; the disadvantage of using them is that VirtIter is a class and thus is much less efficient than structs. Furthermore, algorithms using VirtIter do not inline any iterator members.

Currently NGenLib functions all require iterators to be structs because classes and structs have different copying semantics and class semantics are not supported. To use an generic algorithm on a VirtIter, you should use reflection to call the generic algorithm on the contained type (use VirtIter.I and VirtIter.TI to get the iterator object and the type object). Unfortunately, doing so seems to crash the current pre-release VM, so no infrastructure is provided for this.

Containers

In NGenLib, containers do not have any special status like STL and all STL-style manipulation on them happens through iterators, that can be obtained in a container-specific way.

Note that while STL defines container concepts, they are actually not used, and iterator pairs are always preferred.

This choice allows to use vanilla CLR classes such as System.Collections.Generic.List<T> together with iterators and other NGenLib functionality. Iterators for such types can be obtained with Iter.Begin() and Iter.End().

Insertion and removal functions have been made part of the iterator interface, as the CSeq concept.

While we try to reuse the CLR classes, a LinkList<T> class is included in NGenLib as a replacement for the LinkedList<T> class because the CLR class does not allow O(1) movement of elements (since it keeps a pointer to the list in every node) and its sentinel-less design makes iterators less efficient.

Algorithms

Algorithms are implemented in the Algo class and are similar to the STL ones.

Function objects

There is some code but it is very incomplete.

Furthermore, due to CLR inlining deficiencies, functional support may be significantly less powerful that the STL one.

STL to NGenLib correspondence tables

General entities

Containers

Iterator concepts

Container concepts

Algorithms

Look at the static class Algo.

Function objects

Not finished

Utilities

Design flaws in .NET 2.0 and workarounds

Lack of explicit forced inlining (and very low aggressiveness of the automatic one)

This is the worst of all the flaws listed here.

Designing fast .NET 2.0 libraries is made much harder by this because some powerful abstractions, that would be optimized away if inlined, cannot be used because they would actually appear in the resulting code.

Furthermore, there is no way to make sure that inlining happens consistently so even testing is not conclusive.

Currently, for instance, we hope that ILessComparable<T>.Less always gets inlined when it one of the NumAdapt.cs implementations and is in a specialized generic function. If this is not inlined, the performance of Sort and other compare-based algorithms will probably halve or worse.

Writing a custom IL inliner using the COR profiling API could be a workaround.

Lack of default generic parameters

There is no way to define a default generic parameter on a value type, even with “manual overloading” because a value type cannot be subclassed.

Currently iterators have Distance and Size hardcoded because of this flaw.

Lack of the ability to call generic functions with a runtime-determined interface

Suppose that we interface IA and IB where IB : IA.

If we define a function with a generic parameter that requires IA, we would like to be able to check whether IB is also supported and, if so, call another function with a generic parameter that implements IB.

However, this is apparently impossible without boxing and passing IB itself as the type.

This is worked around by using a single interface and using concepts to differentiate implementations.

Lack of generic parameter deduction using constraints in C#

This flaw causes the C# compiler to be unable to deduce types if a function uses iterators and no object parameters.

We work around this by adding a dummy parameter of type Tag<TO> that allows you to explicitly specify only the object type rather than all generic parameters.

Furthermore, all iterators provide a T property that returns a Tag<TO> object and there is an Iter.T() function that returns a tag for container object types.

Generic function specialization only for value types

Generic functions are only specialized for value types, that means that functions can only get inlined with value types.

NGenLib implements function objects as value types rather than delegates for this reason.

Lack of generic operator support

The lack of generic operator support is worked around by defining inelegantly-named functions that perform the operator job.

Lack of value type operator = overloading

The lack of operator = overloading is worked around by defining an Edit() function that is to be run after the equals operation if the type is modified

Lack of integer/object generic parameters

This feature is currently not needed by NGenLib.

Lack of generics specialization

The lack of specialization is somewhat worked around by creating differently-named classes and forcing the user to specify the desired class.

Lack of typedefs and template-member types

It is not possible to say “ArrayIter<TO>.ObjectType a;” in C#. This is worked around by specifying all such types as generic parameters to the functions using them and using Tag<>s to represent types.

Lack of Turing-complete templating (due to lack of specialization and typedefs)

This feature is currently not needed by NGenLib but it may be needed in the future: manual dynamic code generation may be the solution.

Lack of the memberof(): ability to get member reflection classes efficiently

The only way to get reflection classes for members is string lookup, that of course is terrible.

Currently this feature is not needed, but the only workaround seems to be statically storing the values, perhaps automated with an assembly-processing tool.

Reflection is slow