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_multimap.h] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// Multimap 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,1997
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_multimap.h
53
 *  This is an internal header file, included by other library headers.
54
 *  Do not attempt to use it directly. @headername{map}
55
 */
56
 
57
#ifndef _STL_MULTIMAP_H
58
#define _STL_MULTIMAP_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 (key,value) pairs, which can be
71
   *  retrieved based on a key, in logarithmic time.
72
   *
73
   *  @ingroup associative_containers
74
   *
75
   *  @tparam _Key  Type of key objects.
76
   *  @tparam  _Tp  Type of mapped objects.
77
   *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
78
   *  @tparam _Alloc  Allocator type, defaults to
79
   *                  allocator<pair<const _Key, _Tp>.
80
   *
81
   *  Meets the requirements of a <a href="tables.html#65">container</a>, a
82
   *  <a href="tables.html#66">reversible container</a>, and an
83
   *  <a href="tables.html#69">associative container</a> (using equivalent
84
   *  keys).  For a @c multimap<Key,T> the key_type is Key, the mapped_type
85
   *  is T, and the value_type is std::pair<const Key,T>.
86
   *
87
   *  Multimaps support bidirectional iterators.
88
   *
89
   *  The private tree data is declared exactly the same way for map and
90
   *  multimap; the distinction is made entirely in how the tree functions are
91
   *  called (*_unique versus *_equal, same as the standard).
92
  */
93
  template <typename _Key, typename _Tp,
94
            typename _Compare = std::less<_Key>,
95
            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
96
    class multimap
97
    {
98
    public:
99
      typedef _Key                                          key_type;
100
      typedef _Tp                                           mapped_type;
101
      typedef std::pair<const _Key, _Tp>                    value_type;
102
      typedef _Compare                                      key_compare;
103
      typedef _Alloc                                        allocator_type;
104
 
105
    private:
106
      // concept requirements
107
      typedef typename _Alloc::value_type                   _Alloc_value_type;
108
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
109
      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
110
                                _BinaryFunctionConcept)
111
      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
112
 
113
    public:
114
      class value_compare
115
      : public std::binary_function<value_type, value_type, bool>
116
      {
117
        friend class multimap<_Key, _Tp, _Compare, _Alloc>;
118
      protected:
119
        _Compare comp;
120
 
121
        value_compare(_Compare __c)
122
        : comp(__c) { }
123
 
124
      public:
125
        bool operator()(const value_type& __x, const value_type& __y) const
126
        { return comp(__x.first, __y.first); }
127
      };
128
 
129
    private:
130
      /// This turns a red-black tree into a [multi]map.
131
      typedef typename _Alloc::template rebind<value_type>::other
132
        _Pair_alloc_type;
133
 
134
      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
135
                       key_compare, _Pair_alloc_type> _Rep_type;
136
      /// The actual tree structure.
137
      _Rep_type _M_t;
138
 
139
    public:
140
      // many of these are specified differently in ISO, but the following are
141
      // "functionally equivalent"
142
      typedef typename _Pair_alloc_type::pointer         pointer;
143
      typedef typename _Pair_alloc_type::const_pointer   const_pointer;
144
      typedef typename _Pair_alloc_type::reference       reference;
145
      typedef typename _Pair_alloc_type::const_reference const_reference;
146
      typedef typename _Rep_type::iterator               iterator;
147
      typedef typename _Rep_type::const_iterator         const_iterator;
148
      typedef typename _Rep_type::size_type              size_type;
149
      typedef typename _Rep_type::difference_type        difference_type;
150
      typedef typename _Rep_type::reverse_iterator       reverse_iterator;
151
      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
152
 
153
      // [23.3.2] construct/copy/destroy
154
      // (get_allocator() is also listed in this section)
155
      /**
156
       *  @brief  Default constructor creates no elements.
157
       */
158
      multimap()
159
      : _M_t() { }
160
 
161
      /**
162
       *  @brief  Creates a %multimap with no elements.
163
       *  @param  __comp  A comparison object.
164
       *  @param  __a  An allocator object.
165
       */
