This article compares two styles of building data structures and data structure libraries in C++: (a) Intrusive data structures formed by pointers stored inside the application objects, (b) Containers where auxiliary objects form the required data structure, and only point to the application objects without adding any pointers or other data to them.

Each style works better in different situations, and the first half of the article discusses the impact of this choice on program performance, code maintainability, ease of use and data integrity. When working with templates, containers are easier to implement, which may be the reason why most class libraries are based on containers. The only existing library which is consistently intrusive (Code Farms) uses a code generator. If intrusive data structures could not be implemented with templates, their applicability would be severely limited. The second half of the article deals with this pivotal question, shows an elegant way of building an intrusive data structure library with templates, explains why its interface is similar to- but cannot be identical with STL, discusses the impact of the new architecture on class dependency, and compares the new approach with existing libraries. A prototype of the new library is now available under the name Pattern Template Library.

Open any book on data structures, and somewhere near the beginning you will find a linked list similar to Fig.1a. This is the type of list you would probably use in your program if you were not using any class library.

Download pdf Intrusive Data Structures