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.
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.
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.
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.