]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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] |