libstdc++
stl_multiset.h
Go to the documentation of this file.
1 // Multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // 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 stl_multiset.h
53  * This is an internal header file, included by other library headers.
54  * You should not attempt to use it directly.
55  */
56 
57 #ifndef _STL_MULTISET_H
58 #define _STL_MULTISET_H 1
59 
60 #include <bits/concept_check.h>
61 #include <initializer_list>
62 
63 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
64 
65  /**
66  * @brief A standard container made up of elements, which can be retrieved
67  * in logarithmic time.
68  *
69  * @ingroup associative_containers
70  *
71  * Meets the requirements of a <a href="tables.html#65">container</a>, a
72  * <a href="tables.html#66">reversible container</a>, and an
73  * <a href="tables.html#69">associative container</a> (using equivalent
74  * keys). For a @c multiset<Key> the key_type and value_type are Key.
75  *
76  * Multisets support bidirectional iterators.
77  *
78  * The private tree data is declared exactly the same way for set and
79  * multiset; the distinction is made entirely in how the tree functions are
80  * called (*_unique versus *_equal, same as the standard).
81  */
82  template <typename _Key, typename _Compare = std::less<_Key>,
83  typename _Alloc = std::allocator<_Key> >
84  class multiset
85  {
86  // concept requirements
87  typedef typename _Alloc::value_type _Alloc_value_type;
88  __glibcxx_class_requires(_Key, _SGIAssignableConcept)
89  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
90  _BinaryFunctionConcept)
91  __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
92 
93  public:
94  // typedefs:
95  typedef _Key key_type;
96  typedef _Key value_type;
97  typedef _Compare key_compare;
98  typedef _Compare value_compare;
99  typedef _Alloc allocator_type;
100 
101  private:
102  /// This turns a red-black tree into a [multi]set.
103  typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
104 
105  typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
106  key_compare, _Key_alloc_type> _Rep_type;
107  /// The actual tree structure.
108  _Rep_type _M_t;
109 
110  public:
111  typedef typename _Key_alloc_type::pointer pointer;
112  typedef typename _Key_alloc_type::const_pointer const_pointer;
113  typedef typename _Key_alloc_type::reference reference;
114  typedef typename _Key_alloc_type::const_reference const_reference;
115  // _GLIBCXX_RESOLVE_LIB_DEFECTS
116  // DR 103. set::iterator is required to be modifiable,
117  // but this allows modification of keys.
118  typedef typename _Rep_type::const_iterator iterator;
119  typedef typename _Rep_type::const_iterator const_iterator;
122  typedef typename _Rep_type::size_type size_type;
123  typedef typename _Rep_type::difference_type difference_type;
124 
125  // allocation/deallocation
126  /**
127  * @brief Default constructor creates no elements.
128  */
129  multiset()
130  : _M_t() { }
131 
132  /**
133  * @brief Creates a %multiset with no elements.
134  * @param comp Comparator to use.
135  * @param a An allocator object.
136  */
137  explicit
138  multiset(const _Compare& __comp,
139  const allocator_type& __a = allocator_type())
140  : _M_t(__comp, __a) { }
141 
142  /**
143  * @brief Builds a %multiset from a range.
144  * @param first An input iterator.
145  * @param last An input iterator.
146  *
147  * Create a %multiset consisting of copies of the elements from
148  * [first,last). This is linear in N if the range is already sorted,
149  * and NlogN otherwise (where N is distance(first,last)).
150  */
151  template<typename _InputIterator>
152  multiset(_InputIterator __first, _InputIterator __last)
153  : _M_t()
154  { _M_t._M_insert_equal(__first, __last); }
155 
156  /**
157  * @brief Builds a %multiset from a range.
158  * @param first An input iterator.
159  * @param last An input iterator.
160  * @param comp A comparison functor.
161  * @param a An allocator object.
162  *
163  * Create a %multiset consisting of copies of the elements from
164  * [first,last). This is linear in N if the range is already sorted,
165  * and NlogN otherwise (where N is distance(first,last)).
166  */
167  template<typename _InputIterator>
168  multiset(_InputIterator __first, _InputIterator __last,
169  const _Compare& __comp,
170  const allocator_type& __a = allocator_type())
171  : _M_t(__comp, __a)
172  { _M_t._M_insert_equal(__first, __last); }
173 
174  /**
175  * @brief %Multiset copy constructor.
176  * @param x A %multiset of identical element and allocator types.
177  *
178  * The newly-created %multiset uses a copy of the allocation object used
179  * by @a x.
180  */
181  multiset(const multiset& __x)
182  : _M_t(__x._M_t) { }
183 
184 #ifdef __GXX_EXPERIMENTAL_CXX0X__
185  /**
186  * @brief %Multiset move constructor.
187  * @param x A %multiset of identical element and allocator types.
188  *
189  * The newly-created %multiset contains the exact contents of @a x.
190  * The contents of @a x are a valid, but unspecified %multiset.
191  */
192  multiset(multiset&& __x)
193  : _M_t(std::forward<_Rep_type>(__x._M_t)) { }
194 
195  /**
196  * @brief Builds a %multiset from an initializer_list.
197  * @param l An initializer_list.
198  * @param comp A comparison functor.
199  * @param a An allocator object.
200  *
201  * Create a %multiset consisting of copies of the elements from
202  * the list. This is linear in N if the list is already sorted,
203  * and NlogN otherwise (where N is @a l.size()).
204  */
206  const _Compare& __comp = _Compare(),
207  const allocator_type& __a = allocator_type())
208  : _M_t(__comp, __a)
209  { _M_t._M_insert_equal(__l.begin(), __l.end()); }
210 #endif
211 
212  /**
213  * @brief %Multiset assignment operator.
214  * @param x A %multiset of identical element and allocator types.
215  *
216  * All the elements of @a x are copied, but unlike the copy constructor,
217  * the allocator object is not copied.
218  */
219  multiset&
220  operator=(const multiset& __x)
221  {
222  _M_t = __x._M_t;
223  return *this;
224  }
225 
226 #ifdef __GXX_EXPERIMENTAL_CXX0X__
227  /**
228  * @brief %Multiset move assignment operator.
229  * @param x A %multiset of identical element and allocator types.
230  *
231  * The contents of @a x are moved into this %multiset (without copying).
232  * @a x is a valid, but unspecified %multiset.
233  */
234  multiset&
235  operator=(multiset&& __x)
236  {
237  // NB: DR 675.
238  this->clear();
239  this->swap(__x);
240  return *this;
241  }
242 
243  /**
244  * @brief %Multiset list assignment operator.
245  * @param l An initializer_list.
246  *
247  * This function fills a %multiset with copies of the elements in the
248  * initializer list @a l.
249  *
250  * Note that the assignment completely changes the %multiset and
251  * that the resulting %multiset's size is the same as the number
252  * of elements assigned. Old data may be lost.
253  */
254  multiset&
256  {
257  this->clear();
258  this->insert(__l.begin(), __l.end());
259  return *this;
260  }
261 #endif
262 
263  // accessors:
264 
265  /// Returns the comparison object.
266  key_compare
267  key_comp() const
268  { return _M_t.key_comp(); }
269  /// Returns the comparison object.
270  value_compare
271  value_comp() const
272  { return _M_t.key_comp(); }
273  /// Returns the memory allocation object.
274  allocator_type
275  get_allocator() const
276  { return _M_t.get_allocator(); }
277 
278  /**
279  * Returns a read-only (constant) iterator that points to the first
280  * element in the %multiset. Iteration is done in ascending order
281  * according to the keys.
282  */
283  iterator
284  begin() const
285  { return _M_t.begin(); }
286 
287  /**
288  * Returns a read-only (constant) iterator that points one past the last
289  * element in the %multiset. Iteration is done in ascending order
290  * according to the keys.
291  */
292  iterator
293  end() const
294  { return _M_t.end(); }
295 
296  /**
297  * Returns a read-only (constant) reverse iterator that points to the
298  * last element in the %multiset. Iteration is done in descending order
299  * according to the keys.
300  */
301  reverse_iterator
302  rbegin() const
303  { return _M_t.rbegin(); }
304 
305  /**
306  * Returns a read-only (constant) reverse iterator that points to the
307  * last element in the %multiset. Iteration is done in descending order
308  * according to the keys.
309  */
310  reverse_iterator
311  rend() const
312  { return _M_t.rend(); }
313 
314 #ifdef __GXX_EXPERIMENTAL_CXX0X__
315  /**
316  * Returns a read-only (constant) iterator that points to the first
317  * element in the %multiset. Iteration is done in ascending order
318  * according to the keys.
319  */
320  iterator
321  cbegin() const
322  { return _M_t.begin(); }
323 
324  /**
325  * Returns a read-only (constant) iterator that points one past the last
326  * element in the %multiset. Iteration is done in ascending order
327  * according to the keys.
328  */
329  iterator
330  cend() const
331  { return _M_t.end(); }
332 
333  /**
334  * Returns a read-only (constant) reverse iterator that points to the
335  * last element in the %multiset. Iteration is done in descending order
336  * according to the keys.
337  */
338  reverse_iterator
339  crbegin() const
340  { return _M_t.rbegin(); }
341 
342  /**
343  * Returns a read-only (constant) reverse iterator that points to the
344  * last element in the %multiset. Iteration is done in descending order
345  * according to the keys.
346  */
347  reverse_iterator
348  crend() const
349  { return _M_t.rend(); }
350 #endif
351 
352  /// Returns true if the %set is empty.
353  bool
354  empty() const
355  { return _M_t.empty(); }
356 
357  /// Returns the size of the %set.
358  size_type
359  size() const
360  { return _M_t.size(); }
361 
362  /// Returns the maximum size of the %set.
363  size_type
364  max_size() const
365  { return _M_t.max_size(); }
366 
367  /**
368  * @brief Swaps data with another %multiset.
369  * @param x A %multiset of the same element and allocator types.
370  *
371  * This exchanges the elements between two multisets in constant time.
372  * (It is only swapping a pointer, an integer, and an instance of the @c
373  * Compare type (which itself is often stateless and empty), so it should
374  * be quite fast.)
375  * Note that the global std::swap() function is specialized such that
376  * std::swap(s1,s2) will feed to this function.
377  */
378  void
379 #ifdef __GXX_EXPERIMENTAL_CXX0X__
380  swap(multiset&& __x)
381 #else
382  swap(multiset& __x)
383 #endif
384  { _M_t.swap(__x._M_t); }
385 
386  // insert/erase
387  /**
388  * @brief Inserts an element into the %multiset.
389  * @param x Element to be inserted.
390  * @return An iterator that points to the inserted element.
391  *
392  * This function inserts an element into the %multiset. Contrary
393  * to a std::set the %multiset does not rely on unique keys and thus
394  * multiple copies of the same element can be inserted.
395  *
396  * Insertion requires logarithmic time.
397  */
398  iterator
399  insert(const value_type& __x)
400  { return _M_t._M_insert_equal(__x); }
401 
402  /**
403  * @brief Inserts an element into the %multiset.
404  * @param position An iterator that serves as a hint as to where the
405  * element should be inserted.
406  * @param x Element to be inserted.
407  * @return An iterator that points to the inserted element.
408  *
409  * This function inserts an element into the %multiset. Contrary
410  * to a std::set the %multiset does not rely on unique keys and thus
411  * multiple copies of the same element can be inserted.
412  *
413  * Note that the first parameter is only a hint and can potentially
414  * improve the performance of the insertion process. A bad hint would
415  * cause no gains in efficiency.
416  *
417  * See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
418  * for more on "hinting".
419  *
420  * Insertion requires logarithmic time (if the hint is not taken).
421  */
422  iterator
423  insert(iterator __position, const value_type& __x)
424  { return _M_t._M_insert_equal_(__position, __x); }
425 
426  /**
427  * @brief A template function that attempts to insert a range of elements.
428  * @param first Iterator pointing to the start of the range to be
429  * inserted.
430  * @param last Iterator pointing to the end of the range.
431  *
432  * Complexity similar to that of the range constructor.
433  */
434  template<typename _InputIterator>
435  void
436  insert(_InputIterator __first, _InputIterator __last)
437  { _M_t._M_insert_equal(__first, __last); }
438 
439 #ifdef __GXX_EXPERIMENTAL_CXX0X__
440  /**
441  * @brief Attempts to insert a list of elements into the %multiset.
442  * @param list A std::initializer_list<value_type> of elements
443  * to be inserted.
444  *
445  * Complexity similar to that of the range constructor.
446  */
447  void
449  { this->insert(__l.begin(), __l.end()); }
450 #endif
451 
452  /**
453  * @brief Erases an element from a %multiset.
454  * @param position An iterator pointing to the element to be erased.
455  *
456  * This function erases an element, pointed to by the given iterator,
457  * from a %multiset. Note that this function only erases the element,
458  * and that if the element is itself a pointer, the pointed-to memory is
459  * not touched in any way. Managing the pointer is the user's
460  * responsibility.
461  */
462  void
463  erase(iterator __position)
464  { _M_t.erase(__position); }
465 
466  /**
467  * @brief Erases elements according to the provided key.
468  * @param x Key of element to be erased.
469  * @return The number of elements erased.
470  *
471  * This function erases all elements located by the given key from a
472  * %multiset.
473  * Note that this function only erases the element, and that if
474  * the element is itself a pointer, the pointed-to memory is not touched
475  * in any way. Managing the pointer is the user's responsibility.
476  */
477  size_type
478  erase(const key_type& __x)
479  { return _M_t.erase(__x); }
480 
481  /**
482  * @brief Erases a [first,last) range of elements from a %multiset.
483  * @param first Iterator pointing to the start of the range to be
484  * erased.
485  * @param last Iterator pointing to the end of the range to be erased.
486  *
487  * This function erases a sequence of elements from a %multiset.
488  * Note that this function only erases the elements, and that if
489  * the elements themselves are pointers, the pointed-to memory is not
490  * touched in any way. Managing the pointer is the user's responsibility.
491  */
492  void
493  erase(iterator __first, iterator __last)
494  { _M_t.erase(__first, __last); }
495 
496  /**
497  * Erases all elements in a %multiset. Note that this function only
498  * erases the elements, and that if the elements themselves are pointers,
499  * the pointed-to memory is not touched in any way. Managing the pointer
500  * is the user's responsibility.
501  */
502  void
503  clear()
504  { _M_t.clear(); }
505 
506  // multiset operations:
507 
508  /**
509  * @brief Finds the number of elements with given key.
510  * @param x Key of elements to be located.
511  * @return Number of elements with specified key.
512  */
513  size_type
514  count(const key_type& __x) const
515  { return _M_t.count(__x); }
516 
517  // _GLIBCXX_RESOLVE_LIB_DEFECTS
518  // 214. set::find() missing const overload
519  //@{
520  /**
521  * @brief Tries to locate an element in a %set.
522  * @param x Element to be located.
523  * @return Iterator pointing to sought-after element, or end() if not
524  * found.
525  *
526  * This function takes a key and tries to locate the element with which
527  * the key matches. If successful the function returns an iterator
528  * pointing to the sought after element. If unsuccessful it returns the
529  * past-the-end ( @c end() ) iterator.
530  */
531  iterator
532  find(const key_type& __x)
533  { return _M_t.find(__x); }
534 
535  const_iterator
536  find(const key_type& __x) const
537  { return _M_t.find(__x); }
538  //@}
539 
540  //@{
541  /**
542  * @brief Finds the beginning of a subsequence matching given key.
543  * @param x Key to be located.
544  * @return Iterator pointing to first element equal to or greater
545  * than key, or end().
546  *
547  * This function returns the first element of a subsequence of elements
548  * that matches the given key. If unsuccessful it returns an iterator
549  * pointing to the first element that has a greater value than given key
550  * or end() if no such element exists.
551  */
552  iterator
553  lower_bound(const key_type& __x)
554  { return _M_t.lower_bound(__x); }
555 
556  const_iterator
557  lower_bound(const key_type& __x) const
558  { return _M_t.lower_bound(__x); }
559  //@}
560 
561  //@{
562  /**
563  * @brief Finds the end of a subsequence matching given key.
564  * @param x Key to be located.
565  * @return Iterator pointing to the first element
566  * greater than key, or end().
567  */
568  iterator
569  upper_bound(const key_type& __x)
570  { return _M_t.upper_bound(__x); }
571 
572  const_iterator
573  upper_bound(const key_type& __x) const
574  { return _M_t.upper_bound(__x); }
575  //@}
576 
577  //@{
578  /**
579  * @brief Finds a subsequence matching given key.
580  * @param x Key to be located.
581  * @return Pair of iterators that possibly points to the subsequence
582  * matching given key.
583  *
584  * This function is equivalent to
585  * @code
586  * std::make_pair(c.lower_bound(val),
587  * c.upper_bound(val))
588  * @endcode
589  * (but is faster than making the calls separately).
590  *
591  * This function probably only makes sense for multisets.
592  */
594  equal_range(const key_type& __x)
595  { return _M_t.equal_range(__x); }
596 
598  equal_range(const key_type& __x) const
599  { return _M_t.equal_range(__x); }
600 
601  template<typename _K1, typename _C1, typename _A1>
602  friend bool
603  operator==(const multiset<_K1, _C1, _A1>&,
604  const multiset<_K1, _C1, _A1>&);
605 
606  template<typename _K1, typename _C1, typename _A1>
607  friend bool
608  operator< (const multiset<_K1, _C1, _A1>&,
609  const multiset<_K1, _C1, _A1>&);
610  };
611 
612  /**
613  * @brief Multiset equality comparison.
614  * @param x A %multiset.
615  * @param y A %multiset of the same type as @a x.
616  * @return True iff the size and elements of the multisets are equal.
617  *
618  * This is an equivalence relation. It is linear in the size of the
619  * multisets.
620  * Multisets are considered equivalent if their sizes are equal, and if
621  * corresponding elements compare equal.
622  */
623  template<typename _Key, typename _Compare, typename _Alloc>
624  inline bool
625  operator==(const multiset<_Key, _Compare, _Alloc>& __x,
627  { return __x._M_t == __y._M_t; }
628 
629  /**
630  * @brief Multiset ordering relation.
631  * @param x A %multiset.
632  * @param y A %multiset of the same type as @a x.
633  * @return True iff @a x is lexicographically less than @a y.
634  *
635  * This is a total ordering relation. It is linear in the size of the
636  * maps. The elements must be comparable with @c <.
637  *
638  * See std::lexicographical_compare() for how the determination is made.
639  */
640  template<typename _Key, typename _Compare, typename _Alloc>
641  inline bool
642  operator<(const multiset<_Key, _Compare, _Alloc>& __x,
644  { return __x._M_t < __y._M_t; }
645 
646  /// Returns !(x == y).
647  template<typename _Key, typename _Compare, typename _Alloc>
648  inline bool
649  operator!=(const multiset<_Key, _Compare, _Alloc>& __x,
651  { return !(__x == __y); }
652 
653  /// Returns y < x.
654  template<typename _Key, typename _Compare, typename _Alloc>
655  inline bool
656  operator>(const multiset<_Key,_Compare,_Alloc>& __x,
658  { return __y < __x; }
659 
660  /// Returns !(y < x)
661  template<typename _Key, typename _Compare, typename _Alloc>
662  inline bool
663  operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
665  { return !(__y < __x); }
666 
667  /// Returns !(x < y)
668  template<typename _Key, typename _Compare, typename _Alloc>
669  inline bool
670  operator>=(const multiset<_Key, _Compare, _Alloc>& __x,
672  { return !(__x < __y); }
673 
674  /// See std::multiset::swap().
675  template<typename _Key, typename _Compare, typename _Alloc>
676  inline void
679  { __x.swap(__y); }
680 
681 #ifdef __GXX_EXPERIMENTAL_CXX0X__
682  template<typename _Key, typename _Compare, typename _Alloc>
683  inline void
684  swap(multiset<_Key, _Compare, _Alloc>&& __x,
685  multiset<_Key, _Compare, _Alloc>& __y)
686  { __x.swap(__y); }
687 
688  template<typename _Key, typename _Compare, typename _Alloc>
689  inline void
690  swap(multiset<_Key, _Compare, _Alloc>& __x,
691  multiset<_Key, _Compare, _Alloc>&& __y)
692  { __x.swap(__y); }
693 #endif
694 
695 _GLIBCXX_END_NESTED_NAMESPACE
696 
697 #endif /* _STL_MULTISET_H */