<!--
    Licensed to the Apache Software  Foundation (ASF) under one or more
    contributor  license agreements.  See  the NOTICE  file distributed
    with  this  work  for  additional information  regarding  copyright
    ownership.   The ASF  licenses this  file to  you under  the Apache
    License, Version  2.0 (the  License); you may  not use  this file
    except in  compliance with the License.   You may obtain  a copy of
    the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the  License is distributed on an  "AS IS" BASIS,
    WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
    implied.   See  the License  for  the  specific language  governing
    permissions and limitations under the License.

    Copyright 1999-2007 Rogue Wave Software, Inc.
-->

<HTML>
<HEAD>
<TITLE>Introduction to Iterators</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="2-2.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
<H2>2.1 Introduction to Iterators</H2>
<A NAME="idx11"><!></A>
<P>The concept of iterators is fundamental to using the container classes and the associated algorithms provided by the C++ Standard Library. An <I>iterator</I> is a pointer-like object used to cycle through all the elements stored in a container. Because different algorithms need to traverse containers in a variety of fashions, there are different forms of iterators. Each container class in the C++ Standard Library can generate an iterator with functionality appropriate to the storage technique used in implementing the container. It is the category of iterators required as arguments that chiefly distinguishes which algorithms in the C++ Standard Library can be used with which container classes. </P>
<A NAME="idx12"><!></A>
<P>Just as pointers can be used in a variety of ways in traditional programming, iterators can be used for a number of different purposes. An iterator can be used to denote a specific value, just as a pointer can be used to reference a specific memory location. A <I>pair</I> of iterators can be used to define a <I>range</I> or sequence of values held in a container, just as two pointers can be used to describe a contiguous region of memory. With iterators, however, the values being described may be only logically rather than physically in sequence because they are derived from the same container, and the second follows the first in the order in which the elements are maintained by the container.</P>
<A NAME="idx13"><!></A>
<P>Conventional pointers can sometimes be <I>null</I>, meaning they point at nothing. Iterators, as well, can fail to denote any specific value. Just as it is a logical error to dereference a null pointer, it is an error to dereference an iterator that is not denoting a value. </P>
<P>When two pointers that describe a region in memory are used in a C++ program, it is conventional that the ending pointer <I>not</I> be considered part of the region. For example, an array named <SAMP>x</SAMP> of length <SAMP>10</SAMP> is sometimes described as extending from <SAMP>x</SAMP> to <SAMP>x+10</SAMP>, even though the element at <SAMP>x+10</SAMP> is not part of the array. Instead, the pointer value <SAMP>x+10</SAMP> is the<I> past-the-end</I> value <I>after</I> the end of the range being described. Iterators are used similarly to describe a range. The second value is not considered part of the range being denoted. Instead, the second value is a <I>past-the-end</I> element describing the next value in sequence after the final value of the range. Sometimes, as with pointers to memory, this will be an actual value in the container. Other times it may be a special value, specifically constructed for the purpose. In either case, it is not proper to dereference an iterator that is being used to specify the end of a range. </P>
<A NAME="idx14"><!></A>
<P>Just as with conventional pointers, the fundamental operation used to modify an iterator is the increment operator, <SAMP>operator++()</SAMP>. When the increment operator is applied to an iterator that denotes the final value in a sequence, the iterator is changed to the past-the-end value. An iterator <SAMP>j</SAMP> is said to be <I>reachable</I> from an iterator <SAMP>i</SAMP> if, after a finite sequence of applications of the expression <SAMP>++i</SAMP>, the iterator <SAMP>i</SAMP> becomes equal to <SAMP>j</SAMP>.</P>
<A NAME="idx15"><!></A>
<P>Ranges can be used to describe the entire contents of a container by constructing an iterator to the initial element and a special <I>ending</I> iterator. Ranges can also be used to describe sub-sequences within a single container by employing two iterators to specific values. </P>
<BLOCKQUOTE><HR><B>
NOTE -- Whenever two iterators are used to describe a range, it is assumed that the second iterator is reachable from the first, but this is not verified. Errors can occur if this expectation is not satisfied.
</B><HR></BLOCKQUOTE>
<P>In the remainder of this chapter, we describe the different forms of iterators used by the C++ Standard Library, as well as various other iterator-related functions.</P>

<BR>
<HR>
<A HREF="2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="2-2.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
    _uacct = "UA-1775151-1";
    urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->

</BODY>
</HTML>