    
        
        
        
    
Overview
	The 
introduction.htmlIntroduction  Section described some challenges
in designing associative containers. This section describes the 
pb_assoc's solution.
Figure
#cdClass hierarchy shows a class diagram of 
pb_assoc's associative containers.Associative container classes subclass other associative container classes such that
base classes capture common types and methods
[
references.html#stroustrup97cppstroustrup97cpp ]. The type hash_fn is defined in basic_hash_assoc_cntnr.htmlbasic_hash_assoc_cntnr , for example, since all hash-based containers employ a hash function;
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr and
gp_hash_assoc_cntnr.htmlgp_hash_assoc_cntnr ,
subclasses encapsulating a collision-chaining and (general) probing hash table, respectively, each define other types specific for their underlying data-structure.
This is described further in
ds_gen.htmlData-Structure Genericity .
no image
Class hierarchy.
	It is sometimes useful to know the underlying data-structure.
Associative containers internally define 
ds_category as a class describing this. Two classes might be different instantiations
of
tree_assoc_cntnr.htmltree_assoc_cntnr , but one might be based on a red-black tree while another might be based on a splay tree. (This might affect the way tree objects should be manipulated.) typename Cntnr::ds_categoryyields a "tag" class for the underlying data-structure of some type
Cntnr.
This is described further in
ds_gen.htmlData-Structure Genericity .
	When manipulating generic containers, it is useful to know which types, methods, and guarantees they support. For example, tree-based containers can support split and join operations, while containers based on most other underlying data-structures cannot.
These questions can be answered in compile time through a traits mechanism.
ds_traits.htmlds_traits<Cntnr>::split_join , for example, answers the above question.
This is described further in
ds_gen.htmlData-Structure Genericity ;
../example/ds_traits_example.cppds_traits_example.cpp -
shows an example.
	
pb_assoc	does not contain separate containers for different mapping semantics,
as the STL does (
e.g., std::map and std::multimap). Rather, containers are parameterized by a Data parameter, and this parameter is a policy for the mapping semantics.
	
	Instantiating a container's 
Data parameter by all but two distingished types, will make a "map". Thus
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr <
	
int,
	
char>
 is a type mapping each int value to a char	value.
	
../example/basic_map_example.cppbasic_map_example.cpp 	shows an example.
	
	
	Instantiating a container's 
Data parameter by null_data_type.htmlnull_data_type  will make a "set". Thus
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr <
	
int,
	
null_data_type.htmlnull_data_type >
is a type storing unique 
int values.
../example/basic_set_example.cppbasic_set_example.cpp  shows an example.
	
	
	Instantiating a container's 
Data parameter by compound_data_type.htmlcompound_data_type <Cntnr>, where Cntnr is a different associative container, will make a "(multi)+map". Thus
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr <
	
int,
	
compound_data_type.htmlcompound_data_type <
		
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr <
			
char,
			
null_data_type.htmlnull_data_type > > >
 is a type
mapping each 
int value to a "set" of charvalues.
../example/basic_multimap_example.cppbasic_multimap_example.cpp  shows an example.
This composition is recursive, however, and more complex relationships can be built.
../example/mapping_level_example.cppmapping_level_example.cpp  shows an example.
	
	The associative-container classes derive each from one of the three
basic_assoc_cntnr.htmlbasic_assoc_cntnr  classes, depending
on the data policy. These three base classes define different types and methods. For example, the "map" specialization of
basic_assoc_cntnr.htmlbasic_assoc_cntnr defines 
operator[], wherase the "set" specialization does not.
This is described further in
ms_gen.htmlMapping-Semantic Genericity .
	
pb_assoc's design contains the concept of a mapping level. "Map" and "set" types have a single mapping level; A container
mapping integers to "maps" mapping characters to floats has two mapping levels, since it can be viewed as a type mapping each integer to a "map", or as a type mapping each pair of integer and character to a float. 
pb_assoc contains traits and rebind mechanisms for querying and altering the mapping levels.
This is described further in
ms_gen.htmlMapping-Semantic Genericity .
	The leaf classes in Figure
#cdClass hierarchy are each parameterized by policies, easing configuring containers for different settings.
hash_based_containers.htmlHash-Based Containers  describes the design and policies of hash-based containers,
	
tree_based_containers.htmlTree-Based Containers  describes the design and policies of tree-based containers, and
	
lu_based_containers.htmlList-Based Containers  describes the design and policies of list-based containers with update policies.