166
      explicit
167
      multimap(const _Compare& __comp,
168
               const allocator_type& __a = allocator_type())
169
      : _M_t(__comp, _Pair_alloc_type(__a)) { }
170
 
171
      /**
172
       *  @brief  %Multimap copy constructor.
173
       *  @param  __x  A %multimap of identical element and allocator types.
174
       *
175
       *  The newly-created %multimap uses a copy of the allocation object
176
       *  used by @a __x.
177
       */
178
      multimap(const multimap& __x)
179
      : _M_t(__x._M_t) { }
180
 
181
#if __cplusplus >= 201103L
182
      /**
183
       *  @brief  %Multimap move constructor.
184
       *  @param   __x  A %multimap of identical element and allocator types.
185
       *
186
       *  The newly-created %multimap contains the exact contents of @a __x.
187
       *  The contents of @a __x are a valid, but unspecified %multimap.
188
       */
189
      multimap(multimap&& __x)
190
      noexcept(is_nothrow_copy_constructible<_Compare>::value)
191
      : _M_t(std::move(__x._M_t)) { }
192
 
193
      /**
194
       *  @brief  Builds a %multimap from an initializer_list.
195
       *  @param  __l  An initializer_list.
196
       *  @param  __comp  A comparison functor.
197
       *  @param  __a  An allocator object.
198
       *
199
       *  Create a %multimap consisting of copies of the elements from
200
       *  the initializer_list.  This is linear in N if the list is already
201
       *  sorted, and NlogN otherwise (where N is @a __l.size()).
202
       */
203
      multimap(initializer_list<value_type> __l,
204
               const _Compare& __comp = _Compare(),
205
               const allocator_type& __a = allocator_type())
206
      : _M_t(__comp, _Pair_alloc_type(__a))
207
      { _M_t._M_insert_equal(__l.begin(), __l.end()); }
208
#endif
209
 
210
      /**
211
       *  @brief  Builds a %multimap from a range.
212
       *  @param  __first  An input iterator.
213
       *  @param  __last  An input iterator.
214
       *
215
       *  Create a %multimap consisting of copies of the elements from
216
       *  [__first,__last).  This is linear in N if the range is already sorted,
217
       *  and NlogN otherwise (where N is distance(__first,__last)).
218
       */
219
      template<typename _InputIterator>
220
        multimap(_InputIterator __first, _InputIterator __last)
221
        : _M_t()
222
        { _M_t._M_insert_equal(__first, __last); }
223
 
224
      /**
225
       *  @brief  Builds a %multimap from a range.
226
       *  @param  __first  An input iterator.
227
       *  @param  __last  An input iterator.
228
       *  @param  __comp  A comparison functor.
229
       *  @param  __a  An allocator object.
230
       *
231
       *  Create a %multimap consisting of copies of the elements from
232
       *  [__first,__last).  This is linear in N if the range is already sorted,
233
       *  and NlogN otherwise (where N is distance(__first,__last)).
234
       */
235
      template<typename _InputIterator>
236
        multimap(_InputIterator __first, _InputIterator __last,
237
                 const _Compare& __comp,
238
                 const allocator_type& __a = allocator_type())
239
        : _M_t(__comp, _Pair_alloc_type(__a))
240
        { _M_t._M_insert_equal(__first, __last); }
241
 
242
      // FIXME There is no dtor declared, but we should have something generated
243
      // by Doxygen.  I don't know what tags to add to this paragraph to make
244
      // that happen:
245
      /**
246
       *  The dtor only erases the elements, and note that if the elements
247
       *  themselves are pointers, the pointed-to memory is not touched in any
248
       *  way.  Managing the pointer is the user's responsibility.
249
       */
250
 
251
      /**
252
       *  @brief  %Multimap assignment operator.
253
       *  @param  __x  A %multimap of identical element and allocator types.
254
       *
255
       *  All the elements of @a __x are copied, but unlike the copy
256
       *  constructor, the allocator object is not copied.
257
       */
258
      multimap&
259
      operator=(const multimap& __x)
