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