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