From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libstdc++-v3/doc/html/ext/pb_ds/interface.html | 446 +++++++++++++++++++++++++ 1 file changed, 446 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/interface.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/interface.html') diff --git a/libstdc++-v3/doc/html/ext/pb_ds/interface.html b/libstdc++-v3/doc/html/ext/pb_ds/interface.html new file mode 100644 index 000000000..a48a8bbad --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/interface.html @@ -0,0 +1,446 @@ + + + + + + +Interface + + + + +
+

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. + +
  2. Hash-based: + +
      +
    1. basic_hash_table + - abstract base class for hash-based + containers
      2. + +
    2. cc_hash_table + - concrete collision-chaining hash-based + containers
      3. + +
    3. gp_hash_table + - concrete (general) probing hash-based + containers
      4. +
    +
    3. + +
  3. Tree-based: + +
      +
    1. basic_tree + - abstract base class for tree and trie based + containers
      2. + +
    2. tree + - concrete base class for tree-based + containers
      3. + +
    3. trie + - concrete base class for trie-based + containers
      4. +
    +
    4. + +
  4. List-based: + +
      +
    1. list_update - + singly-linked list with update-policy container
      2. +
    +
    5. +
+ +

Priority + Queues

+ +
    +
  1. priority_queue + - priority queue
    2. +
+
+ +

Container Tags and + Traits

+ +

Container Tags

+ +

Common

+ +
    +
  1. container_tag - + base class for data structure tags
    2. +
+ +

Associative-Containers

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

Priority-Queues

+ +
    +
  1. priority_queue_tag - base + class for priority-queue data structure tags
    2. + +
  2. pairing_heap_tag - + pairing-heap structure tag.
    3. + +
  3. binomial_heap_tag + - binomial-heap structure tag
    4. + +
  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. + +
  5. binary_heap_tag - + binary heap (based on an array or an array of nodes) + structure tag
    6. + +
  6. thin_heap_tag - thin + heap (an alternative [kt99fat_heaps] to + Fibonacci heap) data structure tag.
    7. +
+ +

Invalidation-Guarantee + Tags

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

Container + Traits

+ +
    +
  1. container_traits - + traits for determining underlying data structure + properties
    2. +
+
+ +

Container Policy Classes

+ +

Hash Policies

+ +

Hash and Probe Policies

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

Resize Policies

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

Tree Policies

+ +

Tree Node-Update Policies

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

Trie Policies

+ + +

Trie Element-Access Traits

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

Trie Node-Update Policies

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

List Policies

+ +

List Update Policies

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

Mapped-Type Policies

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

Exceptions

+ + +
    +
  1. container_error + - base class for all policy-based data structure errors
    2. + +
  2. insert_error
    3. + +
  3. join_error
    4. + +
  4. resize_error
    5. +
+ +
+ + -- cgit v1.2.3