260
      {
261
        _M_t = __x._M_t;
262
        return *this;
263
      }
264
 
265
#if __cplusplus >= 201103L
266
      /**
267
       *  @brief  %Multimap move assignment operator.
268
       *  @param  __x  A %multimap of identical element and allocator types.
269
       *
270
       *  The contents of @a __x are moved into this multimap (without copying).
271
       *  @a __x is a valid, but unspecified multimap.
272
       */
273
      multimap&
274
      operator=(multimap&& __x)
275
      {
276
        // NB: DR 1204.
277
        // NB: DR 675.
278
        this->clear();
279
        this->swap(__x);
280
        return *this;
281
      }
282
 
283
      /**
284
       *  @brief  %Multimap list assignment operator.
285
       *  @param  __l  An initializer_list.
286
       *
287
       *  This function fills a %multimap with copies of the elements
288
       *  in the initializer list @a __l.
289
       *
290
       *  Note that the assignment completely changes the %multimap and
291
       *  that the resulting %multimap's size is the same as the number
292
       *  of elements assigned.  Old data may be lost.
293
       */
294
      multimap&
295
      operator=(initializer_list<value_type> __l)
296
      {
297
        this->clear();
298
        this->insert(__l.begin(), __l.end());
299
        return *this;
300
      }
301
#endif
302
 
303
      /// Get a copy of the memory allocation object.
304
      allocator_type
305
      get_allocator() const _GLIBCXX_NOEXCEPT
306
      { return allocator_type(_M_t.get_allocator()); }
307
 
308
      // iterators
309
      /**
310
       *  Returns a read/write iterator that points to the first pair in the
311
       *  %multimap.  Iteration is done in ascending order according to the
312
       *  keys.
313
       */
314
      iterator
315
      begin() _GLIBCXX_NOEXCEPT
316
      { return _M_t.begin(); }
317
 
318
      /**
319
       *  Returns a read-only (constant) iterator that points to the first pair
320
       *  in the %multimap.  Iteration is done in ascending order according to
321
       *  the keys.
322
       */
323
      const_iterator
324
      begin() const _GLIBCXX_NOEXCEPT
325
      { return _M_t.begin(); }
326
 
327
      /**
328
       *  Returns a read/write iterator that points one past the last pair in
329
       *  the %multimap.  Iteration is done in ascending order according to the
330
       *  keys.
331
       */
332
      iterator
333
      end() _GLIBCXX_NOEXCEPT
334
      { return _M_t.end(); }
335
 
336
      /**
337
       *  Returns a read-only (constant) iterator that points one past the last
338
       *  pair in the %multimap.  Iteration is done in ascending order according
339
       *  to the keys.
340
       */
341
      const_iterator
342
      end() const _GLIBCXX_NOEXCEPT
343
      { return _M_t.end(); }
344
 
345
      /**
346
       *  Returns a read/write reverse iterator that points to the last pair in
347
       *  the %multimap.  Iteration is done in descending order according to the
348
       *  keys.
349
       */
350
      reverse_iterator
351
      rbegin() _GLIBCXX_NOEXCEPT
352
      { return _M_t.rbegin(); }
353
 
354
      /**
355
       *  Returns a read-only (constant) reverse iterator that points to the
356
       *  last pair in the %multimap.  Iteration is done in descending order
357
       *  according to the keys.
358
       */
359
      const_reverse_iterator
360
      rbegin() const _GLIBCXX_NOEXCEPT
361
      { return _M_t.rbegin(); }
362
 
363
      /**
364
       *  Returns a read/write reverse iterator that points to one before the
365
       *  first pair in the %multimap.  Iteration is done in descending order
366
       *  according to the keys.
367
       */
368
      reverse_iterator
369
      rend() _GLIBCXX_NOEXCEPT
370
      { return _M_t.rend(); }
371
 
372
      /**
373
       *  Returns a read-only (constant) reverse iterator that points to one
374
       *  before the first pair in the %multimap.  Iteration is done in
375
       *  descending order according to the keys.
376
       */
377
      const_reverse_iterator
378
      rend() const _GLIBCXX_NOEXCEPT
