Main Page   Class Hierarchy   File List  

Compact Associative Collections

Author:
Michael Carrato
Version:
1.0

Introduction

CompactSet and CompactMap are space-efficient associative collections that are drop-in replacements for std::set and std::map, for most uses. The collections are implemented using a hybrid table/tree structure described in C/C++ Users Journal (July 2003 issue). Note that there are some minor performance enhancements in the actual code that were not described in the article, which focused mainly on the basic algorithms.

Features include:

Compiler Compatibility

The compact collections have been tested with the following compilers:

The code should compile on most standard-compliant C++ compilers.

Implementation Summary

The compact collections use a hybrid structure that uses a tree-based collection (std::set or std::map) for newly inserted elements, and a vector-based collection (sorted std::vector or std::deque) for "old" elements. As the collection grows, elements are copied from the tree-based collection into the more space efficient vector-based collection, in a process called compaction.

The use of the tree-based collection guarantees that inserts occur in O(log(N)) time. Compaction occurs in geometric increments of the collection size, so that the cost of compaction is amortized O(1), identical to the expansion cost of std::vector. The total insert cost is therefore amortized O(log(N)).

The per-element overhead for the vector-based collection is almost 0, whereas the per-element overhead for std::set/std::map is at least 12 bytes (plus dynamic memory overhead). For a 4-byte value type (i.e. std::set<int> ), the cooresponding compact set consumes about one third the memory of the standard version.

Policy-based Configurability

Note: Policies are not available with g++ 2.95 or Microsoft Visual Studio 6.0.

Policies provide an additional level of flexibility for customizing compact collections. There are two supplied compact policies supplied with the base code:

In addition to the policy class (which is a template parameter, and therefore fixed at the time of instantiation), the compact collections also allow for dynamic optimizations, by modifying the following parameters : Users may also define their own policy, by defining a class that is interface compatible with SortedArrayBase (defined in CompactColl.h)

Compatibility With Standard Containers

The compact collections are interface compatible with their standard associative collection counterparts. However, there are some minor deviations from the standard spec. These deviations are listed below:

When to Use Compact Collections

The use of table-based storage in compact collections may also reduce memory fragmentation in the dynamic memory allocator, by replacing many small allocations with one large one. This is a theoretical benefit only, and has not been tested.

When NOT to Use Compact Collections

Thread Safety

The compact collections are designed to be thread safe, using the commonly accepted standard for thread safety (multiple readers on the same instance, multiple writers on different instances).

Note 1: Thread safety assumes an underlying standard library that is thread safe.

Note 2: No actual thread testing has been done on the compact collections.

Exception Safety

For the MaximizeSpeedPolicy, I have made an attempt to provide the strong guarantee, but more analysis needs to be done before I can assert that it is. At the very least, I am confident that the compaction itself is strongly exception safe (provided that the underlying standard library is exception safe as well)

For the MinimizeSpacePolicy, the goal of preserving memory at all costs is at odds with the strong guarantee. Since the compaction destroys the old as it rebuilds the new, it is difficult to provide any exception safety guarantees. Therefore, it is recommended that the MinimizeSpacePolicy only be used with value types that do not throw on copy, assignment, or operator<.

Recommended Installation

The distribution contains the following source files:

To use the collection classes, copy the header files CompactColl.h, CompactMap.h, CompactSet.h, and IterAdapter.h, into your include path.

There is currently no namespace, but I plan to add an optional namespace in the next release.

Bug Reports

Please send bug reports to mcarrato@hotmail.com


Generated on Wed May 28 12:44:07 2003 for Compact Associative Collections by doxygen1.2.18