    
        
        
        
    
Mapping-Semantics
	This section describes genericity over different mapping-semantics. It is organized as follows.
	
#introIntroduction 	
#ds_policyData Types as a Policy 	
#problemThe Basic Problem 	
#mapping_levelMapping Levels 	
#ms_traitsTags and Traits 	
#drawbacksDrawbacks Introduction 
motivation.html#mapping_semanticsMotivation::Mapping Semantics  discussed scalability issues with the STL's non-unique-mapping associative containers; non-unique association inherently embeds linked-lists in associative containers resulting in scalability problems and other problems.
	In 
pb_assoc, all containers have unique-key semantics. Each key is uniquely mapped to "something".
Data Types as a Policy 
	All associative-containers in 
pb_assoc are parameterized by a data type.
E.g., cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr  is parameterized as
template<
	
typename Key,
	
typename Data,
	...>
class cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr ;
	There are no separate classes for maps, sets, multimaps, and multisets (as the STL has). Rather, the mapping-semantic is set by specifying the 
Key parameter.
	
 If Data is any type (e.g., int or
std::string), then the container is a "map" - it maps each Key object to a Data object.
	
	
 If Data is
null_data_type.htmlnull_data_type ,
then the container is a "set" - it stores each 
Key object. In this case, each Key object is not really mapped to anything (except, implicitly, to the fact that it is stored in the container object).
	
	
	If 
Data is
compound_data_type.htmlcompound_data_type <Cntnr>,
then the container is a "multimap" - it maps each 
Key object into a Cntnr object. This structure is recursive - Cntnr itself can be a "map", "set", "multimap", and so forth.
	
	Each container derives from one of the three containers
in the oval of Figure
#ms_cdData-types as a policy
.
		
			
basic_assoc_cntnr.htmlbasic_assoc_cntnr is the base for most instantiations of a container's 
Data paramter. This
base includes the definition of 
data_type, and supports
operator[].
			
			
basic_assoc_cntnr_no_data.htmlbasic_assoc_cntnr  is the base for a
null_data_typenull_data_type  instantiation of a container's Data paramter. This
base lacks the definition of 
data_type, and does not support
operator[].
	
basic_assoc_cntnr_compound_data.htmlbasic_assoc_cntnr   is the base for a
compound_data_type.htmlcompound_data_type <Cntnr> instantiation of a container's Data paramter. This
base includes the definition of 
data_type, and supports
operator[]. It further supports some advanced functionality described in the remainder of this section.
		
no image
Data-types as a policy.
The Basic Problem 
	Consider a 
