ceph/src/boost/libs/unordered/doc/comparison.qbk

   1 [/ Copyright 2006-2011 Daniel James.
   2  / Distributed under the Boost Software License, Version 1.0. (See accompanying
   3  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ]
   4
   5 [section:comparison Comparison with Associative Containers]
   6
   7 [table:interface_differences Interface differences.
   8     [[Associative Containers] [Unordered Associative Containers]]
   9
  10     [
  11         [Parameterized by an ordering relation `Compare`]
  12         [Parameterized by a function object `Hash` and an equivalence relation
  13             `Pred`]
  14     ]
  15     [
  16         [Keys can be compared using `key_compare` which is accessed by member function `key_comp()`,
  17          values can be compared using `value_compare` which is accessed by member function `value_comp()`.]
  18         [Keys can be hashed using `hasher` which is accessed by member function `hash_function()`,
  19          and checked for equality using `key_equal` which is accessed by member function `key_eq()`.
  20          There is no function object for compared or hashing values.]
  21     ]
  22     [
  23         [Constructors have optional extra parameters for the comparison object.]
  24         [Constructors have optional extra parameters for the initial minimum
  25             number of buckets, a hash function and an equality object.]
  26     ]
  27
  28     [
  29         [Keys `k1`, `k2` are considered equivalent if
  30             `!Compare(k1, k2) && !Compare(k2, k1)`]
  31         [Keys `k1`, `k2` are considered equivalent if `Pred(k1, k2)`]
  32     ]
  33     [
  34         [Member function `lower_bound(k)` and `upper_bound(k)`]
  35         [No equivalent. Since the elements aren't ordered `lower_bound` and
  36         `upper_bound` would be meaningless.]
  37     ]
  38     [
  39         [`equal_range(k)` returns an empty range at the position that k
  40             would be inserted if k isn't present in the container.]
  41         [`equal_range(k)` returns a range at the end of the container if
  42             k isn't present in the container. It can't return a positioned
  43             range as k could be inserted into multiple place. To find out the
  44             bucket that k would be inserted into use `bucket(k)`. But remember
  45             that an insert can cause the container to rehash - meaning that the
  46             element can be inserted into a different bucket.]
  47     ]
  48     [
  49         [`iterator`, `const_iterator` are of the bidirectional category.]
  50         [`iterator`, `const_iterator` are of at least the forward category.]
  51     ]
  52     [
  53         [Iterators, pointers and references to the container's elements are
  54             never invalidated.]
  55         [[link unordered.buckets.iterator_invalidation Iterators can
  56             be invalidated by calls to insert or rehash]. Pointers and
  57             references to the container's elements are never invalidated.]
  58     ]
  59     [
  60         [Iterators iterate through the container in the order defined by
  61             the comparison object.]
  62         [Iterators iterate through the container in an arbitrary order, that
  63             can change as elements are inserted. Although, equivalent elements
  64             are always adjacent.]
  65     ]
  66     [
  67         [No equivalent]
  68         [Local iterators can be used to iterate through individual buckets.
  69             (The order of local iterators and iterators aren't
  70             required to have any correspondence.)]
  71     ]
  72     [
  73         [Can be compared using the `==`, `!=`, `<`, `<=`, `>`, `>=` operators.]
  74         [Can be compared using the `==` and `!=` operators.]
  75     ]
  76     [
  77         []
  78         [When inserting with a hint, implementations are permitted to ignore
  79             the hint.]
  80     ]
  81     [
  82         [`erase` never throws an exception]
  83         [The containers' hash or predicate function can throw exceptions
  84             from `erase`]
  85     ]
  86 ]
  87
  88 [table:complexity_guarantees Complexity Guarantees
  89     [[Operation] [Associative Containers] [Unordered Associative Containers]]
  90     [
  91         [Construction of empty container]
  92         [constant]
  93         [O(/n/) where /n/ is the minimum number of buckets.]
  94     ]
  95     [
  96         [Construction of container from a range of /N/ elements]
  97         [O(/N/ log /N/), O(/N/) if the range is sorted with `value_comp()`]
  98         [Average case O(/N/), worst case
  99             O(/N/'''<superscript>2</superscript>''')]
 100     ]
 101     [
 102         [Insert a single element]
 103         [logarithmic]
 104         [Average case constant, worst case linear]
 105     ]
 106     [
 107         [Insert a single element with a hint]
 108         [Amortized constant if t elements inserted right after hint,
 109             logarithmic otherwise]
 110         [Average case constant, worst case linear (ie. the same as
 111             a normal insert).]
 112     ]
 113     [
 114         [Inserting a range of /N/ elements]
 115         [ /N/ log(`size()`+/N/) ]
 116         [Average case O(/N/), worst case O(/N/ * `size()`)]
 117     ]
 118     [
 119         [Erase by key, `k`]
 120         [O(log(`size()`) + `count(k)`)]
 121         [Average case: O(`count(k)`), Worst case: O(`size()`)]
 122     ]
 123     [
 124         [Erase a single element by iterator]
 125         [Amortized constant]
 126         [Average case: O(1), Worst case: O(`size()`)]
 127     ]
 128     [
 129         [Erase a range of /N/ elements]
 130         [O(log(`size()`) + /N/)]
 131         [Average case: O(/N/), Worst case: O(`size()`)]
 132     ]
 133     [
 134         [Clearing the container]
 135         [O(`size()`)]
 136         [O(`size()`)]
 137     ]
 138     [
 139         [Find]
 140         [logarithmic]
 141         [Average case: O(1), Worst case: O(`size()`)]
 142     ]
 143     [/ TODO: Average case is probably wrong. ]
 144     [
 145         [Count]
 146         [O(log(`size()`) + `count(k)`)]
 147         [Average case: O(1), Worst case: O(`size()`)]
 148     ]
 149     [
 150         [`equal_range(k)`]
 151         [logarithmic]
 152         [Average case: O(`count(k)`), Worst case: O(`size()`)]
 153     ]
 154     [
 155         [`lower_bound`,`upper_bound`]
 156         [logarithmic]
 157         [n/a]
 158     ]
 159 ]
 160
 161 [endsect]