197403Sobrien// Iterators -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996-1998 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_iterator.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien * 6197403Sobrien * This file implements reverse_iterator, back_insert_iterator, 6297403Sobrien * front_insert_iterator, insert_iterator, __normal_iterator, and their 6397403Sobrien * supporting functions and overloaded operators. 6497403Sobrien */ 6597403Sobrien 66132720Skan#ifndef _ITERATOR_H 67132720Skan#define _ITERATOR_H 1 6897403Sobrien 69169691Skan#include <bits/cpp_type_traits.h> 70169691Skan#include <ext/type_traits.h> 71169691Skan 72169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 73169691Skan 7497403Sobrien // 24.4.1 Reverse iterators 7597403Sobrien /** 7697403Sobrien * "Bidirectional and random access iterators have corresponding reverse 7797403Sobrien * %iterator adaptors that iterate through the data structure in the 7897403Sobrien * opposite direction. They have the same signatures as the corresponding 7997403Sobrien * iterators. The fundamental relation between a reverse %iterator and its 8097403Sobrien * corresponding %iterator @c i is established by the identity: 8197403Sobrien * @code 8297403Sobrien * &*(reverse_iterator(i)) == &*(i - 1) 8397403Sobrien * @endcode 8497403Sobrien * 8597403Sobrien * This mapping is dictated by the fact that while there is always a 8697403Sobrien * pointer past the end of an array, there might not be a valid pointer 8797403Sobrien * before the beginning of an array." [24.4.1]/1,2 8897403Sobrien * 8997403Sobrien * Reverse iterators can be tricky and surprising at first. Their 9097403Sobrien * semantics make sense, however, and the trickiness is a side effect of 9197403Sobrien * the requirement that the iterators must be safe. 9297403Sobrien */ 9397403Sobrien template<typename _Iterator> 94132720Skan class reverse_iterator 9597403Sobrien : public iterator<typename iterator_traits<_Iterator>::iterator_category, 9697403Sobrien typename iterator_traits<_Iterator>::value_type, 9797403Sobrien typename iterator_traits<_Iterator>::difference_type, 9897403Sobrien typename iterator_traits<_Iterator>::pointer, 9997403Sobrien typename iterator_traits<_Iterator>::reference> 10097403Sobrien { 10197403Sobrien protected: 10297403Sobrien _Iterator current; 10397403Sobrien 10497403Sobrien public: 105132720Skan typedef _Iterator iterator_type; 106132720Skan typedef typename iterator_traits<_Iterator>::difference_type 107132720Skan difference_type; 10897403Sobrien typedef typename iterator_traits<_Iterator>::reference reference; 10997403Sobrien typedef typename iterator_traits<_Iterator>::pointer pointer; 11097403Sobrien 11197403Sobrien public: 11297403Sobrien /** 113117397Skan * The default constructor default-initializes member @p current. 114117397Skan * If it is a pointer, that means it is zero-initialized. 11597403Sobrien */ 116132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 117117397Skan // 235 No specification of default ctor for reverse_iterator 118117397Skan reverse_iterator() : current() { } 11997403Sobrien 12097403Sobrien /** 12197403Sobrien * This %iterator will move in the opposite direction that @p x does. 12297403Sobrien */ 123132720Skan explicit 12497403Sobrien reverse_iterator(iterator_type __x) : current(__x) { } 12597403Sobrien 12697403Sobrien /** 12797403Sobrien * The copy constructor is normal. 12897403Sobrien */ 129132720Skan reverse_iterator(const reverse_iterator& __x) 13097403Sobrien : current(__x.current) { } 13197403Sobrien 13297403Sobrien /** 13397403Sobrien * A reverse_iterator across other types can be copied in the normal 13497403Sobrien * fashion. 13597403Sobrien */ 13697403Sobrien template<typename _Iter> 13797403Sobrien reverse_iterator(const reverse_iterator<_Iter>& __x) 13897403Sobrien : current(__x.base()) { } 139132720Skan 14097403Sobrien /** 14197403Sobrien * @return @c current, the %iterator used for underlying work. 14297403Sobrien */ 143132720Skan iterator_type 144132720Skan base() const 145132720Skan { return current; } 14697403Sobrien 14797403Sobrien /** 14897403Sobrien * @return TODO 14997403Sobrien * 15097403Sobrien * @doctodo 15197403Sobrien */ 152132720Skan reference 153132720Skan operator*() const 15497403Sobrien { 15597403Sobrien _Iterator __tmp = current; 15697403Sobrien return *--__tmp; 15797403Sobrien } 15897403Sobrien 15997403Sobrien /** 16097403Sobrien * @return TODO 16197403Sobrien * 16297403Sobrien * @doctodo 16397403Sobrien */ 164132720Skan pointer 165132720Skan operator->() const 166132720Skan { return &(operator*()); } 16797403Sobrien 16897403Sobrien /** 16997403Sobrien * @return TODO 17097403Sobrien * 17197403Sobrien * @doctodo 17297403Sobrien */ 173132720Skan reverse_iterator& 174132720Skan operator++() 17597403Sobrien { 17697403Sobrien --current; 17797403Sobrien return *this; 17897403Sobrien } 17997403Sobrien 18097403Sobrien /** 18197403Sobrien * @return TODO 18297403Sobrien * 18397403Sobrien * @doctodo 18497403Sobrien */ 185132720Skan reverse_iterator 186132720Skan operator++(int) 18797403Sobrien { 18897403Sobrien reverse_iterator __tmp = *this; 18997403Sobrien --current; 19097403Sobrien return __tmp; 19197403Sobrien } 19297403Sobrien 19397403Sobrien /** 19497403Sobrien * @return TODO 19597403Sobrien * 19697403Sobrien * @doctodo 19797403Sobrien */ 198132720Skan reverse_iterator& 199132720Skan operator--() 20097403Sobrien { 20197403Sobrien ++current; 20297403Sobrien return *this; 20397403Sobrien } 20497403Sobrien 20597403Sobrien /** 20697403Sobrien * @return TODO 20797403Sobrien * 20897403Sobrien * @doctodo 20997403Sobrien */ 210169691Skan reverse_iterator 211169691Skan operator--(int) 21297403Sobrien { 21397403Sobrien reverse_iterator __tmp = *this; 21497403Sobrien ++current; 21597403Sobrien return __tmp; 21697403Sobrien } 217132720Skan 21897403Sobrien /** 21997403Sobrien * @return TODO 22097403Sobrien * 22197403Sobrien * @doctodo 22297403Sobrien */ 223132720Skan reverse_iterator 224132720Skan operator+(difference_type __n) const 22597403Sobrien { return reverse_iterator(current - __n); } 22697403Sobrien 22797403Sobrien /** 22897403Sobrien * @return TODO 22997403Sobrien * 23097403Sobrien * @doctodo 23197403Sobrien */ 232132720Skan reverse_iterator& 233132720Skan operator+=(difference_type __n) 23497403Sobrien { 23597403Sobrien current -= __n; 23697403Sobrien return *this; 23797403Sobrien } 23897403Sobrien 23997403Sobrien /** 24097403Sobrien * @return TODO 24197403Sobrien * 24297403Sobrien * @doctodo 24397403Sobrien */ 244132720Skan reverse_iterator 245132720Skan operator-(difference_type __n) const 24697403Sobrien { return reverse_iterator(current + __n); } 24797403Sobrien 24897403Sobrien /** 24997403Sobrien * @return TODO 25097403Sobrien * 25197403Sobrien * @doctodo 25297403Sobrien */ 253132720Skan reverse_iterator& 254132720Skan operator-=(difference_type __n) 25597403Sobrien { 25697403Sobrien current += __n; 25797403Sobrien return *this; 25897403Sobrien } 25997403Sobrien 26097403Sobrien /** 26197403Sobrien * @return TODO 26297403Sobrien * 26397403Sobrien * @doctodo 26497403Sobrien */ 265132720Skan reference 266132720Skan operator[](difference_type __n) const 267132720Skan { return *(*this + __n); } 268132720Skan }; 269132720Skan 27097403Sobrien //@{ 27197403Sobrien /** 27297403Sobrien * @param x A %reverse_iterator. 27397403Sobrien * @param y A %reverse_iterator. 27497403Sobrien * @return A simple bool. 27597403Sobrien * 27697403Sobrien * Reverse iterators forward many operations to their underlying base() 27797403Sobrien * iterators. Others are implemented in terms of one another. 27897403Sobrien * 27997403Sobrien */ 28097403Sobrien template<typename _Iterator> 281132720Skan inline bool 282132720Skan operator==(const reverse_iterator<_Iterator>& __x, 283132720Skan const reverse_iterator<_Iterator>& __y) 28497403Sobrien { return __x.base() == __y.base(); } 28597403Sobrien 28697403Sobrien template<typename _Iterator> 287132720Skan inline bool 288132720Skan operator<(const reverse_iterator<_Iterator>& __x, 289132720Skan const reverse_iterator<_Iterator>& __y) 29097403Sobrien { return __y.base() < __x.base(); } 29197403Sobrien 29297403Sobrien template<typename _Iterator> 293132720Skan inline bool 294132720Skan operator!=(const reverse_iterator<_Iterator>& __x, 295132720Skan const reverse_iterator<_Iterator>& __y) 29697403Sobrien { return !(__x == __y); } 29797403Sobrien 29897403Sobrien template<typename _Iterator> 299132720Skan inline bool 300132720Skan operator>(const reverse_iterator<_Iterator>& __x, 301132720Skan const reverse_iterator<_Iterator>& __y) 30297403Sobrien { return __y < __x; } 30397403Sobrien 30497403Sobrien template<typename _Iterator> 305132720Skan inline bool 306132720Skan operator<=(const reverse_iterator<_Iterator>& __x, 307169691Skan const reverse_iterator<_Iterator>& __y) 30897403Sobrien { return !(__y < __x); } 30997403Sobrien 31097403Sobrien template<typename _Iterator> 311132720Skan inline bool 312132720Skan operator>=(const reverse_iterator<_Iterator>& __x, 313132720Skan const reverse_iterator<_Iterator>& __y) 31497403Sobrien { return !(__x < __y); } 31597403Sobrien 31697403Sobrien template<typename _Iterator> 31797403Sobrien inline typename reverse_iterator<_Iterator>::difference_type 318132720Skan operator-(const reverse_iterator<_Iterator>& __x, 319132720Skan const reverse_iterator<_Iterator>& __y) 32097403Sobrien { return __y.base() - __x.base(); } 32197403Sobrien 32297403Sobrien template<typename _Iterator> 323132720Skan inline reverse_iterator<_Iterator> 32497403Sobrien operator+(typename reverse_iterator<_Iterator>::difference_type __n, 325132720Skan const reverse_iterator<_Iterator>& __x) 32697403Sobrien { return reverse_iterator<_Iterator>(__x.base() - __n); } 327169691Skan 328169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 329169691Skan // DR 280. Comparison of reverse_iterator to const reverse_iterator. 330169691Skan template<typename _IteratorL, typename _IteratorR> 331169691Skan inline bool 332169691Skan operator==(const reverse_iterator<_IteratorL>& __x, 333169691Skan const reverse_iterator<_IteratorR>& __y) 334169691Skan { return __x.base() == __y.base(); } 335169691Skan 336169691Skan template<typename _IteratorL, typename _IteratorR> 337169691Skan inline bool 338169691Skan operator<(const reverse_iterator<_IteratorL>& __x, 339169691Skan const reverse_iterator<_IteratorR>& __y) 340169691Skan { return __y.base() < __x.base(); } 341169691Skan 342169691Skan template<typename _IteratorL, typename _IteratorR> 343169691Skan inline bool 344169691Skan operator!=(const reverse_iterator<_IteratorL>& __x, 345169691Skan const reverse_iterator<_IteratorR>& __y) 346169691Skan { return !(__x == __y); } 347169691Skan 348169691Skan template<typename _IteratorL, typename _IteratorR> 349169691Skan inline bool 350169691Skan operator>(const reverse_iterator<_IteratorL>& __x, 351169691Skan const reverse_iterator<_IteratorR>& __y) 352169691Skan { return __y < __x; } 353169691Skan 354169691Skan template<typename _IteratorL, typename _IteratorR> 355169691Skan inline bool 356169691Skan operator<=(const reverse_iterator<_IteratorL>& __x, 357169691Skan const reverse_iterator<_IteratorR>& __y) 358169691Skan { return !(__y < __x); } 359169691Skan 360169691Skan template<typename _IteratorL, typename _IteratorR> 361169691Skan inline bool 362169691Skan operator>=(const reverse_iterator<_IteratorL>& __x, 363169691Skan const reverse_iterator<_IteratorR>& __y) 364169691Skan { return !(__x < __y); } 365169691Skan 366169691Skan template<typename _IteratorL, typename _IteratorR> 367169691Skan inline typename reverse_iterator<_IteratorL>::difference_type 368169691Skan operator-(const reverse_iterator<_IteratorL>& __x, 369169691Skan const reverse_iterator<_IteratorR>& __y) 370169691Skan { return __y.base() - __x.base(); } 37197403Sobrien //@} 37297403Sobrien 37397403Sobrien // 24.4.2.2.1 back_insert_iterator 37497403Sobrien /** 375117397Skan * @brief Turns assignment into insertion. 376117397Skan * 37797403Sobrien * These are output iterators, constructed from a container-of-T. 37897403Sobrien * Assigning a T to the iterator appends it to the container using 37997403Sobrien * push_back. 38097403Sobrien * 38197403Sobrien * Tip: Using the back_inserter function to create these iterators can 38297403Sobrien * save typing. 38397403Sobrien */ 38497403Sobrien template<typename _Container> 385132720Skan class back_insert_iterator 38697403Sobrien : public iterator<output_iterator_tag, void, void, void, void> 38797403Sobrien { 38897403Sobrien protected: 38997403Sobrien _Container* container; 39097403Sobrien 39197403Sobrien public: 39297403Sobrien /// A nested typedef for the type of whatever container you used. 39397403Sobrien typedef _Container container_type; 394132720Skan 39597403Sobrien /// The only way to create this %iterator is with a container. 396132720Skan explicit 39797403Sobrien back_insert_iterator(_Container& __x) : container(&__x) { } 39897403Sobrien 39997403Sobrien /** 40097403Sobrien * @param value An instance of whatever type 40197403Sobrien * container_type::const_reference is; presumably a 40297403Sobrien * reference-to-const T for container<T>. 40397403Sobrien * @return This %iterator, for chained operations. 40497403Sobrien * 40597403Sobrien * This kind of %iterator doesn't really have a "position" in the 40697403Sobrien * container (you can think of the position as being permanently at 40797403Sobrien * the end, if you like). Assigning a value to the %iterator will 40897403Sobrien * always append the value to the end of the container. 40997403Sobrien */ 41097403Sobrien back_insert_iterator& 411132720Skan operator=(typename _Container::const_reference __value) 412132720Skan { 41397403Sobrien container->push_back(__value); 41497403Sobrien return *this; 41597403Sobrien } 41697403Sobrien 41797403Sobrien /// Simply returns *this. 418132720Skan back_insert_iterator& 419132720Skan operator*() 420132720Skan { return *this; } 42197403Sobrien 42297403Sobrien /// Simply returns *this. (This %iterator does not "move".) 423132720Skan back_insert_iterator& 424132720Skan operator++() 425132720Skan { return *this; } 42697403Sobrien 42797403Sobrien /// Simply returns *this. (This %iterator does not "move".) 42897403Sobrien back_insert_iterator 429132720Skan operator++(int) 430132720Skan { return *this; } 43197403Sobrien }; 43297403Sobrien 43397403Sobrien /** 43497403Sobrien * @param x A container of arbitrary type. 43597403Sobrien * @return An instance of back_insert_iterator working on @p x. 43697403Sobrien * 43797403Sobrien * This wrapper function helps in creating back_insert_iterator instances. 43897403Sobrien * Typing the name of the %iterator requires knowing the precise full 43997403Sobrien * type of the container, which can be tedious and impedes generic 44097403Sobrien * programming. Using this function lets you take advantage of automatic 44197403Sobrien * template parameter deduction, making the compiler match the correct 44297403Sobrien * types for you. 44397403Sobrien */ 44497403Sobrien template<typename _Container> 445132720Skan inline back_insert_iterator<_Container> 446132720Skan back_inserter(_Container& __x) 44797403Sobrien { return back_insert_iterator<_Container>(__x); } 44897403Sobrien 44997403Sobrien /** 450117397Skan * @brief Turns assignment into insertion. 451117397Skan * 45297403Sobrien * These are output iterators, constructed from a container-of-T. 45397403Sobrien * Assigning a T to the iterator prepends it to the container using 45497403Sobrien * push_front. 45597403Sobrien * 45697403Sobrien * Tip: Using the front_inserter function to create these iterators can 45797403Sobrien * save typing. 45897403Sobrien */ 45997403Sobrien template<typename _Container> 460132720Skan class front_insert_iterator 46197403Sobrien : public iterator<output_iterator_tag, void, void, void, void> 46297403Sobrien { 46397403Sobrien protected: 46497403Sobrien _Container* container; 46597403Sobrien 46697403Sobrien public: 46797403Sobrien /// A nested typedef for the type of whatever container you used. 46897403Sobrien typedef _Container container_type; 46997403Sobrien 47097403Sobrien /// The only way to create this %iterator is with a container. 47197403Sobrien explicit front_insert_iterator(_Container& __x) : container(&__x) { } 47297403Sobrien 47397403Sobrien /** 47497403Sobrien * @param value An instance of whatever type 47597403Sobrien * container_type::const_reference is; presumably a 47697403Sobrien * reference-to-const T for container<T>. 47797403Sobrien * @return This %iterator, for chained operations. 47897403Sobrien * 47997403Sobrien * This kind of %iterator doesn't really have a "position" in the 48097403Sobrien * container (you can think of the position as being permanently at 48197403Sobrien * the front, if you like). Assigning a value to the %iterator will 48297403Sobrien * always prepend the value to the front of the container. 48397403Sobrien */ 48497403Sobrien front_insert_iterator& 485132720Skan operator=(typename _Container::const_reference __value) 486132720Skan { 48797403Sobrien container->push_front(__value); 48897403Sobrien return *this; 48997403Sobrien } 49097403Sobrien 49197403Sobrien /// Simply returns *this. 492132720Skan front_insert_iterator& 493132720Skan operator*() 494132720Skan { return *this; } 49597403Sobrien 49697403Sobrien /// Simply returns *this. (This %iterator does not "move".) 497132720Skan front_insert_iterator& 498132720Skan operator++() 499132720Skan { return *this; } 50097403Sobrien 50197403Sobrien /// Simply returns *this. (This %iterator does not "move".) 502132720Skan front_insert_iterator 503132720Skan operator++(int) 504132720Skan { return *this; } 50597403Sobrien }; 50697403Sobrien 50797403Sobrien /** 50897403Sobrien * @param x A container of arbitrary type. 50997403Sobrien * @return An instance of front_insert_iterator working on @p x. 51097403Sobrien * 51197403Sobrien * This wrapper function helps in creating front_insert_iterator instances. 51297403Sobrien * Typing the name of the %iterator requires knowing the precise full 51397403Sobrien * type of the container, which can be tedious and impedes generic 51497403Sobrien * programming. Using this function lets you take advantage of automatic 51597403Sobrien * template parameter deduction, making the compiler match the correct 51697403Sobrien * types for you. 51797403Sobrien */ 51897403Sobrien template<typename _Container> 519132720Skan inline front_insert_iterator<_Container> 520132720Skan front_inserter(_Container& __x) 52197403Sobrien { return front_insert_iterator<_Container>(__x); } 52297403Sobrien 52397403Sobrien /** 524117397Skan * @brief Turns assignment into insertion. 525117397Skan * 52697403Sobrien * These are output iterators, constructed from a container-of-T. 52797403Sobrien * Assigning a T to the iterator inserts it in the container at the 52897403Sobrien * %iterator's position, rather than overwriting the value at that 52997403Sobrien * position. 53097403Sobrien * 53197403Sobrien * (Sequences will actually insert a @e copy of the value before the 53297403Sobrien * %iterator's position.) 53397403Sobrien * 53497403Sobrien * Tip: Using the inserter function to create these iterators can 53597403Sobrien * save typing. 53697403Sobrien */ 53797403Sobrien template<typename _Container> 538132720Skan class insert_iterator 53997403Sobrien : public iterator<output_iterator_tag, void, void, void, void> 54097403Sobrien { 54197403Sobrien protected: 54297403Sobrien _Container* container; 54397403Sobrien typename _Container::iterator iter; 54497403Sobrien 54597403Sobrien public: 54697403Sobrien /// A nested typedef for the type of whatever container you used. 54797403Sobrien typedef _Container container_type; 548132720Skan 54997403Sobrien /** 55097403Sobrien * The only way to create this %iterator is with a container and an 55197403Sobrien * initial position (a normal %iterator into the container). 55297403Sobrien */ 553132720Skan insert_iterator(_Container& __x, typename _Container::iterator __i) 55497403Sobrien : container(&__x), iter(__i) {} 555132720Skan 55697403Sobrien /** 55797403Sobrien * @param value An instance of whatever type 55897403Sobrien * container_type::const_reference is; presumably a 55997403Sobrien * reference-to-const T for container<T>. 56097403Sobrien * @return This %iterator, for chained operations. 56197403Sobrien * 56297403Sobrien * This kind of %iterator maintains its own position in the 56397403Sobrien * container. Assigning a value to the %iterator will insert the 56497403Sobrien * value into the container at the place before the %iterator. 56597403Sobrien * 56697403Sobrien * The position is maintained such that subsequent assignments will 56797403Sobrien * insert values immediately after one another. For example, 56897403Sobrien * @code 56997403Sobrien * // vector v contains A and Z 57097403Sobrien * 57197403Sobrien * insert_iterator i (v, ++v.begin()); 57297403Sobrien * i = 1; 57397403Sobrien * i = 2; 57497403Sobrien * i = 3; 57597403Sobrien * 57697403Sobrien * // vector v contains A, 1, 2, 3, and Z 57797403Sobrien * @endcode 57897403Sobrien */ 57997403Sobrien insert_iterator& 580132720Skan operator=(const typename _Container::const_reference __value) 581132720Skan { 58297403Sobrien iter = container->insert(iter, __value); 58397403Sobrien ++iter; 58497403Sobrien return *this; 58597403Sobrien } 58697403Sobrien 58797403Sobrien /// Simply returns *this. 588132720Skan insert_iterator& 589132720Skan operator*() 590132720Skan { return *this; } 59197403Sobrien 59297403Sobrien /// Simply returns *this. (This %iterator does not "move".) 593132720Skan insert_iterator& 594132720Skan operator++() 595132720Skan { return *this; } 59697403Sobrien 59797403Sobrien /// Simply returns *this. (This %iterator does not "move".) 598132720Skan insert_iterator& 599132720Skan operator++(int) 600132720Skan { return *this; } 60197403Sobrien }; 602132720Skan 60397403Sobrien /** 60497403Sobrien * @param x A container of arbitrary type. 60597403Sobrien * @return An instance of insert_iterator working on @p x. 60697403Sobrien * 60797403Sobrien * This wrapper function helps in creating insert_iterator instances. 60897403Sobrien * Typing the name of the %iterator requires knowing the precise full 60997403Sobrien * type of the container, which can be tedious and impedes generic 61097403Sobrien * programming. Using this function lets you take advantage of automatic 61197403Sobrien * template parameter deduction, making the compiler match the correct 61297403Sobrien * types for you. 61397403Sobrien */ 61497403Sobrien template<typename _Container, typename _Iterator> 615132720Skan inline insert_iterator<_Container> 61697403Sobrien inserter(_Container& __x, _Iterator __i) 61797403Sobrien { 618132720Skan return insert_iterator<_Container>(__x, 61997403Sobrien typename _Container::iterator(__i)); 62097403Sobrien } 62197403Sobrien 622169691Skan_GLIBCXX_END_NAMESPACE 623169691Skan 624169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 625169691Skan 62697403Sobrien // This iterator adapter is 'normal' in the sense that it does not 62797403Sobrien // change the semantics of any of the operators of its iterator 62897403Sobrien // parameter. Its primary purpose is to convert an iterator that is 62997403Sobrien // not a class, e.g. a pointer, into an iterator that is a class. 63097403Sobrien // The _Container parameter exists solely so that different containers 63197403Sobrien // using this template can instantiate different types, even if the 63297403Sobrien // _Iterator parameter is the same. 63397403Sobrien using std::iterator_traits; 63497403Sobrien using std::iterator; 63597403Sobrien template<typename _Iterator, typename _Container> 63697403Sobrien class __normal_iterator 63797403Sobrien { 63897403Sobrien protected: 63997403Sobrien _Iterator _M_current; 640132720Skan 64197403Sobrien public: 642132720Skan typedef typename iterator_traits<_Iterator>::iterator_category 643132720Skan iterator_category; 644132720Skan typedef typename iterator_traits<_Iterator>::value_type value_type; 645132720Skan typedef typename iterator_traits<_Iterator>::difference_type 646132720Skan difference_type; 647132720Skan typedef typename iterator_traits<_Iterator>::reference reference; 648132720Skan typedef typename iterator_traits<_Iterator>::pointer pointer; 64997403Sobrien 65097403Sobrien __normal_iterator() : _M_current(_Iterator()) { } 65197403Sobrien 652132720Skan explicit 65397403Sobrien __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 65497403Sobrien 65597403Sobrien // Allow iterator to const_iterator conversion 65697403Sobrien template<typename _Iter> 657169691Skan __normal_iterator(const __normal_iterator<_Iter, 658169691Skan typename __enable_if< 659169691Skan (std::__are_same<_Iter, typename _Container::pointer>::__value), 660169691Skan _Container>::__type>& __i) 661169691Skan : _M_current(__i.base()) { } 66297403Sobrien 66397403Sobrien // Forward iterator requirements 66497403Sobrien reference 665132720Skan operator*() const 666132720Skan { return *_M_current; } 667132720Skan 66897403Sobrien pointer 669132720Skan operator->() const 670132720Skan { return _M_current; } 671132720Skan 67297403Sobrien __normal_iterator& 673132720Skan operator++() 674132720Skan { 675132720Skan ++_M_current; 676132720Skan return *this; 677132720Skan } 678132720Skan 67997403Sobrien __normal_iterator 680132720Skan operator++(int) 681132720Skan { return __normal_iterator(_M_current++); } 682132720Skan 68397403Sobrien // Bidirectional iterator requirements 68497403Sobrien __normal_iterator& 685132720Skan operator--() 686132720Skan { 687132720Skan --_M_current; 688132720Skan return *this; 689132720Skan } 690132720Skan 69197403Sobrien __normal_iterator 692132720Skan operator--(int) 693132720Skan { return __normal_iterator(_M_current--); } 694132720Skan 69597403Sobrien // Random access iterator requirements 69697403Sobrien reference 69797403Sobrien operator[](const difference_type& __n) const 69897403Sobrien { return _M_current[__n]; } 699132720Skan 70097403Sobrien __normal_iterator& 70197403Sobrien operator+=(const difference_type& __n) 70297403Sobrien { _M_current += __n; return *this; } 70397403Sobrien 70497403Sobrien __normal_iterator 70597403Sobrien operator+(const difference_type& __n) const 70697403Sobrien { return __normal_iterator(_M_current + __n); } 707132720Skan 70897403Sobrien __normal_iterator& 70997403Sobrien operator-=(const difference_type& __n) 71097403Sobrien { _M_current -= __n; return *this; } 711132720Skan 71297403Sobrien __normal_iterator 71397403Sobrien operator-(const difference_type& __n) const 71497403Sobrien { return __normal_iterator(_M_current - __n); } 715132720Skan 716132720Skan const _Iterator& 717132720Skan base() const 718132720Skan { return _M_current; } 71997403Sobrien }; 72097403Sobrien 72197403Sobrien // Note: In what follows, the left- and right-hand-side iterators are 72297403Sobrien // allowed to vary in types (conceptually in cv-qualification) so that 72397403Sobrien // comparaison between cv-qualified and non-cv-qualified iterators be 72497403Sobrien // valid. However, the greedy and unfriendly operators in std::rel_ops 72597403Sobrien // will make overload resolution ambiguous (when in scope) if we don't 72697403Sobrien // provide overloads whose operands are of the same type. Can someone 72797403Sobrien // remind me what generic programming is about? -- Gaby 728132720Skan 72997403Sobrien // Forward iterator requirements 73097403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 731132720Skan inline bool 732132720Skan operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 733132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 734132720Skan { return __lhs.base() == __rhs.base(); } 73597403Sobrien 73697403Sobrien template<typename _Iterator, typename _Container> 737132720Skan inline bool 738132720Skan operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 739132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 740132720Skan { return __lhs.base() == __rhs.base(); } 74197403Sobrien 74297403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 743132720Skan inline bool 744132720Skan operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 745132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 746132720Skan { return __lhs.base() != __rhs.base(); } 74797403Sobrien 74897403Sobrien template<typename _Iterator, typename _Container> 749132720Skan inline bool 750132720Skan operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 751132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 752132720Skan { return __lhs.base() != __rhs.base(); } 75397403Sobrien 75497403Sobrien // Random access iterator requirements 75597403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 756132720Skan inline bool 757132720Skan operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 758132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 759132720Skan { return __lhs.base() < __rhs.base(); } 76097403Sobrien 76197403Sobrien template<typename _Iterator, typename _Container> 762132720Skan inline bool 763132720Skan operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 764132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 765132720Skan { return __lhs.base() < __rhs.base(); } 76697403Sobrien 76797403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 768132720Skan inline bool 769132720Skan operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 770132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 771132720Skan { return __lhs.base() > __rhs.base(); } 77297403Sobrien 77397403Sobrien template<typename _Iterator, typename _Container> 774132720Skan inline bool 775132720Skan operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 776132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 777132720Skan { return __lhs.base() > __rhs.base(); } 77897403Sobrien 77997403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 780132720Skan inline bool 781132720Skan operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 782132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 783132720Skan { return __lhs.base() <= __rhs.base(); } 78497403Sobrien 78597403Sobrien template<typename _Iterator, typename _Container> 786132720Skan inline bool 787132720Skan operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 788132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 789132720Skan { return __lhs.base() <= __rhs.base(); } 79097403Sobrien 79197403Sobrien template<typename _IteratorL, typename _IteratorR, typename _Container> 792132720Skan inline bool 793132720Skan operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 794132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 795132720Skan { return __lhs.base() >= __rhs.base(); } 79697403Sobrien 79797403Sobrien template<typename _Iterator, typename _Container> 798132720Skan inline bool 799132720Skan operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 800132720Skan const __normal_iterator<_Iterator, _Container>& __rhs) 801132720Skan { return __lhs.base() >= __rhs.base(); } 80297403Sobrien 803132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 804102782Skan // According to the resolution of DR179 not only the various comparison 805102782Skan // operators but also operator- must accept mixed iterator/const_iterator 806102782Skan // parameters. 807102782Skan template<typename _IteratorL, typename _IteratorR, typename _Container> 808132720Skan inline typename __normal_iterator<_IteratorL, _Container>::difference_type 809132720Skan operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 810132720Skan const __normal_iterator<_IteratorR, _Container>& __rhs) 811132720Skan { return __lhs.base() - __rhs.base(); } 812102782Skan 81397403Sobrien template<typename _Iterator, typename _Container> 814169691Skan inline typename __normal_iterator<_Iterator, _Container>::difference_type 815169691Skan operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 816169691Skan const __normal_iterator<_Iterator, _Container>& __rhs) 817169691Skan { return __lhs.base() - __rhs.base(); } 818169691Skan 819169691Skan template<typename _Iterator, typename _Container> 820132720Skan inline __normal_iterator<_Iterator, _Container> 821132720Skan operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 822132720Skan __n, const __normal_iterator<_Iterator, _Container>& __i) 823132720Skan { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 82497403Sobrien 825169691Skan_GLIBCXX_END_NAMESPACE 826169691Skan 827132720Skan#endif 828