Cdt is a library for container data types. It provides a uniform interface to manage objects in dictionaries based on the storage methods: list, stack, queue, ordered set/multiset, and unordered set/multiset. Each dictionary has an application-defined discipline and a library-provided method. A Cdt discipline defines object attributes such as how to compare them or how they should be accessed. This can be used to create set-like dictionaries, i.e., objects addressed by comparisons, map-like dictionaries, i.e., objects addressed by keys, and shared dictionaries, i.e., the same objects in multiple dictionaries. A Cdt method defines the data structures and algorithms used to store and efficiently access objects based on their defined attributes. The current set of methods include:

• Dtset: This stores unique and unordered objects. Objects are stored in a hash table with move-to-front chains.
• Dtbag: This stores repeatable and unordered objects. Objects are stored in a hash table so that repeated objects are kept together.
• Dtoset: This stores unique and ordered objects. Objects are stored in a splay tree.
• Dtobag: This stores repeatable and ordered objects. Objects are stored in a splay tree.
• Dtlist: This stores repeatable and unordered objects in a list. Objects are always inserted in front of some current list positions.
• Dtstack: This stores repeatable and unordered objects in a stack. Objects are stored in reverse order of insertion.
• Dtqueue: This stores repeatable and unordered objects in a queue. Objects are stored in order of insertion.

Cdt can be used with the Vmalloc memory allocation library to build persistent dictionaries based on memory mapping. An example of how to do this is given in the Vmalloc distribution.

Below are papers related to Cdt:

• Kiem-Phong Vo, "Cdt: A Container Data Type Library", Software Practice & Experience, vol.27, pp.163-172, 1997.
• Kiem-Phong Vo, ``The Discipline and Method Architecture for Reusable Libraries'', Software - Practice & Experience, v.30, pp.107-128, 2000.
• Kiem-Phong Vo, ``Vmalloc: A General and Efficient Memory Allocator'', Software Practice & Experience, vol.26, pp.1-18, 1996.
• Glenn S. Fowler, David G. Korn and Kiem-Phong Vo, ``Feature-Based Portability'', Proceedings of the Usenix VHLL Conference, pp. 197-207, 1994.

Comments/Questions/Problems

Except for configuration problems in building the package, a bug report should be in the form of a small program that I can compile and run. Without such a program, I will likely ignore the report since it often takes too much time for me to tell if a reported bug is real or if it's just a misuse of the code.