libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
multimap_impl.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 #include <cassert>
20 
21 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { namespace rapid_insert_lookup {
22 
23  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline __stdcall
24  multimap<_Key,_Val,_Pred,_Cont>::multimap(const _Pred &,const allocator_type &al)
25  : cont(al),is_sorted(true) {
26  }
27 
28  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline __stdcall
29  multimap<_Key,_Val,_Pred,_Cont>::multimap(const size_type n,const value_type &v,const _Pred &,const allocator_type &al)
30  : cont(n,v,al),is_sorted(true) {
31  }
32 
33  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline __stdcall
34  multimap<_Key,_Val,_Pred,_Cont>::multimap(const multimap &m)
35  : cont(m.cont),is_sorted(m.is_sorted) {
36  }
37 
38  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline __stdcall
39  multimap<_Key,_Val,_Pred,_Cont>::multimap(const const_iterator &b,const const_iterator &e,const _Pred &,const allocator_type &al)
40  : cont(b,e,al),is_sorted(false) {
41  }
42 
43  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline __stdcall
44  multimap<_Key,_Val,_Pred,_Cont>::~multimap(void) {
45  }
46 
47  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline multimap<_Key,_Val,_Pred,_Cont> & __fastcall
48  multimap<_Key,_Val,_Pred,_Cont>::operator=(const multimap &m) {
49  cont=m.cont;
50  is_sorted=m.is_sorted;
51  return *this;
52  }
53 
54  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
55  multimap<_Key,_Val,_Pred,_Cont>::sort(void) const {
56  std::sort(cont.begin(),cont.end(),value_compare());
57  is_sorted=true;
58  }
59 
60  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
61  multimap<_Key,_Val,_Pred,_Cont>::sort(void) {
62  std::sort(cont.begin(),cont.end(),value_compare());
63  is_sorted=true;
64  }
65 
66  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_iterator __fastcall
67  multimap<_Key,_Val,_Pred,_Cont>::begin(void) const noexcept(true) {
68  if (!is_sorted) {
69  const_cast<multimap<_Key,_Val,_Pred,_Cont> *>(this)->sort();
70  }
71  return cont.begin();
72  }
73 
74  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
75  multimap<_Key,_Val,_Pred,_Cont>::begin(void) noexcept(true) {
76  if (!is_sorted) {
77  sort();
78  }
79  return cont.begin();
80  }
81 
82  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_reverse_iterator __fastcall
83  multimap<_Key,_Val,_Pred,_Cont>::rbegin(void) const noexcept(true) {
84  if (!is_sorted) {
85  const_cast<multimap<_Key,_Val,_Pred,_Cont> *>(this)->sort();
86  }
87  return cont.rbegin();
88  }
89 
90  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::reverse_iterator __fastcall
91  multimap<_Key,_Val,_Pred,_Cont>::rbegin(void) noexcept(true) {
92  if (!is_sorted) {
93  sort();
94  }
95  return cont.rbegin();
96  }
97 
98  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_iterator __fastcall
99  multimap<_Key,_Val,_Pred,_Cont>::end(void) const noexcept(true) {
100  if (!is_sorted) {
101  const_cast<multimap<_Key,_Val,_Pred,_Cont> *>(this)->sort();
102  }
103  return cont.end();
104  }
105 
106  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
107  multimap<_Key,_Val,_Pred,_Cont>::end(void) noexcept(true) {
108  if (!is_sorted) {
109  sort();
110  }
111  return cont.end();
112  }
113 
114  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_reverse_iterator __fastcall
115  multimap<_Key,_Val,_Pred,_Cont>::rend(void) const noexcept(true) {
116  if (!is_sorted) {
117  const_cast<multimap<_Key,_Val,_Pred,_Cont> *>(this)->sort();
118  }
119  return cont.rend();
120  }
121 
122  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::reverse_iterator __fastcall
123  multimap<_Key,_Val,_Pred,_Cont>::rend(void) noexcept(true) {
124  if (!is_sorted) {
125  sort();
126  }
127  return cont.rend();
128  }
129 
130  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline const typename multimap<_Key,_Val,_Pred,_Cont>::size_type __fastcall
131  multimap<_Key,_Val,_Pred,_Cont>::size(void) const noexcept(true) {
132  return cont.size();
133  }
134 
135  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline const typename multimap<_Key,_Val,_Pred,_Cont>::size_type __fastcall
136  multimap<_Key,_Val,_Pred,_Cont>::max_size(void) const noexcept(true) {
137  return cont.max_size();
138  }
139 
140  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline bool __fastcall
141  multimap<_Key,_Val,_Pred,_Cont>::empty(void) const noexcept(true) {
142  return cont.empty();
143  }
144 
145  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
146  multimap<_Key,_Val,_Pred,_Cont>::clear(void) {
147  cont.clear();
148  is_sorted=true;
149  }
150 
151  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
152  multimap<_Key,_Val,_Pred,_Cont>::resize(const size_type new_sz,const value_type &v) {
153  const size_type orig_size=cont.size();
154  cont.resize(new_sz,v);
155  // Only get unsorted if the underlying container grows in size.
156  is_sorted=(orig_size>=cont.size());
157  }
158 
159  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
160  multimap<_Key,_Val,_Pred,_Cont>::reserve(const size_type new_sz) {
161  const size_type orig_size=cont.size();
162  cont.reserve(new_sz);
163  // Only get unsorted if the underlying container grows in size.
164  is_sorted=(orig_size>=cont.size());
165  }
166 
167  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::allocator_type __fastcall
168  multimap<_Key,_Val,_Pred,_Cont>::get_allocator(void) const {
169  return cont.get_allocator();
170  }
171 
172  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::InsertItr_ __fastcall
173  multimap<_Key,_Val,_Pred,_Cont>::insert(const value_type &val) {
174  // Note - we make no checks to determine if the key is already in the map. This could maen that "operator[](...)" won't let us reliably access all of those elements with the same key.
175  cont.push_back(val);
176  const InsertItr_ ret(std::make_pair(std::prev(cont.end()),true));
177  is_sorted=false;
178  return ret;
179  }
180 
181  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
182  multimap<_Key,_Val,_Pred,_Cont>::insert(const iterator &i,const value_type &v) {
183  // Note - we make no checks to determine if the key is already in the map. This could maen that "operator[](...)" won't let us reliably access all of those elements with the same key.
184  const iterator ret(cont.insert(i,v));
185  is_sorted=false;
186  return ret;
187  }
188 
189  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline void __fastcall
190  multimap<_Key,_Val,_Pred,_Cont>::insert(const const_iterator &f,const const_iterator &l) {
191  // Note - we make no checks to determine if the key is already in the map. This could mean that "operator[](...)" won't let us reliably access all of those elements with the same key.
192  cont.insert(end(),f,l);
193  is_sorted=false;
194  }
195 
196  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
197  multimap<_Key,_Val,_Pred,_Cont>::erase(const iterator &i) {
198  return cont.erase(i);
199  }
200 
201  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
202  multimap<_Key,_Val,_Pred,_Cont>::erase(const iterator &f,const iterator &l) {
203  return cont.erase(f,l);
204  }
205 
206  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_iterator __fastcall
207  multimap<_Key,_Val,_Pred,_Cont>::find_first_key(const const_iterator &i) const {
208  if (i!=end()) {
209  const_iterator iter(i);
210  while (iter!=cont.begin() && !key_compare()(std::prev(iter)->first,iter->first) && !key_compare()(iter->first,std::prev(iter)->first)) {
211  --iter;
212  }
213  assert(!key_compare()(i->first,iter->first) && !key_compare()(iter->first,i->first));
214  return iter;
215  }
216  return i;
217  }
218 
219  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
220  multimap<_Key,_Val,_Pred,_Cont>::find_first_key(const iterator &i) const {
221  if (i!=end()) {
222  iterator iter(i);
223  while (iter!=cont.begin() && !key_compare()(std::prev(iter)->first,iter->first) && !key_compare()(iter->first,std::prev(iter)->first)) {
224  --iter;
225  }
226  assert(!key_compare()(i->first,iter->first) && !key_compare()(iter->first,i->first));
227  return iter;
228  }
229  return i;
230  }
231 
232  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline const typename multimap<_Key,_Val,_Pred,_Cont>::size_type __fastcall
233  multimap<_Key,_Val,_Pred,_Cont>::erase(const key_type &key) {
234  size_type num_erased=0;
235  for (
236  iterator iter(find_first_key(std::lower_bound(cont.begin(),cont.end(),std::make_pair(key,mapped_type()),value_compare())));
237  iter!=cont.end() && !key_compare()(key,iter->first);
238  iter=find_first_key(std::lower_bound(cont.begin(),cont.end(),std::make_pair(key,mapped_type()),value_compare()))
239  ) {
240  cont.erase(iter);
241  ++num_erased;
242  }
243  return num_erased;
244  }
245 
246  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::mapped_type & __fastcall
247  multimap<_Key,_Val,_Pred,_Cont>::operator[](const key_type &key) {
248  if (!is_sorted) {
249  sort();
250  }
251  const iterator iter(find_first_key(std::lower_bound(cont.begin(),cont.end(),std::make_pair(key,mapped_type()),value_compare())));
252  if (iter==cont.end()) {
253  cont.push_back(std::make_pair(key,mapped_type()));
254  is_sorted=false;
255  return std::prev(cont.end())->second;
256  }
257  return iter->second;
258  }
259 
260  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::const_iterator __fastcall
261  multimap<_Key,_Val,_Pred,_Cont>::find(const key_type &key) const {
262  if (!is_sorted) {
263  const_cast<multimap<_Key,_Val,_Pred,_Cont> *>(this)->sort();
264  }
265  const const_iterator i(find_first_key(std::lower_bound(cont.begin(),cont.end(),std::make_pair(key,mapped_type()),value_compare())));
266  if (i!=cont.end()) {
267  const bool is_same_key(!key_compare()(i->first,key) && !key_compare()(key,i->first));
268  return is_same_key ? i : cont.end();
269  } else {
270  return i;
271  }
272  }
273 
274  template<typename _Key,typename _Val,typename _Pred,typename _Cont> inline typename multimap<_Key,_Val,_Pred,_Cont>::iterator __fastcall
275  multimap<_Key,_Val,_Pred,_Cont>::find(const key_type &key) {
276  if (!is_sorted) {
277  sort();
278  }
279  const iterator i(find_first_key(std::lower_bound(cont.begin(),cont.end(),std::make_pair(key,mapped_type()),value_compare())));
280  if (i!=cont.end()) {
281  const bool is_same_key(!key_compare()(i->first,key) && !key_compare()(key,i->first));
282  return is_same_key ? i : cont.end();
283  } else {
284  return i;
285  }
286  }
287 
288 // multiset
289 
290  template<typename _Key,typename _Pred,typename _Cont> inline __stdcall
291  multiset<_Key,_Pred,_Cont>::multiset(const _Pred &,const allocator_type &al)
292  : cont(al),is_sorted(true) {
293  }
294 
295  template<typename _Key,typename _Pred,typename _Cont> inline __stdcall
296  multiset<_Key,_Pred,_Cont>::multiset(const size_type n,const value_type &v,const _Pred &,const allocator_type &al)
297  : cont(n,v,al),is_sorted(true) {
298  }
299 
300  template<typename _Key,typename _Pred,typename _Cont> inline __stdcall
301  multiset<_Key,_Pred,_Cont>::multiset(const multiset &m)
302  : cont(m.cont),is_sorted(m.is_sorted) {
303  }
304 
305  template<typename _Key,typename _Pred,typename _Cont> inline __stdcall
306  multiset<_Key,_Pred,_Cont>::multiset(const const_iterator &b,const const_iterator &e,const _Pred &,const allocator_type &al)
307  : cont(b,e,al),is_sorted(false) {
308  }
309 
310  template<typename _Key,typename _Pred,typename _Cont> inline __stdcall
311  multiset<_Key,_Pred,_Cont>::~multiset(void) {
312  }
313 
314  template<typename _Key,typename _Pred,typename _Cont> inline multiset<_Key,_Pred,_Cont> & __fastcall
315  multiset<_Key,_Pred,_Cont>::operator=(const multiset &m) {
316  cont=m.cont;
317  is_sorted=m.is_sorted;
318  return *this;
319  }
320 
321  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
322  multiset<_Key,_Pred,_Cont>::sort(void) const {
323  std::sort(cont.begin(),cont.end(),value_compare());
324  is_sorted=true;
325  }
326 
327  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
328  multiset<_Key,_Pred,_Cont>::sort(void) {
329  std::sort(cont.begin(),cont.end(),value_compare());
330  is_sorted=true;
331  }
332 
333  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_iterator __fastcall
334  multiset<_Key,_Pred,_Cont>::begin(void) const noexcept(true) {
335  if (!is_sorted) {
336  const_cast<multiset<_Key,_Pred,_Cont> *>(this)->sort();
337  }
338  return cont.begin();
339  }
340 
341  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
342  multiset<_Key,_Pred,_Cont>::begin(void) noexcept(true) {
343  if (!is_sorted) {
344  sort();
345  }
346  return cont.begin();
347  }
348 
349  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_reverse_iterator __fastcall
350  multiset<_Key,_Pred,_Cont>::rbegin(void) const noexcept(true) {
351  if (!is_sorted) {
352  const_cast<multiset<_Key,_Pred,_Cont> *>(this)->sort();
353  }
354  return cont.rbegin();
355  }
356 
357  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::reverse_iterator __fastcall
358  multiset<_Key,_Pred,_Cont>::rbegin(void) noexcept(true) {
359  if (!is_sorted) {
360  sort();
361  }
362  return cont.rbegin();
363  }
364 
365  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_iterator __fastcall
366  multiset<_Key,_Pred,_Cont>::end(void) const noexcept(true) {
367  if (!is_sorted) {
368  const_cast<multiset<_Key,_Pred,_Cont> *>(this)->sort();
369  }
370  return cont.end();
371  }
372 
373  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
374  multiset<_Key,_Pred,_Cont>::end(void) noexcept(true) {
375  if (!is_sorted) {
376  sort();
377  }
378  return cont.end();
379  }
380 
381  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_reverse_iterator __fastcall
382  multiset<_Key,_Pred,_Cont>::rend(void) const noexcept(true) {
383  if (!is_sorted) {
384  const_cast<multiset<_Key,_Pred,_Cont> *>(this)->sort();
385  }
386  return cont.rend();
387  }
388 
389  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::reverse_iterator __fastcall
390  multiset<_Key,_Pred,_Cont>::rend(void) noexcept(true) {
391  if (!is_sorted) {
392  sort();
393  }
394  return cont.rend();
395  }
396 
397  template<typename _Key,typename _Pred,typename _Cont> inline const typename multiset<_Key,_Pred,_Cont>::size_type __fastcall
398  multiset<_Key,_Pred,_Cont>::size(void) const noexcept(true) {
399  return cont.size();
400  }
401 
402  template<typename _Key,typename _Pred,typename _Cont> inline const typename multiset<_Key,_Pred,_Cont>::size_type __fastcall
403  multiset<_Key,_Pred,_Cont>::max_size(void) const noexcept(true) {
404  return cont.max_size();
405  }
406 
407  template<typename _Key,typename _Pred,typename _Cont> inline bool __fastcall
408  multiset<_Key,_Pred,_Cont>::empty(void) const noexcept(true) {
409  return cont.empty();
410  }
411 
412  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
413  multiset<_Key,_Pred,_Cont>::clear(void) {
414  cont.clear();
415  is_sorted=true;
416  }
417 
418  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
419  multiset<_Key,_Pred,_Cont>::resize(const size_type new_sz,const value_type &v) {
420  const size_type orig_size=cont.size();
421  cont.resize(new_sz,v);
422  // Only get unsorted if the underlying container grows in size.
423  is_sorted=(orig_size>=cont.size());
424  }
425 
426  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
427  multiset<_Key,_Pred,_Cont>::reserve(const size_type new_sz) {
428  const size_type orig_size=cont.size();
429  cont.reserve(new_sz);
430  // Only get unsorted if the underlying container grows in size.
431  is_sorted=(orig_size>=cont.size());
432  }
433 
434  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::allocator_type __fastcall
435  multiset<_Key,_Pred,_Cont>::get_allocator(void) const {
436  return cont.get_allocator();
437  }
438 
439  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::InsertItr_ __fastcall
440  multiset<_Key,_Pred,_Cont>::insert(const value_type &val) {
441  // Note - we make no checks to determine if the key is already in the map. This could maen that "operator[](...)" won't let us reliably access all of those elements with the same key.
442  cont.push_back(val);
443  const InsertItr_ ret(std::make_pair(std::prev(cont.end()),true));
444  is_sorted=false;
445  return ret;
446  }
447 
448  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
449  multiset<_Key,_Pred,_Cont>::insert(const iterator &i,const value_type &v) {
450  // Note - we make no checks to determine if the key is already in the map. This could maen that "operator[](...)" won't let us reliably access all of those elements with the same key.
451  const iterator ret(cont.insert(i,v));
452  is_sorted=false;
453  return ret;
454  }
455 
456  template<typename _Key,typename _Pred,typename _Cont> inline void __fastcall
457  multiset<_Key,_Pred,_Cont>::insert(const const_iterator &f,const const_iterator &l) {
458  // Note - we make no checks to determine if the key is already in the map. This could maen that "operator[](...)" won't let us reliably access all of those elements with the same key.
459  cont.insert(end(),f,l);
460  is_sorted=false;
461  }
462 
463  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
464  multiset<_Key,_Pred,_Cont>::erase(const iterator &i) {
465  return cont.erase(i);
466  }
467 
468  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
469  multiset<_Key,_Pred,_Cont>::erase(const iterator &f,const iterator &l) {
470  return cont.erase(f,l);
471  }
472 
473  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_iterator __fastcall
474  multiset<_Key,_Pred,_Cont>::find_first_key(const const_iterator &i) const {
475  if (i!=end()) {
476  const_iterator iter(i);
477  while (iter!=cont.begin() && !key_compare()(*std::prev(iter),*iter) && !key_compare()(*iter,*std::prev(iter))) {
478  --iter;
479  }
480  assert(!key_compare()(*i,*iter) && !key_compare()(*iter,*i));
481  return iter;
482  }
483  return i;
484  }
485 
486  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
487  multiset<_Key,_Pred,_Cont>::find_first_key(const iterator &i) const {
488  if (i!=end()) {
489  iterator iter(i);
490  while (iter!=cont.begin() && !key_compare()(*std::prev(iter),*iter) && !key_compare()(*iter,*std::prev(iter))) {
491  --iter;
492  }
493  assert(!key_compare()(*i,*iter) && !key_compare()(*iter,*i));
494  return iter;
495  }
496  return i;
497  }
498 
499  template<typename _Key,typename _Pred,typename _Cont> inline const typename multiset<_Key,_Pred,_Cont>::size_type __fastcall
500  multiset<_Key,_Pred,_Cont>::erase(const key_type &key) {
501  size_type num_erased=0;
502  for (
503  iterator iter(find_first_key(std::lower_bound(cont.begin(),cont.end(),key,value_compare())));
504  iter!=cont.end() && !key_compare()(key,*iter);
505  iter=find_first_key(std::lower_bound(cont.begin(),cont.end(),key,value_compare()))
506  ) {
507  cont.erase(iter++);
508  ++num_erased;
509  }
510  return num_erased;
511  }
512 
513  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::const_iterator __fastcall
514  multiset<_Key,_Pred,_Cont>::find(const key_type &key) const {
515  if (!is_sorted) {
516  const_cast<multiset<_Key,_Pred,_Cont> *>(this)->sort();
517  }
518  const const_iterator i(find_first_key(std::lower_bound(cont.begin(),cont.end(),key,value_compare())));
519  if (i!=cont.end()) {
520  const bool is_same_key(!key_compare()(i->first,key) && !key_compare()(key,i->first));
521  return is_same_key ? i : cont.end();
522  } else {
523  return i;
524  }
525  }
526 
527  template<typename _Key,typename _Pred,typename _Cont> inline typename multiset<_Key,_Pred,_Cont>::iterator __fastcall
528  multiset<_Key,_Pred,_Cont>::find(const key_type &key) {
529  if (!is_sorted) {
530  sort();
531  }
532  const iterator i(find_first_key(std::lower_bound(cont.begin(),cont.end(),key,value_compare())));
533  if (i!=cont.end()) {
534  const bool is_same_key(!key_compare()(i->first,key) && !key_compare()(key,i->first));
535  return is_same_key ? i : cont.end();
536  } else {
537  return i;
538  }
539  }
540 
541 } } }