Introduction

There are (at least) three orthogonal challenges to designing generic associative containers:

1. The choice of underlying data-structure affects not only the performance of containers, but their semantics as well. E.g., containers based on trees store elements by a given order, while containers based on hash tables store elements in a meaningless (and probably time-varying) order; containers based on node-based trees can guarantee exception-free element erasing, while containers based on vector-based trees cannot. This complicates generic manipulation of associative containers based on different underlying data-structures.
2. Underlying data-structures can act very differently given different policies. E.g., the policy by which a hash table translates a hash value into a position within a table affects performance dramatically; certain policies can make containers based on trees support order statistics (i.e., queries on the order of stored elements) or other useful queries. This complicates the policy design of an associative container based on a given data-structure.
3. Various mapping semantics are appropriate in different settings. E.g., in some cases a unique mapping between each key and a datum is appropriate (such as the STL's std::map guarantees); in other cases, unique storage of keys is required (such as the STL's std::set guarantees); in other cases, more complex mapping semantics are required. This complicates generic manipulation of associative containers with different mapping semantics.

pb_assoc attempts to address these problems safely and efficiently.