OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [bits/] [stl_multiset.h] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// Multiset implementation -*- C++ -*-
2
 
3
// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4
// 2011, 2012 Free Software Foundation, Inc.
5
//
6
// This file is part of the GNU ISO C++ Library.  This library is free
7
// software; you can redistribute it and/or modify it under the
8
// terms of the GNU General Public License as published by the
9
// Free Software Foundation; either version 3, or (at your option)
10
// any later version.
11
 
12
// This library is distributed in the hope that it will be useful,
13
// but WITHOUT ANY WARRANTY; without even the implied warranty of
14
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
// GNU General Public License for more details.
16
 
17
// Under Section 7 of GPL version 3, you are granted additional
18
// permissions described in the GCC Runtime Library Exception, version
19
// 3.1, as published by the Free Software Foundation.
20
 
21
// You should have received a copy of the GNU General Public License and
22
// a copy of the GCC Runtime Library Exception along with this program;
23
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24
// <http://www.gnu.org/licenses/>.
25
 
26
/*
27
 *
28
 * Copyright (c) 1994
29
 * Hewlett-Packard Company
30
 *
31
 * Permission to use, copy, modify, distribute and sell this software
32
 * and its documentation for any purpose is hereby granted without fee,
33
 * provided that the above copyright notice appear in all copies and
34
 * that both that copyright notice and this permission notice appear
35
 * in supporting documentation.  Hewlett-Packard Company makes no
36
 * representations about the suitability of this software for any
37
 * purpose.  It is provided "as is" without express or implied warranty.
38
 *
39
 *
40
 * Copyright (c) 1996
41
 * Silicon Graphics Computer Systems, Inc.
42
 *
43
 * Permission to use, copy, modify, distribute and sell this software
44
 * and its documentation for any purpose is hereby granted without fee,
45
 * provided that the above copyright notice appear in all copies and
46
 * that both that copyright notice and this permission notice appear
47
 * in supporting documentation.  Silicon Graphics makes no
48
 * representations about the suitability of this software for any
49
 * purpose.  It is provided "as is" without express or implied warranty.
50
 */
51
 
52
/** @file bits/stl_multiset.h
53
 *  This is an internal header file, included by other library headers.
54
 *  Do not attempt to use it directly. @headername{set}
55
 */
56
 
57
#ifndef _STL_MULTISET_H
58
#define _STL_MULTISET_H 1
59
 
60
#include <bits/concept_check.h>
61
#if __cplusplus >= 201103L
62
#include <initializer_list>
63
#endif
64
 
