libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
multimap.hpp
Go to the documentation of this file.
1 /******************************************************************************
2 ** Copyright © 2004 by J.M.McGuiness, coder@hussar.me.uk
3 **
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Lesser General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2.1 of the License, or (at your option) any later version.
8 **
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Lesser General Public License for more details.
13 **
14 ** You should have received a copy of the GNU Lesser General Public
15 ** License along with this library; if not, write to the Free Software
16 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
19 #pragma once
20 
21 #include "config.h"
22 
23 #include <algorithm>
24 #include <functional>
25 #include <vector>
26 
27 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { 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"