]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Iterators -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
105c6331 | 4 | // Free Software Foundation, Inc. |
42526146 PE |
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) |
42526146 PE |
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. | |
42526146 | 20 | |
748086b7 JJ |
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/>. | |
42526146 | 25 | |
725dc051 BK |
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-1998 | |
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 | ||
729e3d3f PE |
52 | /** @file stl_iterator.h |
53 | * This is an internal header file, included by other library headers. | |
54 | * You should not attempt to use it directly. | |
8f94053d PE |
55 | * |
56 | * This file implements reverse_iterator, back_insert_iterator, | |
57 | * front_insert_iterator, insert_iterator, __normal_iterator, and their | |
58 | * supporting functions and overloaded operators. | |
725dc051 BK |
59 | */ |
60 | ||
046d30f4 PC |
61 | #ifndef _STL_ITERATOR_H |
62 | #define _STL_ITERATOR_H 1 | |
725dc051 | 63 | |
2bcec729 | 64 | #include <bits/cpp_type_traits.h> |
105c6331 | 65 | #include <ext/type_traits.h> |
ca0f8fd1 | 66 | #include <bits/move.h> |
2bcec729 | 67 | |
3cbc7af0 BK |
68 | _GLIBCXX_BEGIN_NAMESPACE(std) |
69 | ||
c766fc5f | 70 | // 24.4.1 Reverse iterators |
8f94053d PE |
71 | /** |
72 | * "Bidirectional and random access iterators have corresponding reverse | |
73 | * %iterator adaptors that iterate through the data structure in the | |
74 | * opposite direction. They have the same signatures as the corresponding | |
75 | * iterators. The fundamental relation between a reverse %iterator and its | |
76 | * corresponding %iterator @c i is established by the identity: | |
77 | * @code | |
78 | * &*(reverse_iterator(i)) == &*(i - 1) | |
79 | * @endcode | |
80 | * | |
81 | * This mapping is dictated by the fact that while there is always a | |
82 | * pointer past the end of an array, there might not be a valid pointer | |
83 | * before the beginning of an array." [24.4.1]/1,2 | |
84 | * | |
85 | * Reverse iterators can be tricky and surprising at first. Their | |
86 | * semantics make sense, however, and the trickiness is a side effect of | |
87 | * the requirement that the iterators must be safe. | |
88 | */ | |
b581eaf7 | 89 | template<typename _Iterator> |
ed6814f7 | 90 | class reverse_iterator |
f591eb23 BK |
91 | : public iterator<typename iterator_traits<_Iterator>::iterator_category, |
92 | typename iterator_traits<_Iterator>::value_type, | |
93 | typename iterator_traits<_Iterator>::difference_type, | |
94 | typename iterator_traits<_Iterator>::pointer, | |
95 | typename iterator_traits<_Iterator>::reference> | |
c766fc5f BK |
96 | { |
97 | protected: | |
8f7a4015 | 98 | _Iterator current; |
c766fc5f BK |
99 | |
100 | public: | |
ed6814f7 BI |
101 | typedef _Iterator iterator_type; |
102 | typedef typename iterator_traits<_Iterator>::difference_type | |
103 | difference_type; | |
b581eaf7 BK |
104 | typedef typename iterator_traits<_Iterator>::reference reference; |
105 | typedef typename iterator_traits<_Iterator>::pointer pointer; | |
c766fc5f BK |
106 | |
107 | public: | |
8f94053d | 108 | /** |
d56a8811 NM |
109 | * The default constructor default-initializes member @p current. |
110 | * If it is a pointer, that means it is zero-initialized. | |
8f94053d | 111 | */ |
3d7c150e | 112 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
d56a8811 NM |
113 | // 235 No specification of default ctor for reverse_iterator |
114 | reverse_iterator() : current() { } | |
c766fc5f | 115 | |
8f94053d PE |
116 | /** |
117 | * This %iterator will move in the opposite direction that @p x does. | |
118 | */ | |
ed6814f7 | 119 | explicit |
8f7a4015 | 120 | reverse_iterator(iterator_type __x) : current(__x) { } |
c766fc5f | 121 | |
8f94053d PE |
122 | /** |
123 | * The copy constructor is normal. | |
124 | */ | |
ed6814f7 | 125 | reverse_iterator(const reverse_iterator& __x) |
8f7a4015 | 126 | : current(__x.current) { } |
c766fc5f | 127 | |
8f94053d PE |
128 | /** |
129 | * A reverse_iterator across other types can be copied in the normal | |
130 | * fashion. | |
131 | */ | |
b581eaf7 | 132 | template<typename _Iter> |
c766fc5f | 133 | reverse_iterator(const reverse_iterator<_Iter>& __x) |
8f7a4015 | 134 | : current(__x.base()) { } |
ed6814f7 | 135 | |
8f94053d PE |
136 | /** |
137 | * @return @c current, the %iterator used for underlying work. | |
138 | */ | |
ed6814f7 | 139 | iterator_type |
f6592a9e PC |
140 | base() const |
141 | { return current; } | |
c766fc5f | 142 | |
8f94053d PE |
143 | /** |
144 | * @return TODO | |
145 | * | |
146 | * @doctodo | |
147 | */ | |
ed6814f7 BI |
148 | reference |
149 | operator*() const | |
c766fc5f | 150 | { |
8f7a4015 | 151 | _Iterator __tmp = current; |
c766fc5f BK |
152 | return *--__tmp; |
153 | } | |
154 | ||
8f94053d PE |
155 | /** |
156 | * @return TODO | |
157 | * | |
158 | * @doctodo | |
159 | */ | |
ed6814f7 | 160 | pointer |
f6592a9e PC |
161 | operator->() const |
162 | { return &(operator*()); } | |
c766fc5f | 163 | |
8f94053d PE |
164 | /** |
165 | * @return TODO | |
166 | * | |
167 | * @doctodo | |
168 | */ | |
ed6814f7 BI |
169 | reverse_iterator& |
170 | operator++() | |
c766fc5f | 171 | { |
8f7a4015 | 172 | --current; |
c766fc5f BK |
173 | return *this; |
174 | } | |
175 | ||
8f94053d PE |
176 | /** |
177 | * @return TODO | |
178 | * | |
179 | * @doctodo | |
180 | */ | |
ed6814f7 BI |
181 | reverse_iterator |
182 | operator++(int) | |
c766fc5f | 183 | { |
b581eaf7 | 184 | reverse_iterator __tmp = *this; |
8f7a4015 | 185 | --current; |
c766fc5f BK |
186 | return __tmp; |
187 | } | |
188 | ||
8f94053d PE |
189 | /** |
190 | * @return TODO | |
191 | * | |
192 | * @doctodo | |
193 | */ | |
ed6814f7 BI |
194 | reverse_iterator& |
195 | operator--() | |
c766fc5f | 196 | { |
8f7a4015 | 197 | ++current; |
c766fc5f BK |
198 | return *this; |
199 | } | |
200 | ||
8f94053d PE |
201 | /** |
202 | * @return TODO | |
203 | * | |
204 | * @doctodo | |
205 | */ | |
c6ff1944 PC |
206 | reverse_iterator |
207 | operator--(int) | |
c766fc5f | 208 | { |
b581eaf7 | 209 | reverse_iterator __tmp = *this; |
8f7a4015 | 210 | ++current; |
c766fc5f BK |
211 | return __tmp; |
212 | } | |
ed6814f7 | 213 | |
8f94053d PE |
214 | /** |
215 | * @return TODO | |
216 | * | |
217 | * @doctodo | |
218 | */ | |
ed6814f7 BI |
219 | reverse_iterator |
220 | operator+(difference_type __n) const | |
8f7a4015 | 221 | { return reverse_iterator(current - __n); } |
c766fc5f | 222 | |
8f94053d PE |
223 | /** |
224 | * @return TODO | |
225 | * | |
226 | * @doctodo | |
227 | */ | |
ed6814f7 BI |
228 | reverse_iterator& |
229 | operator+=(difference_type __n) | |
c766fc5f | 230 | { |
8f7a4015 | 231 | current -= __n; |
c766fc5f BK |
232 | return *this; |
233 | } | |
234 | ||
8f94053d PE |
235 | /** |
236 | * @return TODO | |
237 | * | |
238 | * @doctodo | |
239 | */ | |
ed6814f7 BI |
240 | reverse_iterator |
241 | operator-(difference_type __n) const | |
8f7a4015 | 242 | { return reverse_iterator(current + __n); } |
c766fc5f | 243 | |
8f94053d PE |
244 | /** |
245 | * @return TODO | |
246 | * | |
247 | * @doctodo | |
248 | */ | |
ed6814f7 BI |
249 | reverse_iterator& |
250 | operator-=(difference_type __n) | |
c766fc5f | 251 | { |
8f7a4015 | 252 | current += __n; |
c766fc5f BK |
253 | return *this; |
254 | } | |
255 | ||
8f94053d PE |
256 | /** |
257 | * @return TODO | |
258 | * | |
259 | * @doctodo | |
260 | */ | |
ed6814f7 | 261 | reference |
f6592a9e | 262 | operator[](difference_type __n) const |
ed6814f7 BI |
263 | { return *(*this + __n); } |
264 | }; | |
265 | ||
8f94053d PE |
266 | //@{ |
267 | /** | |
268 | * @param x A %reverse_iterator. | |
269 | * @param y A %reverse_iterator. | |
270 | * @return A simple bool. | |
271 | * | |
272 | * Reverse iterators forward many operations to their underlying base() | |
273 | * iterators. Others are implemented in terms of one another. | |
274 | * | |
275 | */ | |
b581eaf7 | 276 | template<typename _Iterator> |
ed6814f7 BI |
277 | inline bool |
278 | operator==(const reverse_iterator<_Iterator>& __x, | |
279 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
280 | { return __x.base() == __y.base(); } |
281 | ||
b581eaf7 | 282 | template<typename _Iterator> |
ed6814f7 BI |
283 | inline bool |
284 | operator<(const reverse_iterator<_Iterator>& __x, | |
285 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
286 | { return __y.base() < __x.base(); } |
287 | ||
b581eaf7 | 288 | template<typename _Iterator> |
ed6814f7 BI |
289 | inline bool |
290 | operator!=(const reverse_iterator<_Iterator>& __x, | |
291 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
292 | { return !(__x == __y); } |
293 | ||
b581eaf7 | 294 | template<typename _Iterator> |
ed6814f7 BI |
295 | inline bool |
296 | operator>(const reverse_iterator<_Iterator>& __x, | |
297 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
298 | { return __y < __x; } |
299 | ||
b581eaf7 | 300 | template<typename _Iterator> |
ed6814f7 BI |
301 | inline bool |
302 | operator<=(const reverse_iterator<_Iterator>& __x, | |
c6ff1944 | 303 | const reverse_iterator<_Iterator>& __y) |
c766fc5f BK |
304 | { return !(__y < __x); } |
305 | ||
b581eaf7 | 306 | template<typename _Iterator> |
ed6814f7 BI |
307 | inline bool |
308 | operator>=(const reverse_iterator<_Iterator>& __x, | |
309 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
310 | { return !(__x < __y); } |
311 | ||
b581eaf7 | 312 | template<typename _Iterator> |
c766fc5f | 313 | inline typename reverse_iterator<_Iterator>::difference_type |
ed6814f7 BI |
314 | operator-(const reverse_iterator<_Iterator>& __x, |
315 | const reverse_iterator<_Iterator>& __y) | |
c766fc5f BK |
316 | { return __y.base() - __x.base(); } |
317 | ||
b581eaf7 | 318 | template<typename _Iterator> |
ed6814f7 | 319 | inline reverse_iterator<_Iterator> |
c766fc5f | 320 | operator+(typename reverse_iterator<_Iterator>::difference_type __n, |
ed6814f7 | 321 | const reverse_iterator<_Iterator>& __x) |
c766fc5f | 322 | { return reverse_iterator<_Iterator>(__x.base() - __n); } |
c6ff1944 PC |
323 | |
324 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
325 | // DR 280. Comparison of reverse_iterator to const reverse_iterator. | |
326 | template<typename _IteratorL, typename _IteratorR> | |
327 | inline bool | |
328 | operator==(const reverse_iterator<_IteratorL>& __x, | |
329 | const reverse_iterator<_IteratorR>& __y) | |
330 | { return __x.base() == __y.base(); } | |
331 | ||
332 | template<typename _IteratorL, typename _IteratorR> | |
333 | inline bool | |
334 | operator<(const reverse_iterator<_IteratorL>& __x, | |
335 | const reverse_iterator<_IteratorR>& __y) | |
336 | { return __y.base() < __x.base(); } | |
337 | ||
338 | template<typename _IteratorL, typename _IteratorR> | |
339 | inline bool | |
340 | operator!=(const reverse_iterator<_IteratorL>& __x, | |
341 | const reverse_iterator<_IteratorR>& __y) | |
342 | { return !(__x == __y); } | |
343 | ||
344 | template<typename _IteratorL, typename _IteratorR> | |
345 | inline bool | |
346 | operator>(const reverse_iterator<_IteratorL>& __x, | |
347 | const reverse_iterator<_IteratorR>& __y) | |
348 | { return __y < __x; } | |
349 | ||
350 | template<typename _IteratorL, typename _IteratorR> | |
351 | inline bool | |
352 | operator<=(const reverse_iterator<_IteratorL>& __x, | |
353 | const reverse_iterator<_IteratorR>& __y) | |
354 | { return !(__y < __x); } | |
355 | ||
356 | template<typename _IteratorL, typename _IteratorR> | |
357 | inline bool | |
358 | operator>=(const reverse_iterator<_IteratorL>& __x, | |
359 | const reverse_iterator<_IteratorR>& __y) | |
360 | { return !(__x < __y); } | |
361 | ||
362 | template<typename _IteratorL, typename _IteratorR> | |
5defb0f2 PC |
363 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
364 | // DR 685. | |
365 | inline auto | |
366 | operator-(const reverse_iterator<_IteratorL>& __x, | |
367 | const reverse_iterator<_IteratorR>& __y) | |
368 | -> decltype(__y.base() - __x.base()) | |
369 | #else | |
c6ff1944 PC |
370 | inline typename reverse_iterator<_IteratorL>::difference_type |
371 | operator-(const reverse_iterator<_IteratorL>& __x, | |
372 | const reverse_iterator<_IteratorR>& __y) | |
5defb0f2 | 373 | #endif |
c6ff1944 | 374 | { return __y.base() - __x.base(); } |
8f94053d | 375 | //@} |
c766fc5f BK |
376 | |
377 | // 24.4.2.2.1 back_insert_iterator | |
8f94053d | 378 | /** |
aa2d5ba2 PE |
379 | * @brief Turns assignment into insertion. |
380 | * | |
8f94053d PE |
381 | * These are output iterators, constructed from a container-of-T. |
382 | * Assigning a T to the iterator appends it to the container using | |
383 | * push_back. | |
384 | * | |
385 | * Tip: Using the back_inserter function to create these iterators can | |
386 | * save typing. | |
387 | */ | |
b581eaf7 | 388 | template<typename _Container> |
ed6814f7 | 389 | class back_insert_iterator |
c766fc5f BK |
390 | : public iterator<output_iterator_tag, void, void, void, void> |
391 | { | |
392 | protected: | |
8f7a4015 | 393 | _Container* container; |
c766fc5f BK |
394 | |
395 | public: | |
8f94053d | 396 | /// A nested typedef for the type of whatever container you used. |
c766fc5f | 397 | typedef _Container container_type; |
ed6814f7 | 398 | |
8f94053d | 399 | /// The only way to create this %iterator is with a container. |
ed6814f7 | 400 | explicit |
8f7a4015 | 401 | back_insert_iterator(_Container& __x) : container(&__x) { } |
c766fc5f | 402 | |
8f94053d PE |
403 | /** |
404 | * @param value An instance of whatever type | |
405 | * container_type::const_reference is; presumably a | |
406 | * reference-to-const T for container<T>. | |
407 | * @return This %iterator, for chained operations. | |
408 | * | |
409 | * This kind of %iterator doesn't really have a "position" in the | |
410 | * container (you can think of the position as being permanently at | |
411 | * the end, if you like). Assigning a value to the %iterator will | |
412 | * always append the value to the end of the container. | |
413 | */ | |
d27bba5e | 414 | back_insert_iterator& |
ed6814f7 BI |
415 | operator=(typename _Container::const_reference __value) |
416 | { | |
8f7a4015 | 417 | container->push_back(__value); |
c766fc5f BK |
418 | return *this; |
419 | } | |
420 | ||
45d50699 PC |
421 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
422 | back_insert_iterator& | |
423 | operator=(typename _Container::value_type&& __value) | |
424 | { | |
425 | container->push_back(std::move(__value)); | |
426 | return *this; | |
427 | } | |
428 | #endif | |
429 | ||
8f94053d | 430 | /// Simply returns *this. |
ed6814f7 | 431 | back_insert_iterator& |
f6592a9e PC |
432 | operator*() |
433 | { return *this; } | |
c766fc5f | 434 | |
8f94053d | 435 | /// Simply returns *this. (This %iterator does not "move".) |
ed6814f7 | 436 | back_insert_iterator& |
f6592a9e PC |
437 | operator++() |
438 | { return *this; } | |
c766fc5f | 439 | |
8f94053d | 440 | /// Simply returns *this. (This %iterator does not "move".) |
d27bba5e | 441 | back_insert_iterator |
f6592a9e PC |
442 | operator++(int) |
443 | { return *this; } | |
c766fc5f BK |
444 | }; |
445 | ||
8f94053d PE |
446 | /** |
447 | * @param x A container of arbitrary type. | |
448 | * @return An instance of back_insert_iterator working on @p x. | |
449 | * | |
450 | * This wrapper function helps in creating back_insert_iterator instances. | |
451 | * Typing the name of the %iterator requires knowing the precise full | |
452 | * type of the container, which can be tedious and impedes generic | |
453 | * programming. Using this function lets you take advantage of automatic | |
454 | * template parameter deduction, making the compiler match the correct | |
455 | * types for you. | |
456 | */ | |
b581eaf7 | 457 | template<typename _Container> |
ed6814f7 BI |
458 | inline back_insert_iterator<_Container> |
459 | back_inserter(_Container& __x) | |
c766fc5f BK |
460 | { return back_insert_iterator<_Container>(__x); } |
461 | ||
8f94053d | 462 | /** |
aa2d5ba2 PE |
463 | * @brief Turns assignment into insertion. |
464 | * | |
8f94053d PE |
465 | * These are output iterators, constructed from a container-of-T. |
466 | * Assigning a T to the iterator prepends it to the container using | |
467 | * push_front. | |
468 | * | |
469 | * Tip: Using the front_inserter function to create these iterators can | |
470 | * save typing. | |
471 | */ | |
b581eaf7 | 472 | template<typename _Container> |
ed6814f7 | 473 | class front_insert_iterator |
f591eb23 | 474 | : public iterator<output_iterator_tag, void, void, void, void> |
c766fc5f BK |
475 | { |
476 | protected: | |
8f7a4015 | 477 | _Container* container; |
c766fc5f BK |
478 | |
479 | public: | |
8f94053d | 480 | /// A nested typedef for the type of whatever container you used. |
c766fc5f BK |
481 | typedef _Container container_type; |
482 | ||
8f94053d | 483 | /// The only way to create this %iterator is with a container. |
8f7a4015 | 484 | explicit front_insert_iterator(_Container& __x) : container(&__x) { } |
d27bba5e | 485 | |
8f94053d PE |
486 | /** |
487 | * @param value An instance of whatever type | |
488 | * container_type::const_reference is; presumably a | |
489 | * reference-to-const T for container<T>. | |
490 | * @return This %iterator, for chained operations. | |
491 | * | |
492 | * This kind of %iterator doesn't really have a "position" in the | |
493 | * container (you can think of the position as being permanently at | |
494 | * the front, if you like). Assigning a value to the %iterator will | |
495 | * always prepend the value to the front of the container. | |
496 | */ | |
d27bba5e | 497 | front_insert_iterator& |
ed6814f7 BI |
498 | operator=(typename _Container::const_reference __value) |
499 | { | |
8f7a4015 | 500 | container->push_front(__value); |
c766fc5f BK |
501 | return *this; |
502 | } | |
d27bba5e | 503 | |
45d50699 PC |
504 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
505 | front_insert_iterator& | |
506 | operator=(typename _Container::value_type&& __value) | |
507 | { | |
508 | container->push_front(std::move(__value)); | |
509 | return *this; | |
510 | } | |
511 | #endif | |
512 | ||
8f94053d | 513 | /// Simply returns *this. |
ed6814f7 | 514 | front_insert_iterator& |
f6592a9e PC |
515 | operator*() |
516 | { return *this; } | |
d27bba5e | 517 | |
8f94053d | 518 | /// Simply returns *this. (This %iterator does not "move".) |
ed6814f7 | 519 | front_insert_iterator& |
f6592a9e PC |
520 | operator++() |
521 | { return *this; } | |
d27bba5e | 522 | |
8f94053d | 523 | /// Simply returns *this. (This %iterator does not "move".) |
ed6814f7 | 524 | front_insert_iterator |
f6592a9e PC |
525 | operator++(int) |
526 | { return *this; } | |
c766fc5f BK |
527 | }; |
528 | ||
8f94053d PE |
529 | /** |
530 | * @param x A container of arbitrary type. | |
531 | * @return An instance of front_insert_iterator working on @p x. | |
532 | * | |
533 | * This wrapper function helps in creating front_insert_iterator instances. | |
534 | * Typing the name of the %iterator requires knowing the precise full | |
535 | * type of the container, which can be tedious and impedes generic | |
536 | * programming. Using this function lets you take advantage of automatic | |
537 | * template parameter deduction, making the compiler match the correct | |
538 | * types for you. | |
539 | */ | |
b581eaf7 | 540 | template<typename _Container> |
ed6814f7 BI |
541 | inline front_insert_iterator<_Container> |
542 | front_inserter(_Container& __x) | |
f591eb23 | 543 | { return front_insert_iterator<_Container>(__x); } |
725dc051 | 544 | |
8f94053d | 545 | /** |
aa2d5ba2 PE |
546 | * @brief Turns assignment into insertion. |
547 | * | |
8f94053d PE |
548 | * These are output iterators, constructed from a container-of-T. |
549 | * Assigning a T to the iterator inserts it in the container at the | |
550 | * %iterator's position, rather than overwriting the value at that | |
551 | * position. | |
552 | * | |
553 | * (Sequences will actually insert a @e copy of the value before the | |
554 | * %iterator's position.) | |
555 | * | |
556 | * Tip: Using the inserter function to create these iterators can | |
557 | * save typing. | |
558 | */ | |
b581eaf7 | 559 | template<typename _Container> |
ed6814f7 | 560 | class insert_iterator |
f591eb23 | 561 | : public iterator<output_iterator_tag, void, void, void, void> |
c766fc5f BK |
562 | { |
563 | protected: | |
8f7a4015 | 564 | _Container* container; |
c766fc5f BK |
565 | typename _Container::iterator iter; |
566 | ||
567 | public: | |
8f94053d | 568 | /// A nested typedef for the type of whatever container you used. |
c766fc5f | 569 | typedef _Container container_type; |
ed6814f7 | 570 | |
8f94053d PE |
571 | /** |
572 | * The only way to create this %iterator is with a container and an | |
573 | * initial position (a normal %iterator into the container). | |
574 | */ | |
ed6814f7 | 575 | insert_iterator(_Container& __x, typename _Container::iterator __i) |
8f7a4015 | 576 | : container(&__x), iter(__i) {} |
ed6814f7 | 577 | |
8f94053d PE |
578 | /** |
579 | * @param value An instance of whatever type | |
580 | * container_type::const_reference is; presumably a | |
581 | * reference-to-const T for container<T>. | |
582 | * @return This %iterator, for chained operations. | |
583 | * | |
584 | * This kind of %iterator maintains its own position in the | |
585 | * container. Assigning a value to the %iterator will insert the | |
586 | * value into the container at the place before the %iterator. | |
587 | * | |
588 | * The position is maintained such that subsequent assignments will | |
589 | * insert values immediately after one another. For example, | |
590 | * @code | |
591 | * // vector v contains A and Z | |
592 | * | |
593 | * insert_iterator i (v, ++v.begin()); | |
594 | * i = 1; | |
595 | * i = 2; | |
596 | * i = 3; | |
597 | * | |
598 | * // vector v contains A, 1, 2, 3, and Z | |
599 | * @endcode | |
600 | */ | |
d27bba5e | 601 | insert_iterator& |
45d50699 | 602 | operator=(typename _Container::const_reference __value) |
ed6814f7 | 603 | { |
8f7a4015 | 604 | iter = container->insert(iter, __value); |
c766fc5f BK |
605 | ++iter; |
606 | return *this; | |
607 | } | |
d27bba5e | 608 | |
45d50699 PC |
609 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
610 | insert_iterator& | |
611 | operator=(typename _Container::value_type&& __value) | |
612 | { | |
613 | iter = container->insert(iter, std::move(__value)); | |
614 | ++iter; | |
615 | return *this; | |
616 | } | |
617 | #endif | |
618 | ||
8f94053d | 619 | /// Simply returns *this. |
ed6814f7 | 620 | insert_iterator& |
f6592a9e PC |
621 | operator*() |
622 | { return *this; } | |
d27bba5e | 623 | |
8f94053d | 624 | /// Simply returns *this. (This %iterator does not "move".) |
ed6814f7 | 625 | insert_iterator& |
f6592a9e PC |
626 | operator++() |
627 | { return *this; } | |
d27bba5e | 628 | |
8f94053d | 629 | /// Simply returns *this. (This %iterator does not "move".) |
ed6814f7 | 630 | insert_iterator& |
f6592a9e PC |
631 | operator++(int) |
632 | { return *this; } | |
c766fc5f | 633 | }; |
ed6814f7 | 634 | |
8f94053d PE |
635 | /** |
636 | * @param x A container of arbitrary type. | |
637 | * @return An instance of insert_iterator working on @p x. | |
638 | * | |
639 | * This wrapper function helps in creating insert_iterator instances. | |
640 | * Typing the name of the %iterator requires knowing the precise full | |
641 | * type of the container, which can be tedious and impedes generic | |
642 | * programming. Using this function lets you take advantage of automatic | |
643 | * template parameter deduction, making the compiler match the correct | |
644 | * types for you. | |
645 | */ | |
b581eaf7 | 646 | template<typename _Container, typename _Iterator> |
ed6814f7 | 647 | inline insert_iterator<_Container> |
f591eb23 | 648 | inserter(_Container& __x, _Iterator __i) |
b581eaf7 | 649 | { |
ed6814f7 | 650 | return insert_iterator<_Container>(__x, |
f591eb23 | 651 | typename _Container::iterator(__i)); |
b581eaf7 | 652 | } |
f1e888ae | 653 | |
3cbc7af0 BK |
654 | _GLIBCXX_END_NAMESPACE |
655 | ||
656 | _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) | |
657 | ||
b581eaf7 | 658 | // This iterator adapter is 'normal' in the sense that it does not |
3abbcbb1 | 659 | // change the semantics of any of the operators of its iterator |
b581eaf7 BK |
660 | // parameter. Its primary purpose is to convert an iterator that is |
661 | // not a class, e.g. a pointer, into an iterator that is a class. | |
662 | // The _Container parameter exists solely so that different containers | |
663 | // using this template can instantiate different types, even if the | |
664 | // _Iterator parameter is the same. | |
f1e888ae GDR |
665 | using std::iterator_traits; |
666 | using std::iterator; | |
b581eaf7 BK |
667 | template<typename _Iterator, typename _Container> |
668 | class __normal_iterator | |
b581eaf7 BK |
669 | { |
670 | protected: | |
671 | _Iterator _M_current; | |
ed6814f7 | 672 | |
b581eaf7 | 673 | public: |
f0112db9 | 674 | typedef _Iterator iterator_type; |
86f6262d | 675 | typedef typename iterator_traits<_Iterator>::iterator_category |
f6592a9e | 676 | iterator_category; |
86f6262d | 677 | typedef typename iterator_traits<_Iterator>::value_type value_type; |
ed6814f7 | 678 | typedef typename iterator_traits<_Iterator>::difference_type |
f6592a9e PC |
679 | difference_type; |
680 | typedef typename iterator_traits<_Iterator>::reference reference; | |
681 | typedef typename iterator_traits<_Iterator>::pointer pointer; | |
725dc051 | 682 | |
b581eaf7 | 683 | __normal_iterator() : _M_current(_Iterator()) { } |
725dc051 | 684 | |
ed6814f7 | 685 | explicit |
b581eaf7 | 686 | __normal_iterator(const _Iterator& __i) : _M_current(__i) { } |
725dc051 | 687 | |
b581eaf7 BK |
688 | // Allow iterator to const_iterator conversion |
689 | template<typename _Iter> | |
2bcec729 | 690 | __normal_iterator(const __normal_iterator<_Iter, |
105c6331 BK |
691 | typename __enable_if< |
692 | (std::__are_same<_Iter, typename _Container::pointer>::__value), | |
693 | _Container>::__type>& __i) | |
2bcec729 | 694 | : _M_current(__i.base()) { } |
725dc051 | 695 | |
b581eaf7 BK |
696 | // Forward iterator requirements |
697 | reference | |
f6592a9e PC |
698 | operator*() const |
699 | { return *_M_current; } | |
ed6814f7 | 700 | |
b581eaf7 | 701 | pointer |
f6592a9e PC |
702 | operator->() const |
703 | { return _M_current; } | |
ed6814f7 | 704 | |
b581eaf7 | 705 | __normal_iterator& |
f6592a9e PC |
706 | operator++() |
707 | { | |
708 | ++_M_current; | |
709 | return *this; | |
710 | } | |
ed6814f7 | 711 | |
b581eaf7 | 712 | __normal_iterator |
f6592a9e PC |
713 | operator++(int) |
714 | { return __normal_iterator(_M_current++); } | |
ed6814f7 | 715 | |
b581eaf7 BK |
716 | // Bidirectional iterator requirements |
717 | __normal_iterator& | |
f6592a9e PC |
718 | operator--() |
719 | { | |
720 | --_M_current; | |
721 | return *this; | |
722 | } | |
ed6814f7 | 723 | |
b581eaf7 | 724 | __normal_iterator |
f6592a9e PC |
725 | operator--(int) |
726 | { return __normal_iterator(_M_current--); } | |
ed6814f7 | 727 | |
b581eaf7 BK |
728 | // Random access iterator requirements |
729 | reference | |
730 | operator[](const difference_type& __n) const | |
731 | { return _M_current[__n]; } | |
ed6814f7 | 732 | |
b581eaf7 BK |
733 | __normal_iterator& |
734 | operator+=(const difference_type& __n) | |
735 | { _M_current += __n; return *this; } | |
725dc051 | 736 | |
b581eaf7 BK |
737 | __normal_iterator |
738 | operator+(const difference_type& __n) const | |
739 | { return __normal_iterator(_M_current + __n); } | |
ed6814f7 | 740 | |
b581eaf7 BK |
741 | __normal_iterator& |
742 | operator-=(const difference_type& __n) | |
743 | { _M_current -= __n; return *this; } | |
ed6814f7 | 744 | |
b581eaf7 BK |
745 | __normal_iterator |
746 | operator-(const difference_type& __n) const | |
747 | { return __normal_iterator(_M_current - __n); } | |
ed6814f7 BI |
748 | |
749 | const _Iterator& | |
f6592a9e PC |
750 | base() const |
751 | { return _M_current; } | |
b581eaf7 | 752 | }; |
725dc051 | 753 | |
f1e888ae GDR |
754 | // Note: In what follows, the left- and right-hand-side iterators are |
755 | // allowed to vary in types (conceptually in cv-qualification) so that | |
28dac70a | 756 | // comparison between cv-qualified and non-cv-qualified iterators be |
f1e888ae GDR |
757 | // valid. However, the greedy and unfriendly operators in std::rel_ops |
758 | // will make overload resolution ambiguous (when in scope) if we don't | |
759 | // provide overloads whose operands are of the same type. Can someone | |
760 | // remind me what generic programming is about? -- Gaby | |
ed6814f7 | 761 | |
b581eaf7 BK |
762 | // Forward iterator requirements |
763 | template<typename _IteratorL, typename _IteratorR, typename _Container> | |
f6592a9e PC |
764 | inline bool |
765 | operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
766 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
767 | { return __lhs.base() == __rhs.base(); } | |
b581eaf7 | 768 | |
f1e888ae | 769 | template<typename _Iterator, typename _Container> |
f6592a9e PC |
770 | inline bool |
771 | operator==(const __normal_iterator<_Iterator, _Container>& __lhs, | |
772 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
773 | { return __lhs.base() == __rhs.base(); } | |
f1e888ae | 774 | |
b581eaf7 | 775 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
f6592a9e PC |
776 | inline bool |
777 | operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
778 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
779 | { return __lhs.base() != __rhs.base(); } | |
f1e888ae GDR |
780 | |
781 | template<typename _Iterator, typename _Container> | |
f6592a9e PC |
782 | inline bool |
783 | operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, | |
784 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
785 | { return __lhs.base() != __rhs.base(); } | |
725dc051 BK |
786 | |
787 | // Random access iterator requirements | |
b581eaf7 | 788 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
ed6814f7 | 789 | inline bool |
f6592a9e PC |
790 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, |
791 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
792 | { return __lhs.base() < __rhs.base(); } | |
b581eaf7 | 793 | |
f1e888ae | 794 | template<typename _Iterator, typename _Container> |
f6592a9e PC |
795 | inline bool |
796 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs, | |
797 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
798 | { return __lhs.base() < __rhs.base(); } | |
f1e888ae | 799 | |
b581eaf7 | 800 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
f6592a9e PC |
801 | inline bool |
802 | operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
803 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
804 | { return __lhs.base() > __rhs.base(); } | |
f1e888ae GDR |
805 | |
806 | template<typename _Iterator, typename _Container> | |
f6592a9e PC |
807 | inline bool |
808 | operator>(const __normal_iterator<_Iterator, _Container>& __lhs, | |
809 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
810 | { return __lhs.base() > __rhs.base(); } | |
b581eaf7 BK |
811 | |
812 | template<typename _IteratorL, typename _IteratorR, typename _Container> | |
f6592a9e PC |
813 | inline bool |
814 | operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
815 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
816 | { return __lhs.base() <= __rhs.base(); } | |
f1e888ae GDR |
817 | |
818 | template<typename _Iterator, typename _Container> | |
f6592a9e PC |
819 | inline bool |
820 | operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, | |
821 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
822 | { return __lhs.base() <= __rhs.base(); } | |
b581eaf7 BK |
823 | |
824 | template<typename _IteratorL, typename _IteratorR, typename _Container> | |
f6592a9e PC |
825 | inline bool |
826 | operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
827 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
828 | { return __lhs.base() >= __rhs.base(); } | |
f1e888ae GDR |
829 | |
830 | template<typename _Iterator, typename _Container> | |
f6592a9e PC |
831 | inline bool |
832 | operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, | |
833 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
834 | { return __lhs.base() >= __rhs.base(); } | |
b581eaf7 | 835 | |
3d7c150e | 836 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
d16ecaec PC |
837 | // According to the resolution of DR179 not only the various comparison |
838 | // operators but also operator- must accept mixed iterator/const_iterator | |
839 | // parameters. | |
840 | template<typename _IteratorL, typename _IteratorR, typename _Container> | |
5defb0f2 PC |
841 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
842 | // DR 685. | |
843 | inline auto | |
844 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
845 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
846 | -> decltype(__lhs.base() - __rhs.base()) | |
847 | #else | |
f6592a9e PC |
848 | inline typename __normal_iterator<_IteratorL, _Container>::difference_type |
849 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, | |
850 | const __normal_iterator<_IteratorR, _Container>& __rhs) | |
5defb0f2 | 851 | #endif |
f6592a9e | 852 | { return __lhs.base() - __rhs.base(); } |
d16ecaec | 853 | |
3af22b23 PC |
854 | template<typename _Iterator, typename _Container> |
855 | inline typename __normal_iterator<_Iterator, _Container>::difference_type | |
856 | operator-(const __normal_iterator<_Iterator, _Container>& __lhs, | |
857 | const __normal_iterator<_Iterator, _Container>& __rhs) | |
858 | { return __lhs.base() - __rhs.base(); } | |
859 | ||
b581eaf7 | 860 | template<typename _Iterator, typename _Container> |
f6592a9e PC |
861 | inline __normal_iterator<_Iterator, _Container> |
862 | operator+(typename __normal_iterator<_Iterator, _Container>::difference_type | |
863 | __n, const __normal_iterator<_Iterator, _Container>& __i) | |
864 | { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } | |
725dc051 | 865 | |
3cbc7af0 | 866 | _GLIBCXX_END_NAMESPACE |
725dc051 | 867 | |
f63bc637 PC |
868 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
869 | ||
870 | _GLIBCXX_BEGIN_NAMESPACE(std) | |
871 | ||
872 | // 24.4.3 Move iterators | |
873 | /** | |
f63bc637 PC |
874 | * Class template move_iterator is an iterator adapter with the same |
875 | * behavior as the underlying iterator except that its dereference | |
876 | * operator implicitly converts the value returned by the underlying | |
877 | * iterator's dereference operator to an rvalue reference. Some | |
878 | * generic algorithms can be called with move iterators to replace | |
879 | * copying with moving. | |
f63bc637 PC |
880 | */ |
881 | template<typename _Iterator> | |
882 | class move_iterator | |
883 | { | |
884 | protected: | |
885 | _Iterator _M_current; | |
886 | ||
887 | public: | |
888 | typedef _Iterator iterator_type; | |
889 | typedef typename iterator_traits<_Iterator>::difference_type | |
890 | difference_type; | |
1a1b20be PC |
891 | // NB: DR 680. |
892 | typedef _Iterator pointer; | |
f63bc637 PC |
893 | typedef typename iterator_traits<_Iterator>::value_type value_type; |
894 | typedef typename iterator_traits<_Iterator>::iterator_category | |
895 | iterator_category; | |
896 | typedef value_type&& reference; | |
897 | ||
898 | public: | |
899 | move_iterator() | |
900 | : _M_current() { } | |
901 | ||
902 | explicit | |
903 | move_iterator(iterator_type __i) | |
904 | : _M_current(__i) { } | |
905 | ||
906 | template<typename _Iter> | |
907 | move_iterator(const move_iterator<_Iter>& __i) | |
908 | : _M_current(__i.base()) { } | |
909 | ||
910 | iterator_type | |
911 | base() const | |
912 | { return _M_current; } | |
913 | ||
914 | reference | |
915 | operator*() const | |
916 | { return *_M_current; } | |
917 | ||
918 | pointer | |
919 | operator->() const | |
920 | { return _M_current; } | |
921 | ||
922 | move_iterator& | |
923 | operator++() | |
924 | { | |
925 | ++_M_current; | |
926 | return *this; | |
927 | } | |
928 | ||
929 | move_iterator | |
930 | operator++(int) | |
931 | { | |
932 | move_iterator __tmp = *this; | |
933 | ++_M_current; | |
934 | return __tmp; | |
935 | } | |
936 | ||
937 | move_iterator& | |
938 | operator--() | |
939 | { | |
940 | --_M_current; | |
941 | return *this; | |
942 | } | |
943 | ||
944 | move_iterator | |
945 | operator--(int) | |
946 | { | |
947 | move_iterator __tmp = *this; | |
948 | --_M_current; | |
949 | return __tmp; | |
950 | } | |
951 | ||
952 | move_iterator | |
953 | operator+(difference_type __n) const | |
954 | { return move_iterator(_M_current + __n); } | |
955 | ||
956 | move_iterator& | |
957 | operator+=(difference_type __n) | |
958 | { | |
959 | _M_current += __n; | |
960 | return *this; | |
961 | } | |
962 | ||
963 | move_iterator | |
964 | operator-(difference_type __n) const | |
965 | { return move_iterator(_M_current - __n); } | |
966 | ||
967 | move_iterator& | |
968 | operator-=(difference_type __n) | |
969 | { | |
970 | _M_current -= __n; | |
971 | return *this; | |
972 | } | |
973 | ||
974 | reference | |
975 | operator[](difference_type __n) const | |
976 | { return _M_current[__n]; } | |
977 | }; | |
978 | ||
979 | template<typename _IteratorL, typename _IteratorR> | |
980 | inline bool | |
981 | operator==(const move_iterator<_IteratorL>& __x, | |
982 | const move_iterator<_IteratorR>& __y) | |
983 | { return __x.base() == __y.base(); } | |
984 | ||
985 | template<typename _IteratorL, typename _IteratorR> | |
986 | inline bool | |
987 | operator!=(const move_iterator<_IteratorL>& __x, | |
988 | const move_iterator<_IteratorR>& __y) | |
989 | { return !(__x == __y); } | |
990 | ||
991 | template<typename _IteratorL, typename _IteratorR> | |
992 | inline bool | |
993 | operator<(const move_iterator<_IteratorL>& __x, | |
994 | const move_iterator<_IteratorR>& __y) | |
995 | { return __x.base() < __y.base(); } | |
996 | ||
997 | template<typename _IteratorL, typename _IteratorR> | |
998 | inline bool | |
999 | operator<=(const move_iterator<_IteratorL>& __x, | |
1000 | const move_iterator<_IteratorR>& __y) | |
1001 | { return !(__y < __x); } | |
1002 | ||
1003 | template<typename _IteratorL, typename _IteratorR> | |
1004 | inline bool | |
1005 | operator>(const move_iterator<_IteratorL>& __x, | |
1006 | const move_iterator<_IteratorR>& __y) | |
1007 | { return __y < __x; } | |
1008 | ||
1009 | template<typename _IteratorL, typename _IteratorR> | |
1010 | inline bool | |
1011 | operator>=(const move_iterator<_IteratorL>& __x, | |
1012 | const move_iterator<_IteratorR>& __y) | |
1013 | { return !(__x < __y); } | |
1014 | ||
5defb0f2 | 1015 | // DR 685. |
f63bc637 | 1016 | template<typename _IteratorL, typename _IteratorR> |
5defb0f2 | 1017 | inline auto |
f63bc637 PC |
1018 | operator-(const move_iterator<_IteratorL>& __x, |
1019 | const move_iterator<_IteratorR>& __y) | |
5defb0f2 | 1020 | -> decltype(__x.base() - __y.base()) |
f63bc637 PC |
1021 | { return __x.base() - __y.base(); } |
1022 | ||
1023 | template<typename _Iterator> | |
1024 | inline move_iterator<_Iterator> | |
1025 | operator+(typename move_iterator<_Iterator>::difference_type __n, | |
1026 | const move_iterator<_Iterator>& __x) | |
1027 | { return __x + __n; } | |
1028 | ||
1029 | template<typename _Iterator> | |
1030 | inline move_iterator<_Iterator> | |
1031 | make_move_iterator(const _Iterator& __i) | |
1032 | { return move_iterator<_Iterator>(__i); } | |
1033 | ||
1034 | _GLIBCXX_END_NAMESPACE | |
1035 | ||
245a5fe5 PC |
1036 | #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) |
1037 | #else | |
1038 | #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) | |
f63bc637 PC |
1039 | #endif // __GXX_EXPERIMENTAL_CXX0X__ |
1040 | ||
3cbc7af0 | 1041 | #endif |