Interface Specifics

Following are the library's interface specifics. Short Tutorial is a short tutorial, and Concepts describes some concepts.

Namespace

All code is enclosed in namespace pb_ds. Nested within this is namespace detail, which contains the parts of this library that are considered implementation details.

Containers

Associative Containers

  1. container_base - abstract base class for associative containers.
  2. Hash-based:
    1. basic_hash_table - abstract base class for hash-based containers
    2. cc_hash_table - concrete collision-chaining hash-based containers
    3. gp_hash_table - concrete (general) probing hash-based containers
  3. Tree-based:
    1. basic_tree - abstract base class for tree and trie based containers
    2. tree - concrete base class for tree-based containers
    3. trie - concrete base class for trie-based containers
  4. List-based:
    1. list_update - singly-linked list with update-policy container

Priority Queues

  1. priority_queue - priority queue

Container Tags and Traits

Container Tags

Common

  1. container_tag - base class for data structure tags

Associative-Containers

  1. associative_container_tag - base class for associative-container data structure tags
  2. basic_hash_tag - base class for hash-based structure tags
  3. cc_hash_tag - collision-chaining hash structure tag
  4. gp_hash_tag - (general) probing hash structure tag
  5. basic_tree_tag - base class for tree-like structure tags
  6. tree_tag - base class for tree structure tags
  7. rb_tree_tag - red-black tree structure tag/li>
  8. splay_tree_tag - splay tree structure tag
  9. ov_tree_tag - ordered-vector tree structure tag
  10. trie_tag - trie structure tag
  11. pat_trie_tag - PATRICIA trie structure tag
  12. list_update_tag - list (with updates) structure tag

Priority-Queues

  1. priority_queue_tag - base class for priority-queue data structure tags
  2. pairing_heap_tag - pairing-heap structure tag.
  3. binomial_heap_tag - binomial-heap structure tag
  4. rc_binomial_heap_tag - redundant-counter binomial-heap (i.e., a heap where binomial trees form a sequence that is similar to a de-amortized bit-addition algorithm) structure tag
  5. binary_heap_tag - binary heap (based on an array or an array of nodes) structure tag
  6. thin_heap_tag - thin heap (an alternative [kt99fat_heaps] to Fibonacci heap) data structure tag.

Invalidation-Guarantee Tags

  1. basic_invalidation_guarantee - weakest invalidation guarantee
  2. point_invalidation_guarantee - stronger invalidation guarantee
  3. range_invalidation_guarantee - strongest invalidation guarantee

Container Traits

  1. container_traits - traits for determining underlying data structure properties

Container Policy Classes

Hash Policies

Hash and Probe Policies

  1. Hash Functions:
    1. null_hash_fn - type indicating one-step range-hashing
  2. Range-Hashing Functions:
    1. Sample range-hashing function - interface required of a range-hashing functor
    2. direct_mask_range_hashing - (bit) mask-based range hashing functor
    3. direct_mod_range_hashing - modulo-based range hashing functor
  3. Probe Functions:
    1. Sample probe function - interface required of a probe functor
    2. null_probe_fn - type indicating one-step ranged-probe
    3. linear_probe_fn - linear-probe functor
    4. quadratic_probe_fn- quadratic-probe functor
  4. Ranged-Hash Functions:
    1. Sample ranged-hash function - interface required of a ranged-hash functor
  5. Ranged-Probe Functions:
    1. Sample ranged-probe function - interface required of a ranged-probe functor

Resize Policies

  1. Resize Policies:
    1. Sample resize policy - interface required of a resize policy
    2. hash_standard_resize_policy - standard resize policy
  2. Size Policies:
    1. Sample size policy - interface required of a size policy
    2. hash_exponential_size_policy - exponential size policy (typically used with (bit) mask range-hashing)
    3. hash_prime_size_policy - prime size policy (typically used with modulo range-hashing)
  3. Trigger Policies:
    1. Sample trigger policy - interface required of a trigger policy
    2. hash_load_check_resize_trigger - trigger policy based on load checks
    3. cc_hash_max_collision_check_resize_trigger - trigger policy based on collision checks

Tree Policies

Tree Node-Update Policies

  1. Sample node updater policy - interface required of a tree node-updating functor
  2. null_tree_node_update - null policy indicating no updates are required
  3. tree_order_statistics_node_update - updater enabling order statistics queries

Trie Policies

Trie Element-Access Traits

  1. Sample element-access traits - interface required of element-access traits
  2. string_trie_e_access_traits - String element-access traits

Trie Node-Update Policies

  1. Sample node updater policy - interface required of a trie node updater
  2. null_trie_node_update - null policy indicating no updates are required
  3. trie_prefix_search_node_update - updater enabling prefix searches
  4. trie_order_statistics_node_update - updater enabling order statistics queries

List Policies

List Update Policies

  1. Sample list update policy - interface required of a list update policy
  2. move_to_front_lu_policy - move-to-front update algorithm
  3. counter_lu_policy - counter update algorithm

Mapped-Type Policies

  1. null_mapped_type - data policy indicating that a container is a "set"

Exceptions

  1. container_error - base class for all policy-based data structure errors
  2. insert_error
  3. join_error
  4. resize_error