Concepts

+ +

Point and Range Methods and + Iterators

+ +

A point-type iterator is an iterator that refers to a + specific element, e.g. as returned through an + associative-container's find method; a range-type + iterator is an iterator that is used to go over a sequence of + elements, e.g., as returned by a container's + find method. A point-type method is a method that + returns a point-type iterator; a range-type method is a method + that returns a range-type iterator.

+ +

For most containers, these types are synonymous; for + self-organizing containers, such as hash-based containers or + priority queues, these are inherently different (in any + implementation, including that of the STL), but in + pb_ds this is made explicit - they are distinct + types.

+ + +

Invalidation Guarantees

+ +

If one manipulates a container object, then iterators + previously obtained from it can be invalidated. In some cases a + previously-obtained iterator cannot be de-referenced; in other + cases, the iterator's next or previous element might have + changed unpredictably. This corresponds exactly to the question + whether a point-type or range-type iterator (see previous + concept) is valid or not. In pb_ds one can query a + container (in compile time) what are its invalidation + guarantees.

+ +

Primary and Secondary Keys + and Associative Containers

+ +

In pb_ds there are no associative containers which + allow multiple values with equivalent keys (such as the STL's + std::multimap, for example). Instead, one maps the + unique part of a key - the primary key, into an + associative-container of the (originally) non-unique parts of + the key - the secondary key. A primary associative-container is + an associative container of primary keys; a secondary + associative-container is an associative container of secondary + keys.

+ + +

Null Policy Classes

+ +

Associative containers are typically parametrized by + various policies. For example, a hash-based associative + container is parametrized by a hash-functor, transforming each + key into an non-negative numerical type. Each such value is + then further mapped into a position within the table. The + mapping of a key into a position within the table is therefore + a two-step process.

+ +

In some cases, instantiations are redundant. For + example, when the keys are integers, it is possible to use a + redundant hash policy, which transforms each key into + its value.

+ +

In some other cases, these policies are irrelevant. + For example, a hash-based associative container might transform + keys into positions within a table by a different method than + the two-step method described above. In such a case, the hash + functor is simply irrelevant.

+ +

pb_ds uses special pre-defined "null policies" + classes for these cases. Some null policies in pb_ds + are:

+ +

A "set" in pb_ds, for example, is an associative + container with its Data_Parameter instantiated by + null_mapped_type. + Design::Tree-Based + Containers::Node Invariants explains another case where a + null policy is needed.