libstdc++
debug/multimap.h
Go to the documentation of this file.
1 // Debugging multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2014 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file debug/multimap.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30 #define _GLIBCXX_DEBUG_MULTIMAP_H 1
31 
32 #include <debug/safe_sequence.h>
33 #include <debug/safe_iterator.h>
34 #include <utility>
35 
36 namespace std _GLIBCXX_VISIBILITY(default)
37 {
38 namespace __debug
39 {
40  /// Class std::multimap with safety/checking/debug instrumentation.
41  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
42  typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
43  class multimap
44  : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>,
45  public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
46  _Compare, _Allocator> >
47  {
48  typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
49 
50  typedef typename _Base::const_iterator _Base_const_iterator;
51  typedef typename _Base::iterator _Base_iterator;
52  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53 
54 #if __cplusplus >= 201103L
55  typedef __gnu_cxx::__alloc_traits<typename
56  _Base::allocator_type> _Alloc_traits;
57 #endif
58  public:
59  // types:
60  typedef _Key key_type;
61  typedef _Tp mapped_type;
62  typedef std::pair<const _Key, _Tp> value_type;
63  typedef _Compare key_compare;
64  typedef _Allocator allocator_type;
65  typedef typename _Base::reference reference;
66  typedef typename _Base::const_reference const_reference;
67 
68  typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
69  iterator;
70  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
71  multimap> const_iterator;
72 
73  typedef typename _Base::size_type size_type;
74  typedef typename _Base::difference_type difference_type;
75  typedef typename _Base::pointer pointer;
76  typedef typename _Base::const_pointer const_pointer;
77  typedef std::reverse_iterator<iterator> reverse_iterator;
78  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
79 
80  // 23.3.1.1 construct/copy/destroy:
81 
82  multimap() : _Base() { }
83 
84  explicit multimap(const _Compare& __comp,
85  const _Allocator& __a = _Allocator())
86  : _Base(__comp, __a) { }
87 
88  template<typename _InputIterator>
89  multimap(_InputIterator __first, _InputIterator __last,
90  const _Compare& __comp = _Compare(),
91  const _Allocator& __a = _Allocator())
92  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
93  __last)),
94  __gnu_debug::__base(__last),
95  __comp, __a) { }
96 
97  multimap(const multimap& __x)
98  : _Base(__x) { }
99 
100  multimap(const _Base& __x)
101  : _Base(__x) { }
102 
103 #if __cplusplus >= 201103L
104  multimap(multimap&& __x)
105  noexcept(is_nothrow_copy_constructible<_Compare>::value)
106  : _Base(std::move(__x))
107  { this->_M_swap(__x); }
108 
109  multimap(initializer_list<value_type> __l,
110  const _Compare& __c = _Compare(),
111  const allocator_type& __a = allocator_type())
112  : _Base(__l, __c, __a) { }
113 
114  explicit
115  multimap(const allocator_type& __a)
116  : _Base(__a) { }
117 
118  multimap(const multimap& __m, const allocator_type& __a)
119  : _Base(__m, __a) { }
120 
121  multimap(multimap&& __m, const allocator_type& __a)
122  : _Base(std::move(__m._M_base()), __a) { }
123 
124  multimap(initializer_list<value_type> __l, const allocator_type& __a)
125  : _Base(__l, __a)
126  { }
127 
128  template<typename _InputIterator>
129  multimap(_InputIterator __first, _InputIterator __last,
130  const allocator_type& __a)
131  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
132  __last)),
133  __gnu_debug::__base(__last), __a)
134  { }
135 #endif
136 
137  ~multimap() _GLIBCXX_NOEXCEPT { }
138 
139  multimap&
140  operator=(const multimap& __x)
141  {
142  _M_base() = __x;
143  this->_M_invalidate_all();
144  return *this;
145  }
146 
147 #if __cplusplus >= 201103L
148  multimap&
149  operator=(multimap&& __x)
150  noexcept(_Alloc_traits::_S_nothrow_move())
151  {
152  __glibcxx_check_self_move_assign(__x);
153  bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
154  || __x.get_allocator() == this->get_allocator();
155  _M_base() = std::move(__x._M_base());
156  if (__xfer_memory)
157  this->_M_swap(__x);
158  else
159  this->_M_invalidate_all();
160  __x._M_invalidate_all();
161  return *this;
162  }
163 
164  multimap&
165  operator=(initializer_list<value_type> __l)
166  {
167  _M_base() = __l;
168  this->_M_invalidate_all();
169  return *this;
170  }
171 #endif
172 
173  using _Base::get_allocator;
174 
175  // iterators:
176  iterator
177  begin() _GLIBCXX_NOEXCEPT
178  { return iterator(_Base::begin(), this); }
179 
180  const_iterator
181  begin() const _GLIBCXX_NOEXCEPT
182  { return const_iterator(_Base::begin(), this); }
183 
184  iterator
185  end() _GLIBCXX_NOEXCEPT
186  { return iterator(_Base::end(), this); }
187 
188  const_iterator
189  end() const _GLIBCXX_NOEXCEPT
190  { return const_iterator(_Base::end(), this); }
191 
192  reverse_iterator
193  rbegin() _GLIBCXX_NOEXCEPT
194  { return reverse_iterator(end()); }
195 
196  const_reverse_iterator
197  rbegin() const _GLIBCXX_NOEXCEPT
198  { return const_reverse_iterator(end()); }
199 
200  reverse_iterator
201  rend() _GLIBCXX_NOEXCEPT
202  { return reverse_iterator(begin()); }
203 
204  const_reverse_iterator
205  rend() const _GLIBCXX_NOEXCEPT
206  { return const_reverse_iterator(begin()); }
207 
208 #if __cplusplus >= 201103L
209  const_iterator
210  cbegin() const noexcept
211  { return const_iterator(_Base::begin(), this); }
212 
213  const_iterator
214  cend() const noexcept
215  { return const_iterator(_Base::end(), this); }
216 
217  const_reverse_iterator
218  crbegin() const noexcept
219  { return const_reverse_iterator(end()); }
220 
221  const_reverse_iterator
222  crend() const noexcept
223  { return const_reverse_iterator(begin()); }
224 #endif
225 
226  // capacity:
227  using _Base::empty;
228  using _Base::size;
229  using _Base::max_size;
230 
231  // modifiers:
232 #if __cplusplus >= 201103L
233  template<typename... _Args>
234  iterator
235  emplace(_Args&&... __args)
236  {
237  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
238  }
239 
240  template<typename... _Args>
241  iterator
242  emplace_hint(const_iterator __pos, _Args&&... __args)
243  {
244  __glibcxx_check_insert(__pos);
245  return iterator(_Base::emplace_hint(__pos.base(),
246  std::forward<_Args>(__args)...),
247  this);
248  }
249 #endif
250 
251  iterator
252  insert(const value_type& __x)
253  { return iterator(_Base::insert(__x), this); }
254 
255 #if __cplusplus >= 201103L
256  template<typename _Pair, typename = typename
257  std::enable_if<std::is_constructible<value_type,
258  _Pair&&>::value>::type>
259  iterator
260  insert(_Pair&& __x)
261  { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
262 #endif
263 
264 #if __cplusplus >= 201103L
265  void
266  insert(std::initializer_list<value_type> __list)
267  { _Base::insert(__list); }
268 #endif
269 
270  iterator
271 #if __cplusplus >= 201103L
272  insert(const_iterator __position, const value_type& __x)
273 #else
274  insert(iterator __position, const value_type& __x)
275 #endif
276  {
277  __glibcxx_check_insert(__position);
278  return iterator(_Base::insert(__position.base(), __x), this);
279  }
280 
281 #if __cplusplus >= 201103L
282  template<typename _Pair, typename = typename
283  std::enable_if<std::is_constructible<value_type,
284  _Pair&&>::value>::type>
285  iterator
286  insert(const_iterator __position, _Pair&& __x)
287  {
288  __glibcxx_check_insert(__position);
289  return iterator(_Base::insert(__position.base(),
290  std::forward<_Pair>(__x)), this);
291  }
292 #endif
293 
294  template<typename _InputIterator>
295  void
296  insert(_InputIterator __first, _InputIterator __last)
297  {
298  __glibcxx_check_valid_range(__first, __last);
299  _Base::insert(__gnu_debug::__base(__first),
300  __gnu_debug::__base(__last));
301  }
302 
303 #if __cplusplus >= 201103L
304  iterator
305  erase(const_iterator __position)
306  {
307  __glibcxx_check_erase(__position);
308  this->_M_invalidate_if(_Equal(__position.base()));
309  return iterator(_Base::erase(__position.base()), this);
310  }
311 
312  iterator
313  erase(iterator __position)
314  { return erase(const_iterator(__position)); }
315 #else
316  void
317  erase(iterator __position)
318  {
319  __glibcxx_check_erase(__position);
320  this->_M_invalidate_if(_Equal(__position.base()));
321  _Base::erase(__position.base());
322  }
323 #endif
324 
325  size_type
326  erase(const key_type& __x)
327  {
328  std::pair<_Base_iterator, _Base_iterator> __victims =
329  _Base::equal_range(__x);
330  size_type __count = 0;
331  _Base_iterator __victim = __victims.first;
332  while (__victim != __victims.second)
333  {
334  this->_M_invalidate_if(_Equal(__victim));
335  _Base::erase(__victim++);
336  ++__count;
337  }
338  return __count;
339  }
340 
341 #if __cplusplus >= 201103L
342  iterator
343  erase(const_iterator __first, const_iterator __last)
344  {
345  // _GLIBCXX_RESOLVE_LIB_DEFECTS
346  // 151. can't currently clear() empty container
347  __glibcxx_check_erase_range(__first, __last);
348  for (_Base_const_iterator __victim = __first.base();
349  __victim != __last.base(); ++__victim)
350  {
351  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
352  _M_message(__gnu_debug::__msg_valid_range)
353  ._M_iterator(__first, "first")
354  ._M_iterator(__last, "last"));
355  this->_M_invalidate_if(_Equal(__victim));
356  }
357  return iterator(_Base::erase(__first.base(), __last.base()), this);
358  }
359 #else
360  void
361  erase(iterator __first, iterator __last)
362  {
363  // _GLIBCXX_RESOLVE_LIB_DEFECTS
364  // 151. can't currently clear() empty container
365  __glibcxx_check_erase_range(__first, __last);
366  for (_Base_iterator __victim = __first.base();
367  __victim != __last.base(); ++__victim)
368  {
369  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
370  _M_message(__gnu_debug::__msg_valid_range)
371  ._M_iterator(__first, "first")
372  ._M_iterator(__last, "last"));
373  this->_M_invalidate_if(_Equal(__victim));
374  }
375  _Base::erase(__first.base(), __last.base());
376  }
377 #endif
378 
379  void
380  swap(multimap& __x)
381 #if __cplusplus >= 201103L
382  noexcept(_Alloc_traits::_S_nothrow_swap())
383 #endif
384  {
385 #if __cplusplus >= 201103L
386  if (!_Alloc_traits::_S_propagate_on_swap())
387  __glibcxx_check_equal_allocs(__x);
388 #endif
389  _Base::swap(__x);
390  this->_M_swap(__x);
391  }
392 
393  void
394  clear() _GLIBCXX_NOEXCEPT
395  {
396  this->_M_invalidate_all();
397  _Base::clear();
398  }
399 
400  // observers:
401  using _Base::key_comp;
402  using _Base::value_comp;
403 
404  // 23.3.1.3 multimap operations:
405  iterator
406  find(const key_type& __x)
407  { return iterator(_Base::find(__x), this); }
408 
409  const_iterator
410  find(const key_type& __x) const
411  { return const_iterator(_Base::find(__x), this); }
412 
413  using _Base::count;
414 
415  iterator
416  lower_bound(const key_type& __x)
417  { return iterator(_Base::lower_bound(__x), this); }
418 
419  const_iterator
420  lower_bound(const key_type& __x) const
421  { return const_iterator(_Base::lower_bound(__x), this); }
422 
423  iterator
424  upper_bound(const key_type& __x)
425  { return iterator(_Base::upper_bound(__x), this); }
426 
427  const_iterator
428  upper_bound(const key_type& __x) const
429  { return const_iterator(_Base::upper_bound(__x), this); }
430 
431  std::pair<iterator,iterator>
432  equal_range(const key_type& __x)
433  {
434  std::pair<_Base_iterator, _Base_iterator> __res =
435  _Base::equal_range(__x);
436  return std::make_pair(iterator(__res.first, this),
437  iterator(__res.second, this));
438  }
439 
440  std::pair<const_iterator,const_iterator>
441  equal_range(const key_type& __x) const
442  {
443  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
444  _Base::equal_range(__x);
445  return std::make_pair(const_iterator(__res.first, this),
446  const_iterator(__res.second, this));
447  }
448 
449  _Base&
450  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
451 
452  const _Base&
453  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
454 
455  private:
456  void
457  _M_invalidate_all()
458  {
459  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
460  this->_M_invalidate_if(_Not_equal(_Base::end()));
461  }
462  };
463 
464  template<typename _Key, typename _Tp,
465  typename _Compare, typename _Allocator>
466  inline bool
467  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
468  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
469  { return __lhs._M_base() == __rhs._M_base(); }
470 
471  template<typename _Key, typename _Tp,
472  typename _Compare, typename _Allocator>
473  inline bool
474  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
475  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
476  { return __lhs._M_base() != __rhs._M_base(); }
477 
478  template<typename _Key, typename _Tp,
479  typename _Compare, typename _Allocator>
480  inline bool
481  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
482  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
483  { return __lhs._M_base() < __rhs._M_base(); }
484 
485  template<typename _Key, typename _Tp,
486  typename _Compare, typename _Allocator>
487  inline bool
488  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
489  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
490  { return __lhs._M_base() <= __rhs._M_base(); }
491 
492  template<typename _Key, typename _Tp,
493  typename _Compare, typename _Allocator>
494  inline bool
495  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
496  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
497  { return __lhs._M_base() >= __rhs._M_base(); }
498 
499  template<typename _Key, typename _Tp,
500  typename _Compare, typename _Allocator>
501  inline bool
502  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
503  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
504  { return __lhs._M_base() > __rhs._M_base(); }
505 
506  template<typename _Key, typename _Tp,
507  typename _Compare, typename _Allocator>
508  inline void
509  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
510  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
511  { __lhs.swap(__rhs); }
512 
513 } // namespace __debug
514 } // namespace std
515 
516 #endif
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276
__gnu_cxx::__alloc_traits
Uniform interface to C++98 and C++0x allocators.
Definition: ext/alloc_traits.h:95
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:73
__gnu_debug::_Safe_sequence
Base class for constructing a safe sequence type that tracks iterators that reference it...
Definition: formatter.h:52
__gnu_debug::__base
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
__gnu_debug::_Safe_sequence_base::_M_swap
void _M_swap(_Safe_sequence_base &__x)
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
std
ISO C++ entities toplevel namespace is std.
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:139
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:46
std::operator>=
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
Definition: basic_string.h:2699
std::multimap
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_multimap.h:95
std::operator>
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
Definition: basic_string.h:2625
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
__gnu_debug::_Safe_iterator::base
_Iterator base() const noexcept
Return the underlying iterator.
Definition: safe_iterator.h:392
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:167
std::__debug::multimap
Class std::multimap with safety/checking/debug instrumentation.
Definition: debug/multimap.h:43