379
      { return _M_t.rend(); }
380
 
381
#if __cplusplus >= 201103L
382
      /**
383
       *  Returns a read-only (constant) iterator that points to the first pair
384
       *  in the %multimap.  Iteration is done in ascending order according to
385
       *  the keys.
386
       */
387
      const_iterator
388
      cbegin() const noexcept
389
      { return _M_t.begin(); }
390
 
391
      /**
392
       *  Returns a read-only (constant) iterator that points one past the last
393
       *  pair in the %multimap.  Iteration is done in ascending order according
394
       *  to the keys.
395
       */
396
      const_iterator
397
      cend() const noexcept
398
      { return _M_t.end(); }
399
 
400
      /**
401
       *  Returns a read-only (constant) reverse iterator that points to the
402
       *  last pair in the %multimap.  Iteration is done in descending order
403
       *  according to the keys.
404
       */
405
      const_reverse_iterator
406
      crbegin() const noexcept
407
      { return _M_t.rbegin(); }
408
 
409
      /**
410
       *  Returns a read-only (constant) reverse iterator that points to one
411
       *  before the first pair in the %multimap.  Iteration is done in
412
       *  descending order according to the keys.
413
       */
414
      const_reverse_iterator
415
      crend() const noexcept
416
      { return _M_t.rend(); }
417
#endif
418
 
419
      // capacity
420
      /** Returns true if the %multimap is empty.  */
421
      bool
422
      empty() const _GLIBCXX_NOEXCEPT
423
      { return _M_t.empty(); }
424
 
425
      /** Returns the size of the %multimap.  */
426
      size_type
427
      size() const _GLIBCXX_NOEXCEPT
428
      { return _M_t.size(); }
429
 
430
      /** Returns the maximum size of the %multimap.  */
431
      size_type
432
      max_size() const _GLIBCXX_NOEXCEPT
433
      { return _M_t.max_size(); }
434
 
435
      // modifiers
436
#if __cplusplus >= 201103L
437
      /**
438
       *  @brief Build and insert a std::pair into the %multimap.
439
       *
440
       *  @param __args  Arguments used to generate a new pair instance (see
441
       *                std::piecewise_contruct for passing arguments to each
442
       *                part of the pair constructor).
443
       *
444
       *  @return An iterator that points to the inserted (key,value) pair.
445
       *
446
       *  This function builds and inserts a (key, value) %pair into the
447
       *  %multimap.
448
       *  Contrary to a std::map the %multimap does not rely on unique keys and
449
       *  thus multiple pairs with the same key can be inserted.
450
       *
451
       *  Insertion requires logarithmic time.
452
       */
453
      template<typename... _Args>
454
        iterator
455
        emplace(_Args&&... __args)
