Tutorial (original) (raw)
Short Tutorial
Following is a short tutorial illustrating the main points of pb_ds. Concepts describes and summarizes some concepts.
Associative Containers
Basic Use
For the most part, pb_ds's containers have the same interface as the STL's, except for the names used for the container classes themselves. For example, this shows basic operations on a collision-chaining hash-based container:
cc_hash_table<**int**, **char**> c;
c[2] = 'b';
assert(c.find(1) == c.end());
The container is called cc_hash_table as opposed to unordered_map, since "unordered map" does not necessarily mean a hash-based map (as the STL implicitly implies). For example, list-based associative containers, which are very useful for the construction of "multimaps" (seeAssociative-Container Performance Tests::Observations::Mapping-Semantics Considerations), are also unordered. It is also not calledhash_map since there are more ways than one to implement hash tables.
This snippet shows a red-black tree based container:
tree<**int**, **char**> c;
c[2] = 'b';
assert(c.find(2) != c.end());
The container is called tree as opposed to map, since "map" doesn't say that much.
Most of the STL's familiar methods are unchanged.E.g., being, end, size,empty, and clear, do just the same as is customary. Associative-Container Examples::Basic use, and especially basic_map.cc, show examples of this.
This isn't to say that things are exactly as one would expect, given the container requirments and interfaces in the C++ standard.
The names of containers' policies and policy accessors are different than those of the STL. For example, if C is some type of hash-based container, then
C::hash_fn
gives the type of its hash functor, and if
c
is some hash-based container object, then
c.get_hash_fn()
will return a reference to its hash-functor object.
Similarly, if C is some type of tree-based container, then
C::cmp_fn
gives the type of its comparison functor, and if
c
is some tree-based container object, then
c.get_cmp_fn()
will return a reference to its comparison-functor object.
It would be nice to give names consistent with those in the existing C++ standard (inclusive of TR1). Unfortunately, these standard containers don't consistently name types and methods. For example, std::tr1::unordered_map useshasher for the hash functor, but std::map useskey_compare for the comparison functor. Also, we could not find an accessor for std::tr1::unordered_map's hash functor, but std::map uses compare for accessing the comparison functor.
Instead, pb_ds attempts to be internally consistent, and uses standard-derived terminology if possible.
Another source of difference is in scope: pb_ds contains more types of associative containers than the STL, and more opportunities to configure these new containers, since different types of associative containers are useful in different settings (see Associative-Container Performance Tests::Observations::Underlying Data-Structure Families).
pb_ds contains different classes for hash-based containers, tree-based containers, trie-based containers, and list-based containers. Inteface::Containers::Associative Containers lists the containers. Design::Associative Containers::Hash-Based Containers, Design::Associative Containers::Tree-Based Containers, Design::Associative Containers::Trie-Based Containers, and Design::Associative Containers::List-Based Containers, explain some more about these types of containers, respectively.
Since associative containers share parts of their interface, they are organized as a class hierarchy; it is shown in FigureClass hierarchy.
Class hierarchy.
Each type or method is defined in the most-common ancestor in which it makes sense:basic_map.cc shows an example of most of the associative-container types.
For example, all associative containers support iteration. Consequently, container_base has the interface:
template<...> class container_base { ...
public: ...
const_iterator
begin() **const**;
iterator
begin();
const_iterator
end() **const**;
iterator
end();
...};
and so all associative containers inherent this method. Conversely, both collision-chaining and (general) probing hash-based associative containers have a hash functor, sobasic_hash_table has the interface:
template<...> class basic_hash_table : public container_base { ...
public: ...
const hash_fn&
get_hash_fn() const;
hash_fn&
get_hash_fn();
...};
and so all hash-based associative containers inherit the same hash-functor accessor methods.
This is discussed further in Design::Associative Containers::Data-Structure Genericity.
Configuring Associative Containers
In general, each of pb_ds's containers is parametrized by more policies than those of the STL's. For example, the STL's hash-based container is parametrized as follows:
template< **typename** Key, **typename** Mapped, **typename** Hash, **typename** Pred, **typename** Allocator, **bool** Cache_Hashe_Code> class unordered_map;
and so can be configured by key type, mapped type, a functor that translates keys to unsigned integral types, an equivalence predicate, an allocator, and an indicator whether to store hash values with each entry. pb_ds's collision-chaining hash-based container is parametrized as
template< **typename** Key, **typename** Mapped, **typename** Hash_Fn, **typename** Eq_Fn, **typename** Comb_Hash_Fn, **typename** Resize_Policy **bool** Store_Hash **typename** Allocator> class cc_hash_table;
and so can be configured by the first four types ofstd::tr1::unordered_map, then a policy for translating the key-hash result into a position within the table, then a policy by which the table resizes, an indicator whether to store hash values with each entry, and an allocator (which is typically the last template parameter in STL containers).
Nearly all policy parameters have default values, so this need not be considered for casual use. It is important to note, however, that hash-based containers' policies can dramatically alter their performance in different settings, and that tree-based containers' policies can make them useful for other purposes than just look-up.
Design::Associative Containers::Hash-Based Containers, Design::Associative Containers::Tree-Based Containers, Design::Associative Containers::Trie-Based Containers, and Design::Associative Containers::List-Based Containers, explain some more about configuring hash based, tree based, trie based, and list base containers, respectively. Interface::Container Policy Classes shows the different policy classes for configuring associative containers. Examples::Hash-Based Containers, Examples::Tree-Like-Based Containers, and Examples::Trie-Based Containers show examples for this.
Determining Containers' Attributes
Associative-containers' underlying data structures obviously affect their performance; Unfortunately, they can also affect their interface. When manipulating generically associative containers, it is often useful to be able to statically determine what they can support and what the cannot. (This was discussed in Motivation::Associative Containers::Data-Structure Genericity.)
Happily, the STL provides a good solution to a similar problem - that of the different behavior of iterators. IfIt is an iterator, then
typename std::iterator_traits::iterator_category
is one of a small number of pre-definedstructs, and,
typename std::iterator_traits::value_type
is the value type to which the iterator "points".
Similarly, in pb_ds, if C is an associative container, then
typename container_traits::container_category
is one of a small number of pre-defined
struct
s, each one corresponding to a class in Figure Class hierarchy. These tags are listed inInterface::Associative Containers::Data-Structure Tags and Traits::Data-Structure Tags::Associative-Containers; Design::Associative Containers::Data-Structure Tags and Traits explains this further; Design::Associative Containers::Data-Structure Tags and Traits::Data-structure tag class hierarchy shows a class diagram.
In most cases, however, the exact underlying data structure is not really important, but only one of its attributes: whether it guarantees storing elements by key order, for example. For this one can use
typename container_traits::order_preserving
This is described further in Design::Data-Structure Genericity; assoc_container_traits.cc shows an example of querying containers' attributes.
Point-Type and Range-Type Methods and Iterators
(This subsection addresses points from Motivation::Associative Containers::Differentiating between Iterator Types.)
pb_ds differentiates between two types of methods and iterators: point-type, and range-type. For example,find and insert are point-type methods, since they each deal with a specific element; their returned iterators are point-type iterators. begin andend are range-type methods, since they are not used to find a specific element, but rather to go over all elements in a container object; their returned iterators are range-type iterators.
Most containers store elements in an order that is determined by their interface. Correspondingly, it is fine that their point-type iterators are synonymous with their range-type iterators. For example, in the following snippet
std::for_each(c.find(1), c.find(5), foo);
two point-type iterators (returned by
find
) are used for a range-type purpose - going over all elements whose key is between 1 and 5.
Conversely, the above snippet makes no sense for self-organizing containers - ones that order (and reorder) their elements by implementation. It would be nice to have a uniform iterator system that would allow the above snippet to compile only if it made sense.
This could trivially be done by specializingstd::for_each for the case of iterators returned bystd::tr1::unordered_map, but this would only solve the problem for one algorithm and one container. Fundamentally, the problem is that one can loop using a self-organizing container's point-type iterators.
pb_ds's containers define two families of iterators: const_point_iterator andpoint_iterator are the iterator types returned by point-type methods; const_iterator anditerator are the iterator types returned by range-type methods.
class <- some container -> { public: ...
**typedef** _<- something ->_ const_iterator;
**typedef** _<- something ->_ iterator;
**typedef** _<- something ->_ const_point_iterator;
**typedef** _<- something ->_ point_iterator;
...public: ...
const_iterator begin () **const**;
iterator begin();
const_point_iterator find(...) **const**;
point_iterator find(...);};
Design::Associative Containers::Data-Structure Genericity::Point-Type and Range-Type Methods and Iterators discusses the relationship between point-type and range-type iterators in general; for containers whose interface defines sequence order, however, it is very simple: point-type and range-type iterators are exactly the same, which means that the above snippet will compile if it is used for an order-preserving associative container.
For self-organizing containers, however, (hash-based containers as a special example), the preceding snippet will not compile, because their point-type iterators do not supportoperator++.
In any case, both for order-preserving and self-organizing containers, the following snippet will compile:
typename Cntnr::point_iterator it = c.find(2);
because a range-type iterator can always be converted to a point-type iterator.
Design::Associative Containers::Data-Structure Genericity::Point-Type and Range-Type Methods and Iterators discusses this further.
Motivation::Associative Containers::Differentiating between Iterator Types also raised the point that a container's iterators might have different invalidation rules concerning their de-referencing abilities and movement abilities. This now corresponds exactly to the question of whether point-type and range-type iterators are valid. As explained in Determining Containers' Attributes, container_traits allows querying a container for its data structure attributes. The iterator-invalidation guarantees are certainly a property of the underlying data structure, and so
container_traits::invalidation_guarantee
gives one of three pre-determined types that answer this query. This is explained further in Design::Associative Containers::Data-Structure Genericity::Point-Type and Range-Type Methods and Iterators.
Distinguishing between Maps and Sets
Anyone familiar with the STL knows that there are four kinds of associative containers: maps, sets, multimaps, and multisets. Basic Use discussed how to use maps, i.e. containers that associate each key to some data.
Sets are associative containers that simply store keys - they do not map them to anything. In the STL, each map class has a corresponding set class. E.g.,std::map<int**, char> maps eachint** to a char, butstd::set<int**, char> simply storesint**s. In pb_ds, however, there are no distinct classes for maps and sets. Instead, an associative container's Mapped template parameter is a policy: if it is instantiated by null_mapped_type, then it is a "set"; otherwise, it is a "map". E.g.,
cc_hash_table<**int**, **char**>
is a "map" mapping each
int
value to a
char
, but
cc_hash_table<**int**, null_mapped_type>
is a type that uniquely stores
int
values.
Once the Mapped template parameter is instantiated by null_mapped_type, then the "set" acts very similarly to the STL's sets - it does not map each key to a distinct null_mapped_type object. Also, , the container's value_type is essentially its key_type - just as with the STL's sets. For a simple example, see basic_set.cc .
The STL's multimaps and multisets allow, respectively, non-uniquely mapping keys and non-uniquely storing keys. As discussed in Motivation::Associative Containers::Alternative to Multiple Equivalent Keys, the reasons why this might be necessary are 1) that a key might be decomposed into a primary key and a secondary key, 2) that a key might appear more than once, or 3) any arbitrary combination of 1)s and 2)s. Correspondingly, one should use 1) "maps" mapping primary keys to secondary keys, 2) "maps" mapping keys to size types, or 3) any arbitrary combination of 1)s and 2)s. Thus, for example, anstd::multiset<**int**> might be used to store multiple instances of integers, but using pb_ds's containers, one might use
tree<**int**, size_t>
i.e., a "map" of
int
s to
size_t
s.
Associative-Container Examples::"Multimaps" and "Multisets" shows some simple examples.
These "multimaps" and "multisets" might be confusing to anyone familiar with the STL's std::multimap andstd::multiset, because there is no clear correspondence between the two. For example, in some cases where one uses std::multiset in the STL, one might use in pb_ds a "multimap" of "multisets" - i.e., a container that maps primary keys each to an associative container that maps each secondary key to the number of times it occurs.
When one uses a "multimap," one should choose with care the type of container used for secondary keys. This is further explained in Associative-Container Performance Tests::Observations::Mapping-Semantics Considerations.
Priority Queues
Basic Use
pb_ds's priority_queue container is similar to the STL's in interface. For example:
priority_queue<**int**> p;
p.push(2); p.push(4); p.push(1);
assert(p.top() == 4);
p.pop();
assert(p.top() == 2);
assert(p.size() == 2); assert(!p.empty());
Configuring Priority Queues
As opposed to associative containers, priority queues have relatively few configuration options. The priority queue is parametrized as follows:
template< **typename** Value_Type, **typename** Cmp_Fn, **typename** Tag, **typename** Allocator> class priority_queue;
The Value_Type, Cmp_Fn, andAllocator parameters are the container's value type, comparison-functor type, and allocator type, respectively; these are very similar to the STL's priority queue. TheTag parameter is different: there are a number of pre-defined tag types corresponding to binary heaps, binomial heaps, etc., and Tag should be instantiated by one of them. Interface::Data-Structure Tags and Traits::Data Structure Tags::Priority-Queues lists the possible types, Priority-Queue Design explains this further, and basic_priority_queue.cc shows an example.
Note that as opposed to the STL's priority queue, priority_queue is not a sequence-adapter; it is a regular container.
Supporting More Operations
priority_queue'spush method returns a point-type iterator, which can be used for modifying or erasing arbitrary values. For example:
priority_queue<**int**> p;
priority_queue<**int**>::point_iterator it = p.push(3);
p.modify(it, 4);
These types of operations are necessary for making priority queues useful for different applications, especially graph applications. Priority-Queue Examples::Cross-Referencing gives some examples.
Determining Container Attributes
Similarly to container_traits (described in Associative Containers::Determining Containers' Attributes), container_traits can be used to statically determine priority-queues' attributes:
container_traits::container_category
is one of a small number of predefined tag structures that identifies the underlying data structure, and
container_traits::invalidation_guarantee
is its invalidation guarantee. Invalidation guarantees are especially important regarding priority queues, since inpb_ds's design, iterators are practically the only way to manipulate them.
Design::Priority Queues::Traits discusses this further. Priority-Queue Examples::Generics shows an example.