stl_iterator_base_funcs.h revision 169692
111499Sjkh// Functions used by iterators -*- C++ -*- 211499Sjkh 311499Sjkh// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 411499Sjkh// Free Software Foundation, Inc. 511499Sjkh// 611499Sjkh// This file is part of the GNU ISO C++ Library. This library is free 750479Speter// software; you can redistribute it and/or modify it under the 811499Sjkh// terms of the GNU General Public License as published by the 911499Sjkh// Free Software Foundation; either version 2, or (at your option) 1011499Sjkh// any later version. 1111499Sjkh 1211499Sjkh// This library is distributed in the hope that it will be useful, 1311499Sjkh// but WITHOUT ANY WARRANTY; without even the implied warranty of 1411499Sjkh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1511499Sjkh// GNU General Public License for more details. 1611499Sjkh 1711499Sjkh// You should have received a copy of the GNU General Public License along 1811499Sjkh// with this library; see the file COPYING. If not, write to the Free 1911499Sjkh// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2011499Sjkh// USA. 2111499Sjkh 2211499Sjkh// As a special exception, you may use this file as part of a free software 2311499Sjkh// library without restriction. Specifically, if other files instantiate 2411499Sjkh// templates or use macros or inline functions from this file, or you compile 2511499Sjkh// this file and link it with other files to produce an executable, this 2611499Sjkh// file does not by itself cause the resulting executable to be covered by 2711499Sjkh// the GNU General Public License. This exception does not however 2811499Sjkh// invalidate any other reasons why the executable file might be covered by 2911499Sjkh// the GNU General Public License. 3011499Sjkh 3111499Sjkh/* 3211499Sjkh * 3311499Sjkh * Copyright (c) 1994 3411499Sjkh * Hewlett-Packard Company 3511499Sjkh * 3611499Sjkh * Permission to use, copy, modify, distribute and sell this software 3721243Sjkh * and its documentation for any purpose is hereby granted without fee, 3811499Sjkh * provided that the above copyright notice appear in all copies and 3915883Sjkh * that both that copyright notice and this permission notice appear 4011499Sjkh * in supporting documentation. Hewlett-Packard Company makes no 4111499Sjkh * representations about the suitability of this software for any 4211499Sjkh * purpose. It is provided "as is" without express or implied warranty. 4311499Sjkh * 4450780Sjkh * 4524106Sjkh * Copyright (c) 1996-1998 4624106Sjkh * Silicon Graphics Computer Systems, Inc. 4724106Sjkh * 4824106Sjkh * Permission to use, copy, modify, distribute and sell this software 4924106Sjkh * and its documentation for any purpose is hereby granted without fee, 5024106Sjkh * provided that the above copyright notice appear in all copies and 5124106Sjkh * that both that copyright notice and this permission notice appear 5247055Sjkh * in supporting documentation. Silicon Graphics makes no 5347055Sjkh * representations about the suitability of this software for any 5447055Sjkh * purpose. It is provided "as is" without express or implied warranty. 5511650Sjkh */ 5611650Sjkh 5711650Sjkh/** @file stl_iterator_base_funcs.h 5889775Ssteve * This is an internal header file, included by other library headers. 5947055Sjkh * You should not attempt to use it directly. 6047055Sjkh * 6111650Sjkh * This file contains all of the general iterator-related utility 6215242Sjkh * functions, such as distance() and advance(). 6350780Sjkh */ 6479065Sdd 6550780Sjkh#ifndef _ITERATOR_BASE_FUNCS_H 6650780Sjkh#define _ITERATOR_BASE_FUNCS_H 1 6747055Sjkh 6847055Sjkh#pragma GCC system_header 6947055Sjkh#include <bits/concept_check.h> 7050780Sjkh 7189775Ssteve_GLIBCXX_BEGIN_NAMESPACE(std) 7247055Sjkh 7347221Sjkh template<typename _InputIterator> 7447055Sjkh inline typename iterator_traits<_InputIterator>::difference_type 7547055Sjkh __distance(_InputIterator __first, _InputIterator __last, 7654587Sjkh input_iterator_tag) 7747055Sjkh { 7811650Sjkh // concept requirements 7911650Sjkh __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 8026613Sjkh 8126613Sjkh typename iterator_traits<_InputIterator>::difference_type __n = 0; 8226613Sjkh while (__first != __last) 8326613Sjkh { 8426613Sjkh ++__first; 8526613Sjkh ++__n; 8629539Spst } 8726613Sjkh return __n; 8826613Sjkh } 8926613Sjkh 9026613Sjkh template<typename _RandomAccessIterator> 9126613Sjkh inline typename iterator_traits<_RandomAccessIterator>::difference_type 9226613Sjkh __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 9326613Sjkh random_access_iterator_tag) 9426613Sjkh { 9515788Sjkh // concept requirements 9615788Sjkh __glibcxx_function_requires(_RandomAccessIteratorConcept< 9715788Sjkh _RandomAccessIterator>) 9816688Sjkh return __last - __first; 9916688Sjkh } 10015788Sjkh 10116688Sjkh /** 10216688Sjkh * @brief A generalization of pointer arithmetic. 10316688Sjkh * @param first An input iterator. 10416688Sjkh * @param last An input iterator. 10516688Sjkh * @return The distance between them. 10616688Sjkh * 10716688Sjkh * Returns @c n such that first + n == last. This requires that @p last 10822102Sjkh * must be reachable from @p first. Note that @c n may be negative. 10922102Sjkh * 11015788Sjkh * For random access iterators, this uses their @c + and @c - operations 11115788Sjkh * and are constant time. For other %iterator classes they are linear time. 11215788Sjkh */ 11311499Sjkh template<typename _InputIterator> 11411499Sjkh inline typename iterator_traits<_InputIterator>::difference_type 11514738Sjkh distance(_InputIterator __first, _InputIterator __last) 11611499Sjkh { 11795825Sobrien // concept requirements -- taken care of in __distance 11895825Sobrien return std::__distance(__first, __last, 11995825Sobrien std::__iterator_category(__first)); 12020315Sjkh } 12111499Sjkh 12295825Sobrien template<typename _InputIterator, typename _Distance> 12395825Sobrien inline void 12419385Sjkh __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 12519385Sjkh { 12619385Sjkh // concept requirements 12719385Sjkh __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 12879065Sdd while (__n--) 12911672Sjkh ++__i; 13015242Sjkh } 13111553Sjkh 13211499Sjkh template<typename _BidirectionalIterator, typename _Distance> 13347179Sjkh inline void 13476521Solgeni __advance(_BidirectionalIterator& __i, _Distance __n, 13576521Solgeni bidirectional_iterator_tag) 13647179Sjkh { 13776521Solgeni // concept requirements 13847179Sjkh __glibcxx_function_requires(_BidirectionalIteratorConcept< 13914738Sjkh _BidirectionalIterator>) 14054587Sjkh if (__n > 0) 14112129Sjkh while (__n--) 14230424Sjkh ++__i; 14314670Sjkh else 14493595Sobrien while (__n++) 14512129Sjkh --__i; 14630424Sjkh } 14730424Sjkh 14812129Sjkh template<typename _RandomAccessIterator, typename _Distance> 14947179Sjkh inline void 15047179Sjkh __advance(_RandomAccessIterator& __i, _Distance __n, 15195825Sobrien random_access_iterator_tag) 15247179Sjkh { 15395825Sobrien // concept requirements 15447179Sjkh __glibcxx_function_requires(_RandomAccessIteratorConcept< 15516823Sjkh _RandomAccessIterator>) 15695825Sobrien __i += __n; 15747041Sjkh } 15847047Sjkh 15995825Sobrien /** 16095825Sobrien * @brief A generalization of pointer arithmetic. 16195825Sobrien * @param i An input iterator. 16295825Sobrien * @param n The "delta" by which to change @p i. 16395825Sobrien * @return Nothing. 16495825Sobrien * 16520315Sjkh * This increments @p i by @p n. For bidirectional and random access 16624106Sjkh * iterators, @p n may be negative, in which case @p i is decremented. 16714670Sjkh * 16854722Sjkh * For random access iterators, this uses their @c + and @c - operations 16912184Sjkh * and are constant time. For other %iterator classes they are linear time. 17047221Sjkh */ 17124106Sjkh template<typename _InputIterator, typename _Distance> 17247221Sjkh inline void 17354767Sjkh advance(_InputIterator& __i, _Distance __n) 17414738Sjkh { 17514670Sjkh // concept requirements -- taken care of in __advance 17614670Sjkh typename iterator_traits<_InputIterator>::difference_type __d = __n; 17714670Sjkh std::__advance(__i, __d, std::__iterator_category(__i)); 17814670Sjkh } 17994051Sobrien 18014670Sjkh_GLIBCXX_END_NAMESPACE 18168552Sjkh 18268552Sjkh#endif /* _ITERATOR_BASE_FUNCS_H */ 18368552Sjkh