456
        { return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
457
 
458
      /**
459
       *  @brief Builds and inserts a std::pair into the %multimap.
460
       *
461
       *  @param  __pos  An iterator that serves as a hint as to where the pair
462
       *                should be inserted.
463
       *  @param  __args  Arguments used to generate a new pair instance (see
464
       *                 std::piecewise_contruct for passing arguments to each
465
       *                 part of the pair constructor).
466
       *  @return An iterator that points to the inserted (key,value) pair.
467
       *
468
       *  This function inserts a (key, value) pair into the %multimap.
469
       *  Contrary to a std::map the %multimap does not rely on unique keys and
470
       *  thus multiple pairs with the same key can be inserted.
471
       *  Note that the first parameter is only a hint and can potentially
472
       *  improve the performance of the insertion process.  A bad hint would
473
       *  cause no gains in efficiency.
474
       *
475
       *  For more on @a hinting, see:
476
       *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
477
       *
478
       *  Insertion requires logarithmic time (if the hint is not taken).
479
       */
480
      template<typename... _Args>
481
        iterator
482
        emplace_hint(const_iterator __pos, _Args&&... __args)
483
        {
484
          return _M_t._M_emplace_hint_equal(__pos,
485
                                            std::forward<_Args>(__args)...);
486
        }
487
#endif
488
 
489
      /**
490
       *  @brief Inserts a std::pair into the %multimap.
491
       *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
492
       *             of pairs).
493
       *  @return An iterator that points to the inserted (key,value) pair.
494
       *
495
       *  This function inserts a (key, value) pair into the %multimap.
496
       *  Contrary to a std::map the %multimap does not rely on unique keys and
497
       *  thus multiple pairs with the same key can be inserted.
498
       *
499
       *  Insertion requires logarithmic time.
500
       */
501
      iterator
502
      insert(const value_type& __x)
503
      { return _M_t._M_insert_equal(__x); }
504
 
505
#if __cplusplus >= 201103L
506
      template<typename _Pair, typename = typename
507
               std::enable_if<std::is_constructible<value_type,
508
                                                    _Pair&&>::value>::type>
509
        iterator
510
        insert(_Pair&& __x)
511
        { return _M_t._M_insert_equal(std::forward<_Pair>(__x)); }
512
#endif
513
 
514
      /**
515
       *  @brief Inserts a std::pair into the %multimap.
516
       *  @param  __position  An iterator that serves as a hint as to where the
517
       *                      pair should be inserted.
518
       *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
519
       *               of pairs).
520
       *  @return An iterator that points to the inserted (key,value) pair.
521
       *
522
       *  This function inserts a (key, value) pair into the %multimap.
523
       *  Contrary to a std::map the %multimap does not rely on unique keys and
524
       *  thus multiple pairs with the same key can be inserted.
525
       *  Note that the first parameter is only a hint and can potentially
526
       *  improve the performance of the insertion process.  A bad hint would
527
       *  cause no gains in efficiency.
528
       *
529
       *  For more on @a hinting, see:
530
       *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
531
       *
532
       *  Insertion requires logarithmic time (if the hint is not taken).
533
       */
534
      iterator
535
#if __cplusplus >= 201103L
536
      insert(const_iterator __position, const value_type& __x)
537
#else
538
      insert(iterator __position, const value_type& __x)
539
#endif
540
      { return _M_t._M_insert_equal_(__position, __x); }
541
 
542
#if __cplusplus >= 201103L
543
      template<typename _Pair, typename = typename
544
               std::enable_if<std::is_constructible<value_type,
545
                                                    _Pair&&>::value>::type>
546
        iterator
547
        insert(const_iterator __position, _Pair&& __x)
548
        { return _M_t._M_insert_equal_(__position,
549
                                       std::forward<_Pair>(__x)); }
550
#endif
551
 
552
      /**
553
       *  @brief A template function that attempts to insert a range
554
       *  of elements.
555
       *  @param  __first  Iterator pointing to the start of the range to be
556
       *                   inserted.
557
       *  @param  __last  Iterator pointing to the end of the range.
558
       *
559
       *  Complexity similar to that of the range constructor.
560
       */
561
      template<typename _InputIterator>
562
        void
563
        insert(_InputIterator __first, _InputIterator __last)
564
        { _M_t._M_insert_equal(__first, __last); }
565
 
566
#if __cplusplus >= 201103L
567
      /**
568
       *  @brief Attempts to insert a list of std::pairs into the %multimap.
569
       *  @param  __l  A std::initializer_list<value_type> of pairs to be
570
       *               inserted.
571
       *
572
       *  Complexity similar to that of the range constructor.
573
       */
574
      void
575
      insert(initializer_list<value_type> __l)
576
      { this->insert(__l.begin(), __l.end()); }
577
#endif
578
 
579
#if __cplusplus >= 201103L
580
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
581
      // DR 130. Associative erase should return an iterator.
582
      /**
583
       *  @brief Erases an element from a %multimap.
584
       *  @param  __position  An iterator pointing to the element to be erased.
585
       *  @return An iterator pointing to the element immediately following
586
       *          @a position prior to the element being erased. If no such
587
       *          element exists, end() is returned.
588
       *
589
       *  This function erases an element, pointed to by the given iterator,
590
       *  from a %multimap.  Note that this function only erases the element,
591
       *  and that if the element is itself a pointer, the pointed-to memory is
592
       *  not touched in any way.  Managing the pointer is the user's
593
       *  responsibility.
594
       */
595
      iterator
596
      erase(const_iterator __position)
597
      { return _M_t.erase(__position); }
598
 
599
      // LWG 2059.
600
      iterator
601
      erase(iterator __position)
602
      { return _M_t.erase(__position); }
603
#else
604
      /**
605
       *  @brief Erases an element from a %multimap.
606
       *  @param  __position  An iterator pointing to the element to be erased.
607
       *
608
       *  This function erases an element, pointed to by the given iterator,
609
       *  from a %multimap.  Note that this function only erases the element,
610
       *  and that if the element is itself a pointer, the pointed-to memory is
611
       *  not touched in any way.  Managing the pointer is the user's
612
       *  responsibility.
613
       */
614
      void
615
      erase(iterator __position)
616
      { _M_t.erase(__position); }
617
#endif
618
 
619
      /**
620
       *  @brief Erases elements according to the provided key.
621
       *  @param  __x  Key of element to be erased.
622
       *  @return  The number of elements erased.
623
       *
624
       *  This function erases all elements located by the given key from a
625
       *  %multimap.
626
       *  Note that this function only erases the element, and that if
627
       *  the element is itself a pointer, the pointed-to memory is not touched
628
       *  in any way.  Managing the pointer is the user's responsibility.
629
       */
630
      size_type
631
      erase(const key_type& __x)
632
      { return _M_t.erase(__x); }
633
 
634
#if __cplusplus >= 201103L
635
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
636
      // DR 130. Associative erase should return an iterator.
637
      /**
638
       *  @brief Erases a [first,last) range of elements from a %multimap.
639
       *  @param  __first  Iterator pointing to the start of the range to be
640
       *                   erased.
641
       *  @param __last Iterator pointing to the end of the range to be
642
       *                erased .
643
       *  @return The iterator @a __last.
644
       *
645
       *  This function erases a sequence of elements from a %multimap.
646
       *  Note that this function only erases the elements, and that if
647
       *  the elements themselves are pointers, the pointed-to memory is not
648
       *  touched in any way.  Managing the pointer is the user's
649
       *  responsibility.
650
       */
651
      iterator
652
      erase(const_iterator __first, const_iterator __last)
653
      { return _M_t.erase(__first, __last); }
654
#else
655
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
656
      // DR 130. Associative erase should return an iterator.
657
      /**
658
       *  @brief Erases a [first,last) range of elements from a %multimap.
659
       *  @param  __first  Iterator pointing to the start of the range to be
660
       *                 erased.
661
       *  @param __last Iterator pointing to the end of the range to
662
       *                be erased.
663
       *
664
       *  This function erases a sequence of elements from a %multimap.
665
       *  Note that this function only erases the elements, and that if
666
       *  the elements themselves are pointers, the pointed-to memory is not
667
       *  touched in any way.  Managing the pointer is the user's
668
       *  responsibility.
669
       */
670
      void
671
      erase(iterator __first, iterator __last)
672
      { _M_t.erase(__first, __last); }
673
#endif
674
 
675
      /**
676
       *  @brief  Swaps data with another %multimap.
677
       *  @param  __x  A %multimap of the same element and allocator types.
678
       *
679
       *  This exchanges the elements between two multimaps in constant time.
680
       *  (It is only swapping a pointer, an integer, and an instance of
681
       *  the @c Compare type (which itself is often stateless and empty), so it
682
       *  should be quite fast.)
683
       *  Note that the global std::swap() function is specialized such that
684
       *  std::swap(m1,m2) will feed to this function.
685
       */
686
      void
687
      swap(multimap& __x)
688
      { _M_t.swap(__x._M_t); }
689
 
690
      /**
691
       *  Erases all elements in a %multimap.  Note that this function only
692
       *  erases the elements, and that if the elements themselves are pointers,
693
       *  the pointed-to memory is not touched in any way.  Managing the pointer
694
       *  is the user's responsibility.
695
       */
696
      void
697
      clear() _GLIBCXX_NOEXCEPT
698
      { _M_t.clear(); }
699
 
700
      // observers
701
      /**
702
       *  Returns the key comparison object out of which the %multimap
703
       *  was constructed.
704
       */
705
      key_compare
706
      key_comp() const
707
      { return _M_t.key_comp(); }
708
 
709
      /**
710
       *  Returns a value comparison object, built from the key comparison
711
       *  object out of which the %multimap was constructed.
712
       */
713
      value_compare
714
      value_comp() const
715
      { return value_compare(_M_t.key_comp()); }
716
 
717
      // multimap operations
718
      /**
719
       *  @brief Tries to locate an element in a %multimap.
720
       *  @param  __x  Key of (key, value) pair to be located.
721
       *  @return  Iterator pointing to sought-after element,
722
       *           or end() if not found.
723
       *
724
       *  This function takes a key and tries to locate the element with which
725
       *  the key matches.  If successful the function returns an iterator
726
       *  pointing to the sought after %pair.  If unsuccessful it returns the
727
       *  past-the-end ( @c end() ) iterator.
728
       */
729
      iterator
730
      find(const key_type& __x)
731
      { return _M_t.find(__x); }
732
 
733
      /**
734
       *  @brief Tries to locate an element in a %multimap.
735
       *  @param  __x  Key of (key, value) pair to be located.
736
       *  @return  Read-only (constant) iterator pointing to sought-after
737
       *           element, or end() if not found.
738
       *
739
       *  This function takes a key and tries to locate the element with which
740
       *  the key matches.  If successful the function returns a constant
741
       *  iterator pointing to the sought after %pair.  If unsuccessful it
742
       *  returns the past-the-end ( @c end() ) iterator.
743
       */
744
      const_iterator
745
      find(const key_type& __x) const
746
      { return _M_t.find(__x); }
747
 
748
      /**
749
       *  @brief Finds the number of elements with given key.
750
       *  @param  __x  Key of (key, value) pairs to be located.
751
       *  @return Number of elements with specified key.
752
       */
753
      size_type
754
      count(const key_type& __x) const
755
      { return _M_t.count(__x); }
756
 
757
      /**
758
       *  @brief Finds the beginning of a subsequence matching given key.
759
       *  @param  __x  Key of (key, value) pair to be located.
760
       *  @return  Iterator pointing to first element equal to or greater
761
       *           than key, or end().
762
       *
763
       *  This function returns the first element of a subsequence of elements
764
       *  that matches the given key.  If unsuccessful it returns an iterator
765
       *  pointing to the first element that has a greater value than given key
766
       *  or end() if no such element exists.
767
       */
768
      iterator
769
      lower_bound(const key_type& __x)
770
      { return _M_t.lower_bound(__x); }
771
 
772
      /**
773
       *  @brief Finds the beginning of a subsequence matching given key.
774
       *  @param  __x  Key of (key, value) pair to be located.
775
       *  @return  Read-only (constant) iterator pointing to first element
776
       *           equal to or greater than key, or end().
777
       *
778
       *  This function returns the first element of a subsequence of
779
       *  elements that matches the given key.  If unsuccessful the
780
       *  iterator will point to the next greatest element or, if no
781
       *  such greater element exists, to end().
782
       */
783
      const_iterator
784
      lower_bound(const key_type& __x) const
785
      { return _M_t.lower_bound(__x); }
786
 
787
      /**
788
       *  @brief Finds the end of a subsequence matching given key.
789
       *  @param  __x  Key of (key, value) pair to be located.
790
       *  @return Iterator pointing to the first element
791
       *          greater than key, or end().
792
       */
793
      iterator
794
      upper_bound(const key_type& __x)
795
      { return _M_t.upper_bound(__x); }
796
 
797
      /**
798
       *  @brief Finds the end of a subsequence matching given key.
799
       *  @param  __x  Key of (key, value) pair to be located.
800
       *  @return  Read-only (constant) iterator pointing to first iterator
801
       *           greater than key, or end().
802
       */
803
      const_iterator
804
      upper_bound(const key_type& __x) const
805
      { return _M_t.upper_bound(__x); }
806
 
807
      /**
808
       *  @brief Finds a subsequence matching given key.
809
       *  @param  __x  Key of (key, value) pairs to be located.
810
       *  @return  Pair of iterators that possibly points to the subsequence
811
       *           matching given key.
812
       *
813
       *  This function is equivalent to
814
       *  @code
815
       *    std::make_pair(c.lower_bound(val),
816
       *                   c.upper_bound(val))
817
       *  @endcode
818
       *  (but is faster than making the calls separately).
819
       */
820
      std::pair<iterator, iterator>
821
      equal_range(const key_type& __x)
822
      { return _M_t.equal_range(__x); }
823
 
824
      /**
825
       *  @brief Finds a subsequence matching given key.
826
       *  @param  __x  Key of (key, value) pairs to be located.
827
       *  @return  Pair of read-only (constant) iterators that possibly points
828
       *           to the subsequence matching given key.
829
       *
830
       *  This function is equivalent to
831
       *  @code
832
       *    std::make_pair(c.lower_bound(val),
833
       *                   c.upper_bound(val))
834
       *  @endcode
835
       *  (but is faster than making the calls separately).
836
       */
837
      std::pair<const_iterator, const_iterator>
838
      equal_range(const key_type& __x) const
839
      { return _M_t.equal_range(__x); }
840
 
841
      template<typename _K1, typename _T1, typename _C1, typename _A1>
842
        friend bool
843
        operator==(const multimap<_K1, _T1, _C1, _A1>&,
844
                   const multimap<_K1, _T1, _C1, _A1>&);
845
 
846
      template<typename _K1, typename _T1, typename _C1, typename _A1>
847
        friend bool
848
        operator<(const multimap<_K1, _T1, _C1, _A1>&,
849
                  const multimap<_K1, _T1, _C1, _A1>&);
850
  };
