Non-Unique Mapping Containers

This section describes the design of non-unique mapping containers (multimaps and multisets). It is organized as follows:

  1. The Main Points Section describes the main points.
  2. The Mapped Data Types and Mapped Value Types Section describes some additional types that each associative container defines.
  3. The Generics Section describes some classes for generic programming.
  4. The Compound 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:

  1. key_type- This describes the domain of the keys of the container. All associative containers define this type.
  2. 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.
  3. 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.
  4. 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.
  5. 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, is_set_type, is_multimap_type, and is_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 [boost_concept_check] and [boost_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 and iterator_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_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_interval be a class composed of an interval and a color.

Suppose one wants to store colored_interval objects 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:

  1. A map mapping interval objects to color objects. This, however, assumes that colored_interval is decomposable to, and constructible from, interval and color.
  2. 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_interval objects 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:

  1. 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.
  2. 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 Unique-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 figure shows some STL containers and the pb_assoc counterparts.

no-image
STL containers and pb_assoc counterparts.