	
	
	
Non-Unique Mapping Containers
	This section describes the design of non-unique mapping containers
(multimaps and multisets). It is organized as follows:
	
 The #generalMain Points  Section describes the main points.
	
	
	The 
#typesMapped Data Types and Mapped Value Types  Section
	describes some additional types that each associative container defines.
	
	
 The genericsGenerics  Section describes some classes for
	generic programming.
	
	
 The #compound_keysCompound Keys  Section describes an
	alternative to the STL's design of using equivalent, non-identical, keys.
	
Main Points 
	In 
pb_assoc, all associative containers have a unique-key design;
each container can have at most one entry for any given key. Multimaps
are designed as maps from keys to sets; multisets are designed as maps from
keys to non-negative integral types.
Mapped Data Types and Mapped Value Types 
    The STL's design of associative containers elegantly allows
generic manipulation of containers: each container defines
data_type as the domain of its data;
value_type as the domain of its relationship. This is not
directly applicable in 
pb_assoc. Consider
a multimap mapping 
Key objects to
Data_Coll objects, where
Data_Coll is some set-type of Data.
Then should the multimap's 
value_type should be
std::pair<Key, Data> or
std::pair<Key, Data_Coll>, for example?.
	
pb_assoc addresses this by differentiating
between the 
domain and the type of relationship.
All associative containers define 
value_type as
the relationship's 
domain, and mapped_value_type as its
type. E.g., both
map types and multimap types may share the same 
value_type,
if they map from the same key domain to
the same data domain. In this case, however, they will not share
the same 
mapped_value_type, since the multimap type maps from the
key domain to the domain of collections of data. The same
differentiation exists between the domain and type of mapped data.
	In general, the following types describe the relationships
of each associative container:
	
		
key_type- This describes the domain of the keys of the container. All
		associative containers define this type.
	
	
		
data_type- This describes the domain of the data mapped by a
		key. It is identical to the 
data_type defined by std::map, std::set,
		
std::multimap, and std::multiset. Sets and multisets do not
		define this type, since they map each key to the abstract fact that the key is
		stored by them.
	
	
		
mapped_data_type- This describes the type of the data mapped by
		a key. For maps, this is the same as 
data_type. For multimaps, this is
		not the same as 
data_type; The mapped_data_type describes the
		collection of 
data_types used. Sets do not define this type. For
		multisets, the 
mapped_data_type describes the unsigned integral type
		used to indicate the number of occurrences of a key.
	
	
		
value_type- This describes the domain of relationships store in
		a container. It is identical to the 
value_type defined by std::map,
		
std::set, std::multimap, and std::multiset.
	
	
		
mapped_value_type- This describes the type of relationships
		store in a container. It consists of information on the 
key_type and mapped_data_type		(except for sets).
	
	The following table defines the above types for a map
mapping from 
Key types to Data types:
	
		
type 		
Description / Definition 	
	
		
key_type		
		
Key		
	
	
		
data_type		
		
Data		
	
	
		
mapped_data_type		
		
Data		
	
	
		
value_type		
		
std::pair<const Key, Data>		
	
	
		
mapped_value_type		
		
std::pair<const Key, Data>		
	
The following table defines the above types for a
set storing 
Key types:
	
		
type 		
Description / Definition 	
	
		
key_type		
		
Key		
	
	
		
data_type		
		
- 	
	
		
mapped_data_type		
		
- 	
	
		
value_type		
		
const Key		
	
	
		
mapped_value_type		
		
const Key		
	
The following table defines the above types for a multimap
mapping from 
Key types to Data_Coll<Data>types, where 
Data_Coll<Data>is a set of 
Data types:
	
		
type 		
Description / Definition 	
	
		
key_type		
		
Key		
	
	
		
data_type		
		
Data		
	
	
		
mapped_data_type		
		
Data_Coll<Data>		
	
	
		
value_type		
		
std::pair<const Key, Data>		
	
	
		
mapped_value_type		
		
