libstdc++
multimap.h
Go to the documentation of this file.
1 // Debugging multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 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 /** @file debug/multimap.h
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
31 #define _GLIBCXX_DEBUG_MULTIMAP_H 1
32 
33 #include <debug/safe_sequence.h>
34 #include <debug/safe_iterator.h>
35 #include <utility>
36 
37 namespace std
38 {
39 namespace __debug
40 {
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_D::multimap<_Key, _Tp, _Compare, _Allocator>,
45  public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
46  _Compare, _Allocator> >
47  {
48  typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
49  typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
50 
51  public:
52  // types:
53  typedef _Key key_type;
54  typedef _Tp mapped_type;
55  typedef std::pair<const _Key, _Tp> value_type;
56  typedef _Compare key_compare;
57  typedef _Allocator allocator_type;
58  typedef typename _Base::reference reference;
59  typedef typename _Base::const_reference const_reference;
60 
62  iterator;
63  typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
64  multimap> const_iterator;
65 
66  typedef typename _Base::size_type size_type;
67  typedef typename _Base::difference_type difference_type;
68  typedef typename _Base::pointer pointer;
69  typedef typename _Base::const_pointer const_pointer;
70  typedef std::reverse_iterator<iterator> reverse_iterator;
71  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
72 
73  using _Base::value_compare;
74 
75  // 23.3.1.1 construct/copy/destroy:
76  explicit multimap(const _Compare& __comp = _Compare(),
77  const _Allocator& __a = _Allocator())
78  : _Base(__comp, __a) { }
79 
80  template<typename _InputIterator>
81  multimap(_InputIterator __first, _InputIterator __last,
82  const _Compare& __comp = _Compare(),
83  const _Allocator& __a = _Allocator())
84  : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
85  __comp, __a) { }
86 
87  multimap(const multimap& __x)
88  : _Base(__x), _Safe_base() { }
89 
90  multimap(const _Base& __x)
91  : _Base(__x), _Safe_base() { }
92 
93 #ifdef __GXX_EXPERIMENTAL_CXX0X__
94  multimap(multimap&& __x)
95  : _Base(std::forward<multimap>(__x)), _Safe_base()
96  { this->_M_swap(__x); }
97 
98  multimap(initializer_list<value_type> __l,
99  const _Compare& __c = _Compare(),
100  const allocator_type& __a = allocator_type())
101  : _Base(__l, __c, __a), _Safe_base() { }
102 #endif
103 
104  ~multimap() { }
105 
106  multimap&
107  operator=(const multimap& __x)
108  {
109  *static_cast<_Base*>(this) = __x;
110  this->_M_invalidate_all();
111  return *this;
112  }
113 
114 #ifdef __GXX_EXPERIMENTAL_CXX0X__
115  multimap&
116  operator=(multimap&& __x)
117  {
118  // NB: DR 675.
119  clear();
120  swap(__x);
121  return *this;
122  }
123 
124  multimap&
125  operator=(initializer_list<value_type> __l)
126  {
127  this->clear();
128  this->insert(__l);
129  return *this;
130  }
131 #endif
132 
133  using _Base::get_allocator;
134 
135  // iterators:
136  iterator
137  begin()
138  { return iterator(_Base::begin(), this); }
139 
140  const_iterator
141  begin() const
142  { return const_iterator(_Base::begin(), this); }
143 
144  iterator
145  end()
146  { return iterator(_Base::end(), this); }
147 
148  const_iterator
149  end() const
150  { return const_iterator(_Base::end(), this); }
151 
152  reverse_iterator
153  rbegin()
154  { return reverse_iterator(end()); }
155 
156  const_reverse_iterator
157  rbegin() const
158  { return const_reverse_iterator(end()); }
159 
160  reverse_iterator
161  rend()
162  { return reverse_iterator(begin()); }
163 
164  const_reverse_iterator
165  rend() const
166  { return const_reverse_iterator(begin()); }
167 
168 #ifdef __GXX_EXPERIMENTAL_CXX0X__
169  const_iterator
170  cbegin() const
171  { return const_iterator(_Base::begin(), this); }
172 
173  const_iterator
174  cend() const
175  { return const_iterator(_Base::end(), this); }
176 
177  const_reverse_iterator
178  crbegin() const
179  { return const_reverse_iterator(end()); }
180 
181  const_reverse_iterator
182  crend() const
183  { return const_reverse_iterator(begin()); }
184 #endif
185 
186  // capacity:
187  using _Base::empty;
188  using _Base::size;
189  using _Base::max_size;
190 
191  // modifiers:
192  iterator
193  insert(const value_type& __x)
194  { return iterator(_Base::insert(__x), this); }
195 
196 #ifdef __GXX_EXPERIMENTAL_CXX0X__
197  void
198  insert(std::initializer_list<value_type> __list)
199  { _Base::insert(__list); }
200 #endif
201 
202  iterator
203  insert(iterator __position, const value_type& __x)
204  {
205  __glibcxx_check_insert(__position);
206  return iterator(_Base::insert(__position.base(), __x), this);
207  }
208 
209  template<typename _InputIterator>
210  void
211  insert(_InputIterator __first, _InputIterator __last)
212  {
213  __glibcxx_check_valid_range(__first, __last);
214  _Base::insert(__first, __last);
215  }
216 
217  void
218  erase(iterator __position)
219  {
220  __glibcxx_check_erase(__position);
221  __position._M_invalidate();
222  _Base::erase(__position.base());
223  }
224 
225  size_type
226  erase(const key_type& __x)
227  {
228  std::pair<iterator, iterator> __victims = this->equal_range(__x);
229  size_type __count = 0;
230  while (__victims.first != __victims.second)
231  {
232  iterator __victim = __victims.first++;
233  __victim._M_invalidate();
234  _Base::erase(__victim.base());
235  ++__count;
236  }
237  return __count;
238  }
239 
240  void
241  erase(iterator __first, iterator __last)
242  {
243  // _GLIBCXX_RESOLVE_LIB_DEFECTS
244  // 151. can't currently clear() empty container
245  __glibcxx_check_erase_range(__first, __last);
246  while (__first != __last)
247  this->erase(__first++);
248  }
249 
250  void
251 #ifdef __GXX_EXPERIMENTAL_CXX0X__
252  swap(multimap&& __x)
253 #else
254  swap(multimap& __x)
255 #endif
256  {
257  _Base::swap(__x);
258  this->_M_swap(__x);
259  }
260 
261  void
262  clear()
263  { this->erase(begin(), end()); }
264 
265  // observers:
266  using _Base::key_comp;
267  using _Base::value_comp;
268 
269  // 23.3.1.3 multimap operations:
270  iterator
271  find(const key_type& __x)
272  { return iterator(_Base::find(__x), this); }
273 
274  const_iterator
275  find(const key_type& __x) const
276  { return const_iterator(_Base::find(__x), this); }
277 
278  using _Base::count;
279 
280  iterator
281  lower_bound(const key_type& __x)
282  { return iterator(_Base::lower_bound(__x), this); }
283 
284  const_iterator
285  lower_bound(const key_type& __x) const
286  { return const_iterator(_Base::lower_bound(__x), this); }
287 
288  iterator
289  upper_bound(const key_type& __x)
290  { return iterator(_Base::upper_bound(__x), this); }
291 
292  const_iterator
293  upper_bound(const key_type& __x) const
294  { return const_iterator(_Base::upper_bound(__x), this); }
295 
297  equal_range(const key_type& __x)
298  {
299  typedef typename _Base::iterator _Base_iterator;
301  _Base::equal_range(__x);
302  return std::make_pair(iterator(__res.first, this),
303  iterator(__res.second, this));
304  }
305 
307  equal_range(const key_type& __x) const
308  {
309  typedef typename _Base::const_iterator _Base_const_iterator;
311  _Base::equal_range(__x);
312  return std::make_pair(const_iterator(__res.first, this),
313  const_iterator(__res.second, this));
314  }
315 
316  _Base&
317  _M_base() { return *this; }
318 
319  const _Base&
320  _M_base() const { return *this; }
321 
322  private:
323  void
325  {
326  typedef typename _Base::const_iterator _Base_const_iterator;
328  this->_M_invalidate_if(_Not_equal(_M_base().end()));
329  }
330  };
331 
332  template<typename _Key, typename _Tp,
333  typename _Compare, typename _Allocator>
334  inline bool
335  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
336  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
337  { return __lhs._M_base() == __rhs._M_base(); }
338 
339  template<typename _Key, typename _Tp,
340  typename _Compare, typename _Allocator>
341  inline bool
342  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
343  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
344  { return __lhs._M_base() != __rhs._M_base(); }
345 
346  template<typename _Key, typename _Tp,
347  typename _Compare, typename _Allocator>
348  inline bool
349  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
350  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
351  { return __lhs._M_base() < __rhs._M_base(); }
352 
353  template<typename _Key, typename _Tp,
354  typename _Compare, typename _Allocator>
355  inline bool
356  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
357  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
358  { return __lhs._M_base() <= __rhs._M_base(); }
359 
360  template<typename _Key, typename _Tp,
361  typename _Compare, typename _Allocator>
362  inline bool
363  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
364  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
365  { return __lhs._M_base() >= __rhs._M_base(); }
366 
367  template<typename _Key, typename _Tp,
368  typename _Compare, typename _Allocator>
369  inline bool
370  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
371  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
372  { return __lhs._M_base() > __rhs._M_base(); }
373 
374  template<typename _Key, typename _Tp,
375  typename _Compare, typename _Allocator>
376  inline void
377  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
378  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
379  { __lhs.swap(__rhs); }
380 
381 #ifdef __GXX_EXPERIMENTAL_CXX0X__
382  template<typename _Key, typename _Tp,
383  typename _Compare, typename _Allocator>
384  inline void
385  swap(multimap<_Key, _Tp, _Compare, _Allocator>&& __lhs,
386  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
387  { __lhs.swap(__rhs); }
388 
389  template<typename _Key, typename _Tp,
390  typename _Compare, typename _Allocator>
391  inline void
392  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
393  multimap<_Key, _Tp, _Compare, _Allocator>&& __rhs)
394  { __lhs.swap(__rhs); }
395 #endif
396 
397 } // namespace __debug
398 } // namespace std
399 
400 #endif