This section describes genericity over different mapping-semantics. It is organized as follows.
Motivation::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".
All associative-containers in pb_assoc are parameterized by a data type. E.g., cc_hash_assoc_cntnr is parameterized as
template< typename Key, typename Data, ...> class cc_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.
Each container derives from one of the three containers in the oval of Figure Data-types as a policy .
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_Levels discusses the mechanism for these multiple views in pb_assoc
Each associative container in pb_assoc has a mapping level. The mapping level is defined by the instantiation of a container's Data parameter:
Containers can be rebound, at compile time, to different mapping levels. The compound data-type specialization basic_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< int, compound_data_type< tree_assoc_cntnr< char, null_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<1>::other t_; ((t_ &)c).insert(std::make_pair(2, 'b'));
mapping_level_example.cpp shows a more detailed example.
It is, of course, beneficial to query types for their mapping semantics.
Each container defines internally the type ms_category as its mapping-semantics tag (hopefully this name is not copyrighted by some major corporation). The possible tags, shown in Figure are the following:
Additionally, a container's mapping semantics can be queried by traits. For any container Cntnr,
ms_traits<Cntnr>::mapping_level
indicates the mapping level of the container, for example.
The STL's multimaps and multisets allow storing equivalent, non-identical keys [kleft00sets]. 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 < r_other.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_info object 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_info object.
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.
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_type is 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_type
of the rebound container's iterators. I.e., it is
pb_assoc does not contain a "multiset" type. The closest equivalent is mapping keys to non-negative integral types, e.g., size_t.