std::pair<const Key, Data_Coll<Data> >		
	
The following table defines the above types for a multiset
storing 
Key types:
	
		
type 		
Description / Definition 	
	
		
key_type		
		
Key		
	
	
		
data_type		
		
- 	
	
		
mapped_data_type		
		
size_type		
	
	
		
value_type		
		
std::pair<const Key, size_type>		
	
	
		
mapped_value_type		
		
const Key		
	
	The above types allow to define simple invariants on the interfaces of
containers. For example, each container defines both an 
insert method
which takes a const reference to a 
value_type, and an insert method
which takes a const reference to a 
mapped_value_type. Containers for
which both these types are synonymous (
i.e., maps and sets), consequently
have a
single 
insert method. Containers for which these types are distinct (i.e.,
multimaps and multisets), use overloading.
Generics 
	
pb_assoc contains a number of utility classes to ease generic
programming.
	There are four container-type identifiers, 
is_map_type.htmlis_map_type ,
is_set_type.htmlis_set_type , is_multimap_type.html	
is_multimap_type , and is_multiset_type.htmlis_multiset_type .
Given a container 
T, for example, it is possible to query at compile
time whether it is a a multimap type by writing 
is_multimap_type<T>::value.
(This is probably very similar to [
references.html#boost_concept_checkboost_concept_check ]
and [
references.html#boost_type_traitsboost_type_traits ].)
	In some cases, it is necessary, given a container and an iterator, to query the
iterator' 
value_type to the container's value_type and mapped_value_type.
The classes
is_mapped_value_iterator.htmlis_mapped_value_iterator and 
iterator_key.htmliterator_key  can be used for this.
	The STL's 
std::multimap and std::multiset allow iterating
over all 
value_types stored in them, which is convenient. The library
provides a 
value_iterators.htmlvalue_iterator  for this.
This is an iterator adapter over the containers' native iterators.
Compound Keys 
	The STL allows using equivalent, non-identical, keys.
For example, let 
interval be a line-interval class,
color be a
color type, 
thickness be a thickness type, and colored_intervalbe a class composed of an 
interval and a color.
	Suppose one wants to store 
colored_intervalobjects using a comparison predicate ignoring colors. Then
in the STL's design, one would use
multiset<colored_interval>; in pb_assoc's design,
one would use one of the following:
	
		A map mapping 
interval objects to
color objects. This, however, assumes that
colored_interval is decomposable to, and constructible from,
interval and color.
	
	
		A map mapping 
colored_interval objects to
color objects. In this (less efficient) case, a colored_interval object
is a "representative" of all colored intervals with the same endpoints.
	
	Suppose one wants to map 
colored_intervalobjects to 
thickness objects
using a comparison predicate ignoring colors. Then
in the STL's design, one would use
multimap<colored_interval, thickness>; in pb_assoc's design,
one would use one of the following:
	
 A map mapping interval objects to
std::pair<color, thickness> objects. This, however, assumes that
colored_interval is decomposable to, and constructible from,
interval and color.
	
	
 A map mapping colored_interval objects to
std::pair<color, thickness> objects. In this (less efficient) case, a colored_interval object
is a "representative" of all colored intervals with the same endpoints.
	
(From the above, it is apparent that the STL's design has an advantage
over 
pb_assoc's design in terms of convenience. Nonethless, there
are efficiency limitation in the STL's design (see
motivation.html#unique_keyUnique-Key Design for Multimaps and Multisets ).)
	The above example, using intervals, colors and thicknesses, can be generalized.
Let
key_unique_part be a unique part of some key
(
e.g., interval in the above),
key_non_unique_part be a non-unique part of some key
(
e.g., color in the above),
key be some key composed of unique and non-uniqe parts
(
e.g., colored_interval in the above),
and
data be some data
(
e.g., thickness in the above).
Then the 
#stl_to_pb_assoc_non_unique_mappingfigure shows some
STL containers and the 
pb_assoc counterparts.
no-image 
STL containers and 
pb_assoc counterparts.