851
 
852
  /**
853
   *  @brief  Multimap equality comparison.
854
   *  @param  __x  A %multimap.
855
   *  @param  __y  A %multimap of the same type as @a __x.
856
   *  @return  True iff the size and elements of the maps are equal.
857
   *
858
   *  This is an equivalence relation.  It is linear in the size of the
859
   *  multimaps.  Multimaps are considered equivalent if their sizes are equal,
860
   *  and if corresponding elements compare equal.
861
  */
862
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
863
    inline bool
864
    operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
865
               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
866
    { return __x._M_t == __y._M_t; }
867
 
868
  /**
869
   *  @brief  Multimap ordering relation.
870
   *  @param  __x  A %multimap.
871
   *  @param  __y  A %multimap of the same type as @a __x.
872
   *  @return  True iff @a x is lexicographically less than @a y.
873
   *
874
   *  This is a total ordering relation.  It is linear in the size of the
875
   *  multimaps.  The elements must be comparable with @c <.
876
   *
877
   *  See std::lexicographical_compare() for how the determination is made.
878
  */
879
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
880
    inline bool
881
    operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
882
              const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
883
    { return __x._M_t < __y._M_t; }
884
 
885
  /// Based on operator==
886
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
887
    inline bool
888
    operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
889
               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
890
    { return !(__x == __y); }
891
 
892
  /// Based on operator<
893
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
894
    inline bool
895
    operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
896
              const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
897
    { return __y < __x; }
898
 
899
  /// Based on operator<
900
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
901
    inline bool
902
    operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
903
               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
904
    { return !(__y < __x); }
905
 
906
  /// Based on operator<
907
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
908
    inline bool
909
    operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
910
               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
911
    { return !(__x < __y); }
912
 
913
  /// See std::multimap::swap().
914
  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
915
    inline void
916
    swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
917
         multimap<_Key, _Tp, _Compare, _Alloc>& __y)
918
    { __x.swap(__y); }
919
 
920
_GLIBCXX_END_NAMESPACE_CONTAINER
921
} // namespace std
922
 
923
#endif /* _STL_MULTIMAP_H */

powered by: WebSVN 2.1.0

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