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] 162