]>
Commit | Line | Data |
---|---|---|
285b36d6 BK |
1 | // Debugging map implementation -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009 |
285b36d6 BK |
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 | |
748086b7 | 9 | // Free Software Foundation; either version 3, or (at your option) |
285b36d6 BK |
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 | ||
748086b7 JJ |
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/>. | |
285b36d6 | 25 | |
78a53887 BK |
26 | /** @file debug/map.h |
27 | * This file is a GNU debug extension to the Standard C++ Library. | |
28 | */ | |
29 | ||
285b36d6 BK |
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 | ||
3cbc7af0 BK |
37 | namespace std |
38 | { | |
45f388bb | 39 | namespace __debug |
285b36d6 BK |
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 | |
c2ba9709 | 44 | : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator>, |
285b36d6 BK |
45 | public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > |
46 | { | |
c2ba9709 | 47 | typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base; |
285b36d6 BK |
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; | |
09952acc PC |
57 | typedef typename _Base::reference reference; |
58 | typedef typename _Base::const_reference const_reference; | |
526da49c BI |
59 | |
60 | typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> | |
285b36d6 BK |
61 | iterator; |
62 | typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> | |
63 | const_iterator; | |
64 | ||
65 | typedef typename _Base::size_type size_type; | |
66 | typedef typename _Base::difference_type difference_type; | |
09952acc PC |
67 | typedef typename _Base::pointer pointer; |
68 | typedef typename _Base::const_pointer const_pointer; | |
285b36d6 BK |
69 | typedef std::reverse_iterator<iterator> reverse_iterator; |
70 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
526da49c | 71 | |
285b36d6 | 72 | using _Base::value_compare; |
526da49c | 73 | |
285b36d6 | 74 | // 23.3.1.1 construct/copy/destroy: |
526da49c | 75 | explicit map(const _Compare& __comp = _Compare(), |
285b36d6 BK |
76 | const _Allocator& __a = _Allocator()) |
77 | : _Base(__comp, __a) { } | |
78 | ||
79 | template<typename _InputIterator> | |
80 | map(_InputIterator __first, _InputIterator __last, | |
526da49c | 81 | const _Compare& __comp = _Compare(), |
285b36d6 BK |
82 | const _Allocator& __a = _Allocator()) |
83 | : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, | |
84 | __comp, __a), _Safe_base() { } | |
85 | ||
ed540c0a | 86 | map(const map& __x) |
526da49c BI |
87 | : _Base(__x), _Safe_base() { } |
88 | ||
ed540c0a CJ |
89 | map(const _Base& __x) |
90 | : _Base(__x), _Safe_base() { } | |
91 | ||
92 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
93 | map(map&& __x) | |
cc8c030d | 94 | : _Base(std::forward<map>(__x)), _Safe_base() |
ed540c0a | 95 | { this->_M_swap(__x); } |
988499f4 JM |
96 | |
97 | map(initializer_list<value_type> __l, | |
98 | const _Compare& __c = _Compare(), | |
99 | const allocator_type& __a = allocator_type()) | |
b798df05 | 100 | : _Base(__l, __c, __a), _Safe_base() { } |
ed540c0a | 101 | #endif |
285b36d6 BK |
102 | |
103 | ~map() { } | |
526da49c | 104 | |
ed540c0a CJ |
105 | map& |
106 | operator=(const map& __x) | |
285b36d6 BK |
107 | { |
108 | *static_cast<_Base*>(this) = __x; | |
109 | this->_M_invalidate_all(); | |
110 | return *this; | |
111 | } | |
526da49c | 112 | |
ed540c0a CJ |
113 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
114 | map& | |
115 | operator=(map&& __x) | |
116 | { | |
cbc6c888 PC |
117 | // NB: DR 675. |
118 | clear(); | |
ed540c0a CJ |
119 | swap(__x); |
120 | return *this; | |
121 | } | |
988499f4 JM |
122 | |
123 | map& | |
124 | operator=(initializer_list<value_type> __l) | |
125 | { | |
126 | this->clear(); | |
127 | this->insert(__l); | |
128 | return *this; | |
129 | } | |
ed540c0a CJ |
130 | #endif |
131 | ||
285b36d6 BK |
132 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
133 | // 133. map missing get_allocator() | |
134 | using _Base::get_allocator; | |
526da49c | 135 | |
285b36d6 | 136 | // iterators: |
526da49c BI |
137 | iterator |
138 | begin() | |
285b36d6 | 139 | { return iterator(_Base::begin(), this); } |
526da49c BI |
140 | |
141 | const_iterator | |
142 | begin() const | |
285b36d6 | 143 | { return const_iterator(_Base::begin(), this); } |
526da49c BI |
144 | |
145 | iterator | |
146 | end() | |
285b36d6 | 147 | { return iterator(_Base::end(), this); } |
526da49c BI |
148 | |
149 | const_iterator | |
150 | end() const | |
285b36d6 | 151 | { return const_iterator(_Base::end(), this); } |
526da49c BI |
152 | |
153 | reverse_iterator | |
154 | rbegin() | |
285b36d6 | 155 | { return reverse_iterator(end()); } |
526da49c BI |
156 | |
157 | const_reverse_iterator | |
285b36d6 BK |
158 | rbegin() const |
159 | { return const_reverse_iterator(end()); } | |
526da49c BI |
160 | |
161 | reverse_iterator | |
162 | rend() | |
285b36d6 | 163 | { return reverse_iterator(begin()); } |
526da49c BI |
164 | |
165 | const_reverse_iterator | |
166 | rend() const | |
285b36d6 | 167 | { return const_reverse_iterator(begin()); } |
526da49c | 168 | |
0cd50f89 PC |
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 | ||
285b36d6 BK |
187 | // capacity: |
188 | using _Base::empty; | |
189 | using _Base::size; | |
190 | using _Base::max_size; | |
526da49c | 191 | |
285b36d6 BK |
192 | // 23.3.1.2 element access: |
193 | using _Base::operator[]; | |
526da49c | 194 | |
8b5f07a2 PC |
195 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
196 | // DR 464. Suggestion for new member functions in standard containers. | |
197 | using _Base::at; | |
198 | ||
285b36d6 | 199 | // modifiers: |
526da49c | 200 | std::pair<iterator, bool> |
285b36d6 BK |
201 | insert(const value_type& __x) |
202 | { | |
203 | typedef typename _Base::iterator _Base_iterator; | |
204 | std::pair<_Base_iterator, bool> __res = _Base::insert(__x); | |
526da49c | 205 | return std::pair<iterator, bool>(iterator(__res.first, this), |
285b36d6 BK |
206 | __res.second); |
207 | } | |
526da49c | 208 | |
988499f4 JM |
209 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
210 | void | |
211 | insert(std::initializer_list<value_type> __list) | |
212 | { _Base::insert(__list); } | |
213 | #endif | |
214 | ||
526da49c | 215 | iterator |
285b36d6 BK |
216 | insert(iterator __position, const value_type& __x) |
217 | { | |
218 | __glibcxx_check_insert(__position); | |
219 | return iterator(_Base::insert(__position.base(), __x), this); | |
220 | } | |
526da49c | 221 | |
285b36d6 | 222 | template<typename _InputIterator> |
526da49c | 223 | void |
285b36d6 BK |
224 | insert(_InputIterator __first, _InputIterator __last) |
225 | { | |
58753063 | 226 | __glibcxx_check_valid_range(__first, __last); |
285b36d6 BK |
227 | _Base::insert(__first, __last); |
228 | } | |
526da49c BI |
229 | |
230 | void | |
285b36d6 BK |
231 | erase(iterator __position) |
232 | { | |
233 | __glibcxx_check_erase(__position); | |
234 | __position._M_invalidate(); | |
235 | _Base::erase(__position.base()); | |
236 | } | |
526da49c BI |
237 | |
238 | size_type | |
285b36d6 BK |
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 | } | |
526da49c BI |
251 | |
252 | void | |
285b36d6 BK |
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 | } | |
526da49c BI |
261 | |
262 | void | |
ed540c0a | 263 | swap(map& __x) |
285b36d6 BK |
264 | { |
265 | _Base::swap(__x); | |
266 | this->_M_swap(__x); | |
267 | } | |
526da49c BI |
268 | |
269 | void | |
285b36d6 BK |
270 | clear() |
271 | { this->erase(begin(), end()); } | |
526da49c | 272 | |
285b36d6 BK |
273 | // observers: |
274 | using _Base::key_comp; | |
275 | using _Base::value_comp; | |
526da49c | 276 | |
285b36d6 | 277 | // 23.3.1.3 map operations: |
526da49c | 278 | iterator |
285b36d6 BK |
279 | find(const key_type& __x) |
280 | { return iterator(_Base::find(__x), this); } | |
526da49c BI |
281 | |
282 | const_iterator | |
285b36d6 BK |
283 | find(const key_type& __x) const |
284 | { return const_iterator(_Base::find(__x), this); } | |
526da49c | 285 | |
285b36d6 | 286 | using _Base::count; |
526da49c BI |
287 | |
288 | iterator | |
285b36d6 BK |
289 | lower_bound(const key_type& __x) |
290 | { return iterator(_Base::lower_bound(__x), this); } | |
526da49c BI |
291 | |
292 | const_iterator | |
285b36d6 BK |
293 | lower_bound(const key_type& __x) const |
294 | { return const_iterator(_Base::lower_bound(__x), this); } | |
526da49c BI |
295 | |
296 | iterator | |
285b36d6 BK |
297 | upper_bound(const key_type& __x) |
298 | { return iterator(_Base::upper_bound(__x), this); } | |
526da49c BI |
299 | |
300 | const_iterator | |
285b36d6 BK |
301 | upper_bound(const key_type& __x) const |
302 | { return const_iterator(_Base::upper_bound(__x), this); } | |
526da49c | 303 | |
285b36d6 BK |
304 | std::pair<iterator,iterator> |
305 | equal_range(const key_type& __x) | |
306 | { | |
307 | typedef typename _Base::iterator _Base_iterator; | |
308 | std::pair<_Base_iterator, _Base_iterator> __res = | |
309 | _Base::equal_range(__x); | |
310 | return std::make_pair(iterator(__res.first, this), | |
311 | iterator(__res.second, this)); | |
312 | } | |
526da49c | 313 | |
285b36d6 BK |
314 | std::pair<const_iterator,const_iterator> |
315 | equal_range(const key_type& __x) const | |
316 | { | |
317 | typedef typename _Base::const_iterator _Base_const_iterator; | |
318 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = | |
319 | _Base::equal_range(__x); | |
320 | return std::make_pair(const_iterator(__res.first, this), | |
321 | const_iterator(__res.second, this)); | |
322 | } | |
526da49c BI |
323 | |
324 | _Base& | |
285b36d6 BK |
325 | _M_base() { return *this; } |
326 | ||
526da49c | 327 | const _Base& |
285b36d6 | 328 | _M_base() const { return *this; } |
526da49c | 329 | |
285b36d6 | 330 | private: |
526da49c | 331 | void |
285b36d6 BK |
332 | _M_invalidate_all() |
333 | { | |
334 | typedef typename _Base::const_iterator _Base_const_iterator; | |
335 | typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; | |
336 | this->_M_invalidate_if(_Not_equal(_M_base().end())); | |
337 | } | |
338 | }; | |
339 | ||
ed540c0a CJ |
340 | template<typename _Key, typename _Tp, |
341 | typename _Compare, typename _Allocator> | |
285b36d6 | 342 | inline bool |
ed540c0a CJ |
343 | operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
344 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
345 | { return __lhs._M_base() == __rhs._M_base(); } |
346 | ||
ed540c0a CJ |
347 | template<typename _Key, typename _Tp, |
348 | typename _Compare, typename _Allocator> | |
285b36d6 | 349 | inline bool |
ed540c0a CJ |
350 | operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
351 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
352 | { return __lhs._M_base() != __rhs._M_base(); } |
353 | ||
ed540c0a CJ |
354 | template<typename _Key, typename _Tp, |
355 | typename _Compare, typename _Allocator> | |
285b36d6 | 356 | inline bool |
ed540c0a CJ |
357 | operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
358 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
359 | { return __lhs._M_base() < __rhs._M_base(); } |
360 | ||
ed540c0a CJ |
361 | template<typename _Key, typename _Tp, |
362 | typename _Compare, typename _Allocator> | |
285b36d6 | 363 | inline bool |
ed540c0a CJ |
364 | operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
365 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
366 | { return __lhs._M_base() <= __rhs._M_base(); } |
367 | ||
ed540c0a CJ |
368 | template<typename _Key, typename _Tp, |
369 | typename _Compare, typename _Allocator> | |
285b36d6 | 370 | inline bool |
ed540c0a CJ |
371 | operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
372 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
373 | { return __lhs._M_base() >= __rhs._M_base(); } |
374 | ||
ed540c0a CJ |
375 | template<typename _Key, typename _Tp, |
376 | typename _Compare, typename _Allocator> | |
285b36d6 | 377 | inline bool |
ed540c0a CJ |
378 | operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
379 | const map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
380 | { return __lhs._M_base() > __rhs._M_base(); } |
381 | ||
ed540c0a CJ |
382 | template<typename _Key, typename _Tp, |
383 | typename _Compare, typename _Allocator> | |
285b36d6 | 384 | inline void |
ed540c0a CJ |
385 | swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, |
386 | map<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 | 387 | { __lhs.swap(__rhs); } |
ed540c0a | 388 | |
45f388bb | 389 | } // namespace __debug |
3cbc7af0 | 390 | } // namespace std |
285b36d6 | 391 | |
526da49c | 392 | #endif |