pb_assoc "multimap" mapping integers to characters.
Since a 
pb_assoc "multimap" is a "map" of "sets",
if 
m is an object of this type, it is not possible to directly use
m.insert(std::make_pair(2, 'b') (however, it is possible to directly use
m[2].insert('b')). In would be nice if this method whould be supported.
	Put differently, while the 
pb_assoc "multimap" can be viewed logically as the collection
	{ 
int → {char} },
	It would be nice if it could simultaneously be viewed as the collection
	{ (
int, char) },
i.e., a "set" of pairs.
	In more general terms, it would be nice to be able to simultaneously
view a collection
{ key_type_0 → { key_type_1 → { key_type_2 → { key_type_3 → { ... }}}}}
as each of the following:
{ (key_type_0, key_type_1) → { key_type_2 &rarr { key_type_e → { ... }}}},
{ (key_type_0, key_type_1, key_type_2) &rarr { key_type_3 → { ... }}}
{ (key_type_0, key_type_1, key_type_2, key_type_3 ) &rarr { }}
...
#mapping_level"Mapping_Levels  discusses the mechanism
for these multiple views in 
pb_assoc
Mapping Levels 
	Each associative container in 
pb_assoc has
a 
mapping level. The mapping level is defined by
the instantiation of a container's 
Dataparameter:
	
 If the Data parameter is instantiated
by
null_data_type.htmlnull_data_type  (i.e.,
the container is a "set"), then the mapping level is 1.
	
	
 If the Data parameter is instantiated
by
compound_data_type.htmlcompound_data_type <Cntnr>(
i.e., the container is a "multimap"), then the mapping level
is 1 + the mapping level of 
Cntnr.
	
	
 If the Data parameter is instantiated
by any other type, 
e.g., char (i.e.,
the container is a "map"), then the mapping level is 1.
	
	Containers can be rebound, at compile time, to different mapping levels.
The compound data-type specialization 
basic_assoc_cntnr_compound_data.htmlbasic_assoc_cntnr defines internally
template<
	
int Mapping_Level>
struct rebind
{
	
typedef		...
		other;
};
(which is similar to the STL's allocator rebind mechanism).
the type 
other is the view of the container with mapping
level 
Mapping_Level. The container can be safely cast
to 
other.
	As an example, consider the type
typedef	
cc_hash_assoc_cntnr.htmlcc_hash_assoc_cntnr <
		
int,
		
compound_data_type.htmlcompound_data_type <
			
tree_assoc_cntnr.htmltree_assoc_cntnr <
				
char,
				
null_data_type.htmlnull_data_type > > >
	cntnr_t;
	which is a "map" mapping each 
int to
a "set" of 
chars. In this case, cntnr_t has mapping level 2.
	An object of type 
cntnr_t cannot support insert(std::make_pair(2, 'b'));. On the other hand, the following code snippet shows how to do so:
cntnr_t c;
typedef	t::rebind
::other
	t_;
((t_ &)c).insert(std::make_pair(2, 'b'));
../example/mapping_level_example.cppmapping_level_example.cpp  shows a more detailed example.
Tags and Traits 
	It is, of course, beneficial to query types for their mapping semantics.
	Each container defines internally the type 
ms_categoryas its mapping-semantics tag (hopefully this name is not copyrighted
by some major corporation). The possible tags, shown in Figure
are the following:
	
	
basic_ms_tag.htmlbasic_ms_tag is a basic mapping-semantics tag. It is the type defined by "set"s.
	
	
	
data_enabled_ms_tag.htmldata_enabled_ms_tag is a mapping-semantics tag of types that have data. It is the type defined by "map"s.
	
	
	
compound_data_enabled_ms_tag.htmlcompound_data_enabled_ms_tag is a mapping-semantics tag of types that have compound data. It is the type defined by "multimap"s.
	
	Additionally, a container's mapping semantics can be queried by traits. For any
container 
Cntnr,
ms_traits.htmlms_traits <Cntnr>::mapping_level
	indicates the mapping level of the container, for example.
Drawbacks 
pb_assoc's mapping-semantics design has some drawbacks compared to that of the STL.
Equivalent, Non-Identical Keys
	The STL's multimaps and multisets allow storing equivalent, non-identical keys
[
references.html#kleft00setskleft00sets ]. For example, assume a bank maintains a data structure monitoring the accounts opened by each person. This could be modeled as the following:
// Name type.typedef	std::string
	name;
// Account-id type.typedef	
unsigned long	account_id;
// Association between a name and an account id.class opened_info
{
public:
	...
	
// Comparison operator.	
bool	 	
operator<	 	(
const opened_info &r_other)
	{
		
Comparison is defined as the comparison of the names.	 	
return m_name private:
	name m_name;
	account_id m_acc_id;
};
// A multiset of opened accounts.typedef	std::multiset<
		opened_info>
	all_opened_info;
	
std::multiset can accomodate multiple equivalent, non-identical opened_info - those with the same name but different account id.
	In 
pb_assoc, however, non-unique mapping is unsupported. The equivalent to the above could be
typedef	tree_assoc_cntnr<
		name,
		compound_data_type<
			cc_hash_assoc_cntnr<
				account_id> > >
	all_opened_info;
	The drawback lies in the fact that the data stored in
all_opened_info is less encapsulated - an opened_infoobject needs to be constructed when a specific name and account are found, and
an 
opened_info object needs to be decomposed into name and
account_id objects when it is inserted into a all_opened_infoobject.
	It should be noticed however, that the above drawbacks - construction and decomposition are constant-time additive drawbacks. The drawbacks of the
STL's associative containers are in terms of orders of growth.
Definition of value_type
	The STL's associative containers contain a pleasingly uniform definition of
the 
value_type of a container.
If a container is parameterized by 
key as its Key, and data as its Data, then its value_type is
std::pair<const key, data>;
for example, the 
value_type of std::map<int, char> is
std::pair<const int, char>. Futhermore, the value_type of a container and the value_type of the container's iterators are identical.
	In 
pb_assoc, conversely, the rules are more complex.
 For one, a container's
value_type is, in general
std::pair<const Key, Data>,
but if 
Data is null_data_type, then the value_typeis
Key,
and if
Data is
compound_data_type<Cntnr>, then the value_type is
std::pair<const Key, Cntnr>.
	Futhermore, assume that 
Cntnr is an associative container with more than a single mapping level, and let Cntnr_ be defined as
typedef	
typename Cntnr::template rebind<i>::other	Cntnr_;
i.e., the container rebound to a different mapping level.
In this case, the 
value_type of the rebound container is not the value_typeof the rebound container's iterators. 
I.e., it is not true that
typename Cntnr_::value_type is the same as
typename Cntnr_::iterator::value_type. This complication never exists for the STL's container.
no image
Iterator of a rebound type.
Multisets
	
pb_assoc does not contain a "multiset" type. The closest equivalent is mapping keys to non-negative integral types, e.g., size_t.