65
namespace std _GLIBCXX_VISIBILITY(default)
66
{
67
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
 
69
  /**
70
   *  @brief A standard container made up of elements, which can be retrieved
71
   *  in logarithmic time.
72
   *
73
   *  @ingroup associative_containers
74
   *
75
   *
76
   *  @tparam _Key  Type of key objects.
77
   *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
78
   *  @tparam _Alloc  Allocator type, defaults to allocator<_Key>.
79
   *
80
   *  Meets the requirements of a <a href="tables.html#65">container</a>, a
81
   *  <a href="tables.html#66">reversible container</a>, and an
82
   *  <a href="tables.html#69">associative container</a> (using equivalent
83
   *  keys).  For a @c multiset<Key> the key_type and value_type are Key.
84
   *
85
   *  Multisets support bidirectional iterators.
86
   *
87
   *  The private tree data is declared exactly the same way for set and
88
   *  multiset; the distinction is made entirely in how the tree functions are
89
   *  called (*_unique versus *_equal, same as the standard).
90
  */
91
  template <typename _Key, typename _Compare = std::less<_Key>,
92
            typename _Alloc = std::allocator<_Key> >
93
    class multiset
94
    {
95
      // concept requirements
96
      typedef typename _Alloc::value_type                   _Alloc_value_type;
97
      __glibcxx_class_requires(_Key, _SGIAssignableConcept)
98
      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
99
                                _BinaryFunctionConcept)
100
      __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
101
 
102
    public:
103
      // typedefs:
104
      typedef _Key     key_type;
105
      typedef _Key     value_type;
106
      typedef _Compare key_compare;
107
      typedef _Compare value_compare;
108
      typedef _Alloc   allocator_type;
109
 
110
    private:
111
      /// This turns a red-black tree into a [multi]set.
112
      typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
113
 
114
      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
115
                       key_compare, _Key_alloc_type> _Rep_type;
116
      /// The actual tree structure.
117
      _Rep_type _M_t;
118
 
119
    public:
120
      typedef typename _Key_alloc_type::pointer             pointer;
121
      typedef typename _Key_alloc_type::const_pointer       const_pointer;
122
      typedef typename _Key_alloc_type::reference           reference;
123
      typedef typename _Key_alloc_type::const_reference     const_reference;
124
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
125
      // DR 103. set::iterator is required to be modifiable,
126
      // but this allows modification of keys.
127
      typedef typename _Rep_type::const_iterator            iterator;
128
      typedef typename _Rep_type::const_iterator            const_iterator;
129
      typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
130
      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
131
      typedef typename _Rep_type::size_type                 size_type;
132
      typedef typename _Rep_type::difference_type           difference_type;
133
 
134
      // allocation/deallocation
135
      /**
136
       *  @brief  Default constructor creates no elements.
137
       */
138
      multiset()
139
      : _M_t() { }
140
 
141
      /**
142
       *  @brief  Creates a %multiset with no elements.
143
       *  @param  __comp  Comparator to use.
144
       *  @param  __a  An allocator object.
145
       */
146
      explicit
147
      multiset(const _Compare& __comp,
148
               const allocator_type& __a = allocator_type())
149
      : _M_t(__comp, _Key_alloc_type(__a)) { }
150
 
151
      /**
152
       *  @brief  Builds a %multiset from a range.
153
       *  @param  __first  An input iterator.
154
       *  @param  __last  An input iterator.
155
       *
156
       *  Create a %multiset consisting of copies of the elements from
157
       *  [first,last).  This is linear in N if the range is already sorted,
158
       *  and NlogN otherwise (where N is distance(__first,__last)).
159
       */
160
      template<typename _InputIterator>
161
        multiset(_InputIterator __first, _InputIterator __last)
162
        : _M_t()
163
        { _M_t._M_insert_equal(__first, __last); }
164
 
165
      /**
166
       *  @brief  Builds a %multiset from a range.
167
       *  @param  __first  An input iterator.
168
       *  @param  __last  An input iterator.
169
       *  @param  __comp  A comparison functor.
170
       *  @param  __a  An allocator object.
171
       *
172
       *  Create a %multiset consisting of copies of the elements from
173
       *  [__first,__last).  This is linear in N if the range is already sorted,
174
       *  and NlogN otherwise (where N is distance(__first,__last)).
175
       */
176
      template<typename _InputIterator>
177
        multiset(_InputIterator __first, _InputIterator __last,
178
                 const _Compare& __comp,
179
                 const allocator_type& __a = allocator_type())
180
        : _M_t(__comp, _Key_alloc_type(__a))
181
        { _M_t._M_insert_equal(__first, __last); }
182
 
183
      /**
184
       *  @brief  %Multiset copy constructor.
185
       *  @param  __x  A %multiset of identical element and allocator types.
186
       *
187
       *  The newly-created %multiset uses a copy of the allocation object used
188
       *  by @a __x.
189
       */
190
      multiset(const multiset& __x)
191
      : _M_t(__x._M_t) { }
192
 
193
#if __cplusplus >= 201103L
194
     /**
195
       *  @brief  %Multiset move constructor.
196
       *  @param  __x  A %multiset of identical element and allocator types.
197
       *
198
       *  The newly-created %multiset contains the exact contents of @a __x.
199
       *  The contents of @a __x are a valid, but unspecified %multiset.
200
       */
201
      multiset(multiset&& __x)
202
      noexcept(is_nothrow_copy_constructible<_Compare>::value)
203
      : _M_t(std::move(__x._M_t)) { }
204
 
205
      /**
206
       *  @brief  Builds a %multiset from an initializer_list.
207
       *  @param  __l  An initializer_list.
208
       *  @param  __comp  A comparison functor.
209
       *  @param  __a  An allocator object.
210
       *
211
       *  Create a %multiset consisting of copies of the elements from
212
       *  the list.  This is linear in N if the list is already sorted,
213
       *  and NlogN otherwise (where N is @a __l.size()).
214
       */
215
      multiset(initializer_list<value_type> __l,
216
               const _Compare& __comp = _Compare(),
217
               const allocator_type& __a = allocator_type())
218
      : _M_t(__comp, _Key_alloc_type(__a))
219
      { _M_t._M_insert_equal(__l.begin(), __l.end()); }
220
#endif
221
 
222
      /**
223
       *  @brief  %Multiset assignment operator.
224
       *  @param  __x  A %multiset of identical element and allocator types.
225
       *
226
       *  All the elements of @a __x are copied, but unlike the copy
227
       *  constructor, the allocator object is not copied.
228
       */
229
      multiset&
230
      operator=(const multiset& __x)
231
      {
232
        _M_t = __x._M_t;
233
        return *this;
234
      }
235
 
236
#if __cplusplus >= 201103L
237
      /**
238
       *  @brief  %Multiset move assignment operator.
239
       *  @param  __x  A %multiset of identical element and allocator types.
240
       *
241
       *  The contents of @a __x are moved into this %multiset
242
       *  (without copying).  @a __x is a valid, but unspecified
243
       *  %multiset.
244
       */
245
      multiset&
246
      operator=(multiset&& __x)
247
      {
248
        // NB: DR 1204.
249
        // NB: DR 675.
250
        this->clear();
251
        this->swap(__x);
252
        return *this;
253
      }
254
 
255
      /**
256
       *  @brief  %Multiset list assignment operator.
257
       *  @param  __l  An initializer_list.
258
       *
259
       *  This function fills a %multiset with copies of the elements in the
260
       *  initializer list @a __l.
261
       *
262
       *  Note that the assignment completely changes the %multiset and
263
       *  that the resulting %multiset's size is the same as the number
264
       *  of elements assigned.  Old data may be lost.
265
       */
266
      multiset&
267
      operator=(initializer_list<value_type> __l)
268
      {
269
        this->clear();
270
        this->insert(__l.begin(), __l.end());
271
        return *this;
272
      }
273
#endif
274
 
275
      // accessors:
276
 
277
      ///  Returns the comparison object.
278
      key_compare
279
      key_comp() const
280
      { return _M_t.key_comp(); }
281
      ///  Returns the comparison object.
282
      value_compare
283
      value_comp() const
284
      { return _M_t.key_comp(); }
285
      ///  Returns the memory allocation object.
286
      allocator_type
287
      get_allocator() const _GLIBCXX_NOEXCEPT
288
      { return allocator_type(_M_t.get_allocator()); }
289
 
290
      /**
291
       *  Returns a read-only (constant) iterator that points to the first
292
       *  element in the %multiset.  Iteration is done in ascending order
293
       *  according to the keys.
294
       */
295
      iterator
296
      begin() const _GLIBCXX_NOEXCEPT
297
      { return _M_t.begin(); }
298
 
299
      /**
300
       *  Returns a read-only (constant) iterator that points one past the last
301
       *  element in the %multiset.  Iteration is done in ascending order
302
       *  according to the keys.
303
       */
304
      iterator
305
      end() const _GLIBCXX_NOEXCEPT
306
      { return _M_t.end(); }
307
 
308
      /**
309
       *  Returns a read-only (constant) reverse iterator that points to the
310
       *  last element in the %multiset.  Iteration is done in descending order
311
       *  according to the keys.
312
       */
313
      reverse_iterator
314
      rbegin() const _GLIBCXX_NOEXCEPT
315
      { return _M_t.rbegin(); }
316
 
317
      /**
318
       *  Returns a read-only (constant) reverse iterator that points to the
319
       *  last element in the %multiset.  Iteration is done in descending order
320
       *  according to the keys.
321
       */
322
      reverse_iterator
323
      rend() const _GLIBCXX_NOEXCEPT
324
      { return _M_t.rend(); }
325
 
326
#if __cplusplus >= 201103L
327
      /**
328
       *  Returns a read-only (constant) iterator that points to the first
329
       *  element in the %multiset.  Iteration is done in ascending order
330
       *  according to the keys.
331
       */
332
      iterator
333
      cbegin() const noexcept
334
      { return _M_t.begin(); }
335
 
336
      /**
337
       *  Returns a read-only (constant) iterator that points one past the last
338
       *  element in the %multiset.  Iteration is done in ascending order
339
       *  according to the keys.
340
       */
341
      iterator
342
      cend() const noexcept
343
      { return _M_t.end(); }
344
 
345
      /**
346
       *  Returns a read-only (constant) reverse iterator that points to the
347
       *  last element in the %multiset.  Iteration is done in descending order
348
       *  according to the keys.
349
       */
350
      reverse_iterator
351
      crbegin() const noexcept
352
      { return _M_t.rbegin(); }
353
 
354
      /**
355
       *  Returns a read-only (constant) reverse iterator that points to the
356
       *  last element in the %multiset.  Iteration is done in descending order
357
       *  according to the keys.
358
       */
359
      reverse_iterator
360
      crend() const noexcept
361
      { return _M_t.rend(); }
362
#endif
363
 
364
      ///  Returns true if the %set is empty.
365
      bool
366
      empty() const _GLIBCXX_NOEXCEPT
367
      { return _M_t.empty(); }
368
 
369
      ///  Returns the size of the %set.
370
      size_type
371
      size() const _GLIBCXX_NOEXCEPT
372
      { return _M_t.size(); }
373
 
374
      ///  Returns the maximum size of the %set.
375
      size_type
376
      max_size() const _GLIBCXX_NOEXCEPT
377
      { return _M_t.max_size(); }
378
 
379
      /**
380
       *  @brief  Swaps data with another %multiset.
381
       *  @param  __x  A %multiset of the same element and allocator types.
382
       *
383
       *  This exchanges the elements between two multisets in constant time.
384
       *  (It is only swapping a pointer, an integer, and an instance of the @c
385
       *  Compare type (which itself is often stateless and empty), so it should
386
       *  be quite fast.)
387
       *  Note that the global std::swap() function is specialized such that
388
       *  std::swap(s1,s2) will feed to this function.
389
       */
390
      void
391
      swap(multiset& __x)
392
      { _M_t.swap(__x._M_t); }
393
 
394
      // insert/erase
395
#if __cplusplus >= 201103L
396
      /**
397
       *  @brief Builds and inserts an element into the %multiset.
398
       *  @param  __args  Arguments used to generate the element instance to be
399
       *                 inserted.
400
       *  @return An iterator that points to the inserted element.
401
       *
402
       *  This function inserts an element into the %multiset.  Contrary
403
       *  to a std::set the %multiset does not rely on unique keys and thus
404
       *  multiple copies of the same element can be inserted.
405
       *
406
       *  Insertion requires logarithmic time.
407
       */
408
      template<typename... _Args>
409
        iterator
410
        emplace(_Args&&... __args)
411
        { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
412
 
413
      /**
414
       *  @brief Builds and inserts an element into the %multiset.
415
       *  @param  __pos  An iterator that serves as a hint as to where the
416
       *                element should be inserted.
417
       *  @param  __args  Arguments used to generate the element instance to be
418
       *                 inserted.
419
       *  @return An iterator that points to the inserted element.
420
       *
421
       *  This function inserts an element into the %multiset.  Contrary
422
       *  to a std::set the %multiset does not rely on unique keys and thus
423
       *  multiple copies of the same element can be inserted.
424
       *
425
       *  Note that the first parameter is only a hint and can potentially
426
       *  improve the performance of the insertion process.  A bad hint would
427
       *  cause no gains in efficiency.
428
       *
429
       *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
430
       *  for more on @a hinting.
431
       *
432
       *  Insertion requires logarithmic time (if the hint is not taken).
433
       */
434
      template<typename... _Args>
435
        iterator
436
        emplace_hint(const_iterator __pos, _Args&&... __args)
437
        {
438
          return _M_t._M_emplace_hint_equal(__pos,
439
                                            std::forward<_Args>(__args)...);
440
        }
441
#endif
442
 
443
      /**
444
       *  @brief Inserts an element into the %multiset.
445
       *  @param  __x  Element to be inserted.
446
       *  @return An iterator that points to the inserted element.
447
       *
448
       *  This function inserts an element into the %multiset.  Contrary
449
       *  to a std::set the %multiset does not rely on unique keys and thus
450
       *  multiple copies of the same element can be inserted.
451
       *
452
       *  Insertion requires logarithmic time.
453
       */
454
      iterator
455
      insert(const value_type& __x)
456
      { return _M_t._M_insert_equal(__x); }
457
 
458
#if __cplusplus >= 201103L
459
      iterator
460
      insert(value_type&& __x)
461
      { return _M_t._M_insert_equal(std::move(__x)); }
462
#endif
463
 
464
      /**
465
       *  @brief Inserts an element into the %multiset.
466
       *  @param  __position  An iterator that serves as a hint as to where the
467
       *                    element should be inserted.
468
       *  @param  __x  Element to be inserted.
469
       *  @return An iterator that points to the inserted element.
470
       *
471
       *  This function inserts an element into the %multiset.  Contrary
472
       *  to a std::set the %multiset does not rely on unique keys and thus
473
       *  multiple copies of the same element can be inserted.
474
       *
475
       *  Note that the first parameter is only a hint and can potentially
476
       *  improve the performance of the insertion process.  A bad hint would
477
       *  cause no gains in efficiency.
478
       *
479
       *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
480
       *  for more on @a hinting.
481
       *
482
       *  Insertion requires logarithmic time (if the hint is not taken).
483
       */
484
      iterator
485
      insert(const_iterator __position, const value_type& __x)
486
      { return _M_t._M_insert_equal_(__position, __x); }
487
 
488
#if __cplusplus >= 201103L
489
      iterator
490
      insert(const_iterator __position, value_type&& __x)
491
      { return _M_t._M_insert_equal_(__position, std::move(__x)); }
492
#endif
493
 
494
      /**
495
       *  @brief A template function that tries to insert a range of elements.
496
       *  @param  __first  Iterator pointing to the start of the range to be
497
       *                   inserted.
498
       *  @param  __last  Iterator pointing to the end of the range.
499
       *
500
       *  Complexity similar to that of the range constructor.
501
       */
502
      template<typename _InputIterator>
503
        void
504
        insert(_InputIterator __first, _InputIterator __last)
505
        { _M_t._M_insert_equal(__first, __last); }
506
 
507
#if __cplusplus >= 201103L
508
      /**
509
       *  @brief Attempts to insert a list of elements into the %multiset.
510
       *  @param  __l  A std::initializer_list<value_type> of elements
511
       *               to be inserted.
512
       *
513
       *  Complexity similar to that of the range constructor.
514
       */
515
      void
516
      insert(initializer_list<value_type> __l)
517
      { this->insert(__l.begin(), __l.end()); }
518
#endif
519
 
520
#if __cplusplus >= 201103L
521
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
522
      // DR 130. Associative erase should return an iterator.
523
      /**
524
       *  @brief Erases an element from a %multiset.
525
       *  @param  __position  An iterator pointing to the element to be erased.
526
       *  @return An iterator pointing to the element immediately following
527
       *          @a position prior to the element being erased. If no such
528
       *          element exists, end() is returned.
529
       *
530
       *  This function erases an element, pointed to by the given iterator,
531
       *  from a %multiset.  Note that this function only erases the element,
532
       *  and that if the element is itself a pointer, the pointed-to memory is
533
       *  not touched in any way.  Managing the pointer is the user's
534
       *  responsibility.
535
       */
536
      iterator
537
      erase(const_iterator __position)
538
      { return _M_t.erase(__position); }
539
#else
540
      /**
541
       *  @brief Erases an element from a %multiset.
542
       *  @param  __position  An iterator pointing to the element to be erased.
543
       *
544
       *  This function erases an element, pointed to by the given iterator,
545
       *  from a %multiset.  Note that this function only erases the element,
546
       *  and that if the element is itself a pointer, the pointed-to memory is
547
       *  not touched in any way.  Managing the pointer is the user's
548
       *  responsibility.
549
       */
550
      void
551
      erase(iterator __position)
552
      { _M_t.erase(__position); }
553
#endif
554
 
555
      /**
556
       *  @brief Erases elements according to the provided key.
557
       *  @param  __x  Key of element to be erased.
558
       *  @return  The number of elements erased.
559
       *
560
       *  This function erases all elements located by the given key from a
561
       *  %multiset.
562
       *  Note that this function only erases the element, and that if
563
       *  the element is itself a pointer, the pointed-to memory is not touched
564
       *  in any way.  Managing the pointer is the user's responsibility.
565
       */
566
      size_type
567
      erase(const key_type& __x)
568
      { return _M_t.erase(__x); }
569
 
570
#if __cplusplus >= 201103L
571
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
572
      // DR 130. Associative erase should return an iterator.
573
      /**
574
       *  @brief Erases a [first,last) range of elements from a %multiset.
575
       *  @param  __first  Iterator pointing to the start of the range to be
576
       *                   erased.
577
       *  @param __last Iterator pointing to the end of the range to
578
       *                be erased.
579
       *  @return The iterator @a last.
580
       *
581
       *  This function erases a sequence of elements from a %multiset.
582
       *  Note that this function only erases the elements, and that if
583
       *  the elements themselves are pointers, the pointed-to memory is not
584
       *  touched in any way.  Managing the pointer is the user's
585
       *  responsibility.
586
       */
587
      iterator
588
      erase(const_iterator __first, const_iterator __last)
589
      { return _M_t.erase(__first, __last); }
590
#else
591
      /**
592
       *  @brief Erases a [first,last) range of elements from a %multiset.
593
       *  @param  first  Iterator pointing to the start of the range to be
594
       *                 erased.
595
       *  @param  last  Iterator pointing to the end of the range to be erased.
596
       *
597
       *  This function erases a sequence of elements from a %multiset.
598
       *  Note that this function only erases the elements, and that if
599
       *  the elements themselves are pointers, the pointed-to memory is not
600
       *  touched in any way.  Managing the pointer is the user's
601
       *  responsibility.
602
       */
603
      void
604
      erase(iterator __first, iterator __last)
605
      { _M_t.erase(__first, __last); }
606
#endif
607
 
608
      /**
609
       *  Erases all elements in a %multiset.  Note that this function only
610
       *  erases the elements, and that if the elements themselves are pointers,
611
       *  the pointed-to memory is not touched in any way.  Managing the pointer
612
       *  is the user's responsibility.
613
       */
614
      void
615
      clear() _GLIBCXX_NOEXCEPT
616
      { _M_t.clear(); }
617
 
618
      // multiset operations:
619
 
620
      /**
621
       *  @brief Finds the number of elements with given key.
622
       *  @param  __x  Key of elements to be located.
623
       *  @return Number of elements with specified key.
624
       */
625
      size_type
626
      count(const key_type& __x) const
627
      { return _M_t.count(__x); }
628
 
629
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
630
      // 214.  set::find() missing const overload
631
      //@{
632
      /**
633
       *  @brief Tries to locate an element in a %set.
634
       *  @param  __x  Element to be located.
635
       *  @return  Iterator pointing to sought-after element, or end() if not
636
       *           found.
637
       *
638
       *  This function takes a key and tries to locate the element with which
639
       *  the key matches.  If successful the function returns an iterator
640
       *  pointing to the sought after element.  If unsuccessful it returns the
641
       *  past-the-end ( @c end() ) iterator.
642
       */
643
      iterator
644
      find(const key_type& __x)
645
      { return _M_t.find(__x); }
646
 
647
      const_iterator
648
      find(const key_type& __x) const
649
      { return _M_t.find(__x); }
650
      //@}
651
 
652
      //@{
653
      /**
654
       *  @brief Finds the beginning of a subsequence matching given key.
655
       *  @param  __x  Key to be located.
656
       *  @return  Iterator pointing to first element equal to or greater
657
       *           than key, or end().
658
       *
659
       *  This function returns the first element of a subsequence of elements
660
       *  that matches the given key.  If unsuccessful it returns an iterator
661
       *  pointing to the first element that has a greater value than given key
662
       *  or end() if no such element exists.
663
       */
664
      iterator
665
      lower_bound(const key_type& __x)
666
      { return _M_t.lower_bound(__x); }
667
 
668
      const_iterator
669
      lower_bound(const key_type& __x) const
670
      { return _M_t.lower_bound(__x); }
671
      //@}
672
 
673
      //@{
674
      /**
675
       *  @brief Finds the end of a subsequence matching given key.
676
       *  @param  __x  Key to be located.
677
       *  @return Iterator pointing to the first element
678
       *          greater than key, or end().
679
       */
680
      iterator
681
      upper_bound(const key_type& __x)
682
      { return _M_t.upper_bound(__x); }
683
 
684
      const_iterator
685
      upper_bound(const key_type& __x) const
686
      { return _M_t.upper_bound(__x); }
687
      //@}
688
 
689
      //@{
690
      /**
691
       *  @brief Finds a subsequence matching given key.
692
       *  @param  __x  Key to be located.
693
       *  @return  Pair of iterators that possibly points to the subsequence
694
       *           matching given key.
695
       *
696
       *  This function is equivalent to
697
       *  @code
698
       *    std::make_pair(c.lower_bound(val),
699
       *                   c.upper_bound(val))
700
       *  @endcode
701
       *  (but is faster than making the calls separately).
702
       *
703
       *  This function probably only makes sense for multisets.
704
       */
705
      std::pair<iterator, iterator>
706
      equal_range(const key_type& __x)
707
      { return _M_t.equal_range(__x); }
708
 
709
      std::pair<const_iterator, const_iterator>
710
      equal_range(const key_type& __x) const
711
      { return _M_t.equal_range(__x); }
712
      //@}
713
 
714
      template<typename _K1, typename _C1, typename _A1>
715
        friend bool
716
        operator==(const multiset<_K1, _C1, _A1>&,
717
                   const multiset<_K1, _C1, _A1>&);
718
 
719
      template<typename _K1, typename _C1, typename _A1>
720
        friend bool
721
        operator< (const multiset<_K1, _C1, _A1>&,
722
                   const multiset<_K1, _C1, _A1>&);
723
    };
724
 
725
  /**
726
   *  @brief  Multiset equality comparison.
727
   *  @param  __x  A %multiset.
728
   *  @param  __y  A %multiset of the same type as @a __x.
729
   *  @return  True iff the size and elements of the multisets are equal.
730
   *
731
   *  This is an equivalence relation.  It is linear in the size of the
732
   *  multisets.
733
   *  Multisets are considered equivalent if their sizes are equal, and if
734
   *  corresponding elements compare equal.
735
  */
736
  template<typename _Key, typename _Compare, typename _Alloc>
737
    inline bool
738
    operator==(const multiset<_Key, _Compare, _Alloc>& __x,
739
               const multiset<_Key, _Compare, _Alloc>& __y)
740
    { return __x._M_t == __y._M_t; }
741
 
742
  /**
743
   *  @brief  Multiset ordering relation.
744
   *  @param  __x  A %multiset.
745
   *  @param  __y  A %multiset of the same type as @a __x.
746
   *  @return  True iff @a __x is lexicographically less than @a __y.
747
   *
748
   *  This is a total ordering relation.  It is linear in the size of the
749
   *  maps.  The elements must be comparable with @c <.
750
   *
751
   *  See std::lexicographical_compare() for how the determination is made.
752
  */
753
  template<typename _Key, typename _Compare, typename _Alloc>
754
    inline bool
755
    operator<(const multiset<_Key, _Compare, _Alloc>& __x,
756
              const multiset<_Key, _Compare, _Alloc>& __y)
757
    { return __x._M_t < __y._M_t; }
758
 
759
  ///  Returns !(x == y).
760
  template<typename _Key, typename _Compare, typename _Alloc>
761
    inline bool
762
    operator!=(const multiset<_Key, _Compare, _Alloc>& __x,
763
               const multiset<_Key, _Compare, _Alloc>& __y)
764
    { return !(__x == __y); }
765
 
766
  ///  Returns y < x.
767
  template<typename _Key, typename _Compare, typename _Alloc>
768
    inline bool
769
    operator>(const multiset<_Key,_Compare,_Alloc>& __x,
770
              const multiset<_Key,_Compare,_Alloc>& __y)
771
    { return __y < __x; }
772
 
773
  ///  Returns !(y < x)
774
  template<typename _Key, typename _Compare, typename _Alloc>
775
    inline bool
776
    operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
777
               const multiset<_Key, _Compare, _Alloc>& __y)
778
    { return !(__y < __x); }
779
 
780
  ///  Returns !(x < y)
781
  template<typename _Key, typename _Compare, typename _Alloc>
782
    inline bool
783
    operator>=(const multiset<_Key, _Compare, _Alloc>& __x,
784
               const multiset<_Key, _Compare, _Alloc>& __y)
785
    { return !(__x < __y); }
786
 
787
  /// See std::multiset::swap().
788
  template<typename _Key, typename _Compare, typename _Alloc>
789
    inline void
790
    swap(multiset<_Key, _Compare, _Alloc>& __x,
791
         multiset<_Key, _Compare, _Alloc>& __y)
792
    { __x.swap(__y); }
793
 
794
_GLIBCXX_END_NAMESPACE_CONTAINER
795
} // namespace std
796
 
797
#endif /* _STL_MULTISET_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.