1 /******************************************************************************
2 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/multimap.hpp 2055 2017-05-13 19:35:47Z jmmcg $
3 **
4 ** Copyright (C) 2004 by J.M.McGuiness, coder@hussar.me.uk
5 **
6 ** This library is free software; you can redistribute it and/or
7 ** modify it under the terms of the GNU Lesser General Public
8 ** License as published by the Free Software Foundation; either
9 ** version 2.1 of the License, or (at your option) any later version.
10 **
11 ** This library is distributed in the hope that it will be useful,
12 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** Lesser General Public License for more details.
15 **
16 ** You should have received a copy of the GNU Lesser General Public
17 ** License along with this library; if not, write to the Free Software
18 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 #pragma once
22
23 #include <algorithm>
24 #include <functional>
25 #include <vector>
26
27 namespace jmmcg { namespace rapid_insert_lookup {
28
29 /**
30 This collection implementation is efficient when the `inserts()` to the collection come
31 in blocks, then the lookups (`find()` or `operator[]()`) in blocks, then the `inserts(...)` again.
32 This is because the collection only sorts itself when it is unsorted and a lookup occurs.
33 Non-unique keys are allowed, and the groups of non-unique keys are adjacent (after sorting) then the range of the "unique" key is multiple values.
34
35 The complexity is (assuming default container of `std::vector`, which affects these complexities):
36 -# Copy: O(n), worst-case.
37
38 More notes:
39 ===========
40 -# After sorting, non-unique keys are guaranteed to be adjacent in the multimap.
41 -# The base container can be pretty much any STL container. The obvious candidates are `std::vector` or `std:list`. The choice will affect the complexities above. The advantage of `std::vector` over `std::list` is locality of reference: The data elements are guaranteed to be local to each other, unlike `std::list`. Alternatively `std:list` has better complexity than `std::vector` for some of the operations. Choose wisely.
42 */
43 template<typename _Key,typename _Val,typename _Pred=std::less<_Key>,typename _Cont=std::vector<std::pair<_Key,_Val> > >
44 class multimap {
45 public:
46 typedef _Cont base_container;
47 typedef typename base_container::allocator_type allocator_type;
48 typedef _Key key_type;
49 typedef _Val mapped_type;
50 typedef _Pred key_compare;
51 typedef std::pair<const key_type,mapped_type> value_type;
52 typedef typename base_container::difference_type difference_type;
53 typedef typename base_container::reference reference;
54 typedef typename base_container::const_reference const_reference;
55 typedef typename base_container::size_type size_type;
56 typedef typename base_container::const_iterator const_iterator;
57 typedef typename base_container::iterator iterator;
58 typedef typename base_container::reverse_iterator reverse_iterator;
59 typedef typename base_container::const_reverse_iterator const_reverse_iterator;
60 typedef std::pair<iterator,bool> InsertItr_;
61
62 explicit __stdcall multimap(const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
63 __stdcall multimap(const size_type,const value_type &v=value_type(),const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
64 __stdcall multimap(const multimap &) FORCE_INLINE;
65 __stdcall multimap(const const_iterator &,const const_iterator &,const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
66 __stdcall ~multimap(void) FORCE_INLINE;
67
68 multimap & __fastcall operator=(const multimap &m) FORCE_INLINE;
69
70 const_iterator __fastcall begin(void) const noexcept(true) FORCE_INLINE;
71 iterator __fastcall begin(void) noexcept(true) FORCE_INLINE;
72 const_reverse_iterator __fastcall rbegin(void) const noexcept(true) FORCE_INLINE;
73 reverse_iterator __fastcall rbegin(void) noexcept(true) FORCE_INLINE;
74 const_iterator __fastcall end(void) const noexcept(true) FORCE_INLINE;
75 iterator __fastcall end(void) noexcept(true) FORCE_INLINE;
76 const_reverse_iterator __fastcall rend(void) const noexcept(true) FORCE_INLINE;
77 reverse_iterator __fastcall rend(void) noexcept(true) FORCE_INLINE;
78
79 const size_type __fastcall size(void) const noexcept(true) FORCE_INLINE;
80 const size_type __fastcall max_size(void) const noexcept(true) FORCE_INLINE;
81 bool __fastcall empty(void) const noexcept(true) FORCE_INLINE;
82 void __fastcall clear(void) FORCE_INLINE;
83 void __fastcall resize(const size_type,const value_type &v=value_type()) FORCE_INLINE;
84 void __fastcall reserve(const size_type) FORCE_INLINE;
85
86 allocator_type __fastcall get_allocator(void) const FORCE_INLINE;
87
88 /**
89 Insert: (with `insert()`) constant time. (But unsorts the multimap.)
90 Allows the insertion of multiple keys with the same value, but different referents.
91 */
92 InsertItr_ __fastcall insert(const value_type &) FORCE_INLINE;
93 /**
94 Insert: (with `insert()`) constant time. (But unsorts the multimap.)
95 Allows the insertion of multiple keys with the same value, but different referents.
96 */
97 iterator __fastcall insert(const iterator &,const value_type &) FORCE_INLINE;
98 /**
99 Insert: (with `insert()`) constant time. (But unsorts the multimap.)
100 Allows the insertion of multiple keys with the same value, but different referents.
101 */
102 void __fastcall insert(const const_iterator &,const const_iterator &) FORCE_INLINE;
103
104 /**
105 Erase: O(n).
106 */
107 iterator __fastcall erase(const iterator &) FORCE_INLINE;
108 /**
109 Erase: O(n).
110 */
111 iterator __fastcall erase(const iterator &,const iterator &) FORCE_INLINE;
112 /**
113 Erase: O(nlog(n)).
114 All keys with same value are erased. Collection remains sorted.
115 */
116 const size_type __fastcall erase(const key_type &) FORCE_INLINE;
117
118 /**
119 Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not.
120 Will only insert the key if it is not in the map, i.e. it will ensure keys are unique, but will be slower.
121 Are guaranteed to return the first key if they are not unique in the multimap.
122 */
123 mapped_type & __fastcall operator[](const key_type &) FORCE_INLINE;
124
125 /**
126 Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not.
127 Are guaranteed to return the first key if they are not unique in the multimap.
128 */
129 const_iterator __fastcall find(const key_type &) const FORCE_INLINE;
130 /**
131 Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not.
132 Are guaranteed to return the first key if they are not unique in the multimap.
133 */
134 iterator __fastcall find(const key_type &) FORCE_INLINE;
135
136 private:
137 class value_compare : public std::binary_function<value_type,value_type,bool> {
138 public:
139 constexpr value_compare(void) noexcept(true) FORCE_INLINE
140 : comp() {
141 }
142
143 bool __fastcall operator()(const value_type &X,const value_type &Y) const FORCE_INLINE {
144 return comp(X.first, Y.first);
145 }
146
147 private:
148 const _Pred comp;
149
150 friend class multimap<_Key,_Val,_Pred,_Cont>;
151
152 void __fastcall operator=(const value_compare &)=delete;
153 };
154
155 mutable base_container cont;
156 mutable bool is_sorted;
157
158 void __fastcall sort(void) const FORCE_INLINE;
159 void __fastcall sort(void) FORCE_INLINE;
160 const_iterator __fastcall find_first_key(const const_iterator &) const FORCE_INLINE;
161 iterator __fastcall find_first_key(const iterator &) const FORCE_INLINE;
162 };
163
164 /**
165 This collection implementation is efficient when the `inserts()` to the collection come
166 in blocks, then the lookups (`find()` or `operator[]()`) in blocks, then the `inserts()` again.
167 This is because the collection only sorts itself when it is unsorted and a lookup occurs.
168 Non-unique keys are allowed, and the groups of non-unique keys are adjacent (after sorting) then the range of the "unique" key is multiple values.
169
170 The complexity is (assuming default container of `std::vector`, which affects these complexities):
171 -# Copy: O(n), worst-case.
172
173 More notes:
174 ===========
175 -# After sorting, non-unique keys are guaranteed to be adjacent in the multiset.
176 -# The base container can be pretty much any STL container. The obvious candidates are `std::vector` or `std:list`. The choice will affect the complexities above. The advantage of `std::vector` over `std::list` is locality of reference: The data elements are guaranteed to be local to each other, unlike `std::list`. Alternatively `std:list` has better complexity than `std::vector` for some of the operations. Choose wisely.
177 */
178 template<typename _Key,typename _Pred=std::less<_Key>,typename _Cont=std::vector<_Key> >
179 class multiset {
180 public:
181 typedef _Cont base_container;
182 typedef typename base_container::allocator_type allocator_type;
183 typedef _Key key_type;
184 typedef _Pred key_compare;
185 typedef const key_type value_type;
186 typedef typename base_container::difference_type difference_type;
187 typedef typename base_container::reference reference;
188 typedef typename base_container::const_reference const_reference;
189 typedef typename base_container::size_type size_type;
190 typedef typename base_container::const_iterator const_iterator;
191 typedef typename base_container::iterator iterator;
192 typedef typename base_container::reverse_iterator reverse_iterator;
193 typedef typename base_container::const_reverse_iterator const_reverse_iterator;
194 typedef std::pair<iterator,bool> InsertItr_;
195
196 explicit __stdcall multiset(const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
197 __stdcall multiset(const size_type,const value_type &v=value_type(),const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
198 __stdcall multiset(const multiset &) FORCE_INLINE;
199 __stdcall multiset(const const_iterator &,const const_iterator &,const _Pred &pr=_Pred(),const allocator_type &al=allocator_type()) FORCE_INLINE;
200 __stdcall ~multiset(void) FORCE_INLINE;
201
202 multiset & __fastcall operator=(const multiset &m) FORCE_INLINE;
203
204 const_iterator __fastcall begin(void) const noexcept(true) FORCE_INLINE;
205 iterator __fastcall begin(void) noexcept(true) FORCE_INLINE;
206 const_reverse_iterator __fastcall rbegin(void) const noexcept(true) FORCE_INLINE;
207 reverse_iterator __fastcall rbegin(void) noexcept(true) FORCE_INLINE;
208 const_iterator __fastcall end(void) const noexcept(true) FORCE_INLINE;
209 iterator __fastcall end(void) noexcept(true) FORCE_INLINE;
210 const_reverse_iterator __fastcall rend(void) const noexcept(true) FORCE_INLINE;
211 reverse_iterator __fastcall rend(void) noexcept(true) FORCE_INLINE;
212
213 const size_type __fastcall size(void) const noexcept(true) FORCE_INLINE;
214 const size_type __fastcall max_size(void) const noexcept(true) FORCE_INLINE;
215 bool __fastcall empty(void) const noexcept(true) FORCE_INLINE;
216 void __fastcall clear(void) FORCE_INLINE;
217 void __fastcall resize(const size_type,const value_type &v=value_type()) FORCE_INLINE;
218 void __fastcall reserve(const size_type) FORCE_INLINE;
219
220 allocator_type __fastcall get_allocator(void) const FORCE_INLINE;
221
222 /**
223 Insert: (with `insert()`) constant time. (But unsorts the multiset.)
224 Allows the insertion of multiple keys with the same value.
225 */
226 InsertItr_ __fastcall insert(const value_type &) FORCE_INLINE;
227 /**
228 Insert: (with `insert()`) constant time. (But unsorts the multiset.)
229 Allows the insertion of multiple keys with the same value.
230 */
231 iterator __fastcall insert(const iterator &,const value_type &) FORCE_INLINE;
232 /**
233 Insert: (with `insert()`) constant time. (But unsorts the multiset.)
234 Allows the insertion of multiple keys with the same value.
235 */
236 void __fastcall insert(const const_iterator &,const const_iterator &) FORCE_INLINE;
237
238 /**
239 Erase: O(n).
240 */
241 iterator __fastcall erase(const iterator &) FORCE_INLINE;
242 /**
243 Erase: O(n).
244 */
245 iterator __fastcall erase(const iterator &,const iterator &) FORCE_INLINE;
246 /**
247 Erase: O(nlog(n)).
248 All keys with same value are erased. Collection remains sorted.
249 */
250 const size_type __fastcall erase(const key_type &) FORCE_INLINE;
251
252 /**
253 Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multiset or not.
254 Are guaranteed to return the first key if they are not unique in the multiset.
255 */
256 const_iterator __fastcall find(const key_type &) const FORCE_INLINE;
257 /**
258 Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multiset or not.
259 Are guaranteed to return the first key if they are not unique in the multiset.
260 */
261 iterator __fastcall find(const key_type &) FORCE_INLINE;
262
263 private:
264 class value_compare : public std::binary_function<value_type,value_type,bool> {
265 public:
266 constexpr value_compare(void) noexcept(true) FORCE_INLINE
267 : comp() {
268 }
269
270 bool __fastcall operator()(const value_type &X, const value_type &Y) const FORCE_INLINE {
271 return comp(X, Y);
272 }
273
274 private:
275 const _Pred comp;
276
277 friend class multiset<_Key,_Pred,_Cont>;
278
279 void __fastcall operator=(const value_compare &)=delete;
280 };
281
282 mutable base_container cont;
283 mutable bool is_sorted;
284
285 void __fastcall sort(void) const FORCE_INLINE;
286 void __fastcall sort(void) FORCE_INLINE;
287 const_iterator __fastcall find_first_key(const const_iterator &) const FORCE_INLINE;
288 iterator __fastcall find_first_key(const iterator &) const FORCE_INLINE;
289 };
290
291 } }
292
293 #include "multimap_impl.hpp"