Following are some concepts used throughout the documentation.
Associative containers are typically parameterized by various policies. For example, a hash-based associative container is parameterized by a hash-functor, transforming each key into an non-negative numerical type. Each such value is then further mapped into a position within the table. The mapping of a key into a position within the table is therefore a two-step process.
In some cases, instantiations are redundant. For example, when the keys are integers, it is possible to use a redundant hash policy, which transforms each key into its value.
In some other cases, these policies are irrelevent. For example, a hash-based associative container might transform keys into positions within a table by a different method than the two-step method described above. In such a case, the hash functor is simply irrelevent.
pb_assoc uses special pre-defined "null policies" classes for these cases. Some null policies in pb_assoc are:
A "set" in pb_assoc is an associative container with its Data_Parameter instantiated by null_data_type. Tree-Based Containers::Node Invariants explains another case where a null policy is needed.
Associative containers allow access to their elements via iterators. E.g., find returns an iterator to an element with a given key and begin returns an iterator to the first element in the container.
In general, there are two types of methods: find types, and range types. Find-type methods return iterators corresponding to elements which have been found in some sense, as the container searched for them in order to access them (i.e., via the find method) or searched for their location in order to insert them (i.e., via the insert method). Range-type methods return iterators which can be used to traverse the range of all stored elements, (i.e., via the begin and end methods).
Correspondingly, in pb_assoc there are two types of iterators: find type iterators are returned by find methods, and range iterators are returned by range methods. For example, if T is any associative container with integer keys, and t is a container of type T, then the following snippet is valid:
typename T::find_iterator it0 = t.find(3); typename T::const_find_iterator it0 = t.find(3); typename T::iterator it0 = t.begin(); typename T::const_iterator it0 = t.begin();
This is motivated and explained further in Data-Structure Genericity::Find-Type and Range-Type Methods and Iterators, which also explains the relationship between find-type and range-type iterators.
In pb_assoc "multimaps" are "maps" of "sets". While this design allows efficient operations, it makes for cumbersome use at points. For example a "multimap" of integers to characters does not directly support inser(std::make_pair(2, 'b'), since 2 is mapped to a "set" of characters, and not to a character.
Consequently, pb_assoc contains a rebind-like mechanism so that containers can support such operations. To dispel ambiguity, container types are assigned mapping levels. "Maps" and "sets" have a mapping level 1, since they use a single association level. The "multimap" above has a mapping level 2, since it uses two association levels: one for integers, and one for characters. The rebind mechanism can be used to alter the association level. This is described in Mapping Semantics.