Intrusive Data Structures

"Intrusive Data Structures" by JiriSoukup (CppReport, May 1998, Vol 10/No5. p. 22.)

Also available online: http://www.codefarms.com/publications/intrusiv/intr.htm

Abstract:

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 auxilliary 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 exisiting 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.

CategoryPaper