File: counting_iterator.htm

package info (click to toggle)
boost 1.27.0-3
links: PTS
area: main
in suites: woody
size: 19,908 kB
ctags: 26,546
sloc: cpp: 122,225; ansic: 10,956; python: 4,412; sh: 855; yacc: 803; makefile: 257; perl: 165; lex: 90; csh: 6
file content (325 lines) | stat: -rw-r--r-- 10,871 bytes
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>Counting Iterator Adaptor Documentation</title>
</head>

<body bgcolor="#FFFFFF" text="#000000">

<img src="../../c++boost.gif" alt="c++boost.gif (8819 bytes)"
align="center" width="277" height="86">

<h1>Counting Iterator Adaptor</h1>

Defined in header
<a href="../../boost/counting_iterator.hpp">boost/counting_iterator.hpp</a>

<p>
How would you fill up a vector with the numbers zero
through one hundred using <a
href="http://www.sgi.com/tech/stl/copy.html"><tt>std::copy()</tt></a>? The
only iterator operation missing from builtin integer types is an
<tt>operator*()</tt> that returns the current
value of the integer.  The counting iterator adaptor adds this crucial piece of
functionality to whatever type it wraps. One can use the
counting iterator adaptor not only with integer types, but with any
type that is <tt>Incrementable</tt> (see type requirements <a href="#requirements">below</a>).  The
following <b>pseudo-code</b> shows the general idea of how the
counting iterator is implemented.
</p>

<pre>
  // inside a hypothetical counting_iterator class...
  typedef Incrementable value_type;
  value_type counting_iterator::operator*() const {
    return this->base; // no dereference!
  }
</pre>

All of the other operators of the counting iterator behave in the same
fashion as the <tt>Incrementable</tt> base type.

<h2>Synopsis</h2>

<pre>
namespace boost {
  template &lt;class Incrementable&gt;
  struct <a href="#counting_iterator_traits">counting_iterator_traits</a>;

  template &lt;class Incrementable&gt;
  struct <a href="#counting_iterator_generator">counting_iterator_generator</a>;

  template &lt;class Incrementable&gt;
  typename counting_iterator_generator&lt;Incrementable&gt;::type
  <a href="#make_counting_iterator">make_counting_iterator</a>(Incrementable x);
}
</pre>

<hr>

<h2><a name="counting_iterator_generator">The Counting Iterator Type
Generator</a></h2>

The class template <tt>counting_iterator_generator&lt;Incrementable&gt;</tt> is a <a href="../../more/generic_programming.html#type_generator">type generator</a> for counting iterators.

<pre>
template &lt;class Incrementable&gt;
class counting_iterator_generator
{
public:
    typedef <a href="./iterator_adaptors.htm#iterator_adaptor">iterator_adaptor</a>&lt;...&gt; type;
};
</pre>

<h3>Example</h3>

In this example we use the counting iterator generator to create a
counting iterator, and count from zero to four.

<pre>
#include &lt;boost/config.hpp&gt;
#include &lt;iostream&gt;
#include &lt;boost/counting_iterator.hpp&gt;

int main(int, char*[])
{
  // Example of using counting_iterator_generator
  std::cout &lt;&lt; "counting from 0 to 4:" &lt;&lt; std::endl;
  boost::counting_iterator_generator&lt;int&gt;::type first(0), last(4);
  std::copy(first, last, std::ostream_iterator&lt;int&gt;(std::cout, " "));
  std::cout &lt;&lt; std::endl;

  // to be continued...
</pre>
The output from this part is:
<pre>
counting from 0 to 4:
0 1 2 3 
</pre>

<h3>Template Parameters</h3>

<Table border>
<TR>
<TH>Parameter</TH><TH>Description</TH>
</TR>

<TR>
<TD><tt>Incrementable</tt></TD>
<TD>The type being wrapped by the adaptor.</TD>
</TR>

</Table>

<h3>Model of</h3>

If the <tt>Incrementable</tt> type has all of the functionality of a
<a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random
Access Iterator</a> except the <tt>operator*()</tt>, then the counting
iterator will be a model of <a
href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random
Access Iterator</a>. If the <tt>Incrementable</tt> type has less
functionality, then the counting iterator will have correspondingly
less functionality.

<h3><a name="requirements">Type Requirements</a></h3>

The <tt>Incrementable</tt> type must be <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
Constructible</a>, <a href="./CopyConstructible.html">Copy
Constructible</a>, and <a href="./Assignable.html">Assignable</a>.
Also, the <tt>Incrementable</tt> type must provide access to an
associated <tt>difference_type</tt> and <tt>iterator_category</tt>
through the <a
href="#counting_iterator_traits"><tt>counting_iterator_traits</tt></a>
class.

<p>
Furthermore, if you wish to create a counting iterator that is a <a
href="http://www.sgi.com/tech/stl/ForwardIterator.html"> Forward
Iterator</a>, then the following expressions must be valid:
<pre>
Incrementable i, j;
++i         // pre-increment
i == j      // operator equal
</pre>
If you wish to create a counting iterator that is a <a
href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">
Bidirectional Iterator</a>, then pre-decrement is also required:
<pre>
--i
</pre>
If you wish to create a counting iterator that is a <a
href="http://www.sgi.com/tech/stl/RandomAccessIterator.html"> Random
Access Iterator</a>, then these additional expressions are also required:
<pre>
<a href="#counting_iterator_traits">counting_iterator_traits</a>&lt;Incrementable&gt;::difference_type n;
i += n
n = i - j
i < j
</pre>



<h3>Members</h3>

The counting iterator type implements the member functions and
operators required of the <a
href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random
Access Iterator</a> concept. In addition it has the following
constructor:

<pre>
counting_iterator_generator::type(const Incrementable&amp; i)
</pre>

<p>
<hr>
<p>


<h2><a name="make_counting_iterator">The Counting Iterator Object Generator</a></h2>

<pre>
template &lt;class Incrementable&gt;
typename counting_iterator_generator&lt;Incrementable&gt;::type
make_counting_iterator(Incrementable base);
</pre>

An <a href="../../more/generic_programming.html#object_generator">object
generator</a> function that provides a convenient way to create counting
iterators.<p>



<h3>Example</h3>

In this example we count from negative five to positive five, this
time using the <tt>make_counting_iterator()</tt> function to save some
typing.

<pre>
  // continuing from previous example...

  std::cout &lt;&lt; "counting from -5 to 4:" &lt;&lt; std::endl;
  std::copy(boost::make_counting_iterator(-5),
	    boost::make_counting_iterator(5),
	    std::ostream_iterator&lt;int&gt;(std::cout, " "));
  std::cout &lt;&lt; std::endl;

  // to be continued...
</pre>
The output from this part is:
<pre>
counting from -5 to 4:
-5 -4 -3 -2 -1 0 1 2 3 4 
</pre>

In the next example we create an array of numbers, and then create a
second array of pointers, where each pointer is the address of a
number in the first array. The counting iterator makes it easy to do
this since dereferencing a counting iterator that is wrapping an
iterator over the array of numbers just returns a pointer to the
current location in the array. We then use the <a
href="./indirect_iterator.htm">indirect iterator adaptor</a> to print
out the number in the array by accessing the numbers through the array
of pointers.

<pre>
  // continuing from previous example...

  const int N = 7;
  std::vector&lt;int&gt; numbers;
  // Fill "numbers" array with [0,N)
  std::copy(boost::make_counting_iterator(0), boost::make_counting_iterator(N),
	    std::back_inserter(numbers));

  std::vector&lt;std::vector&lt;int&gt;::iterator&gt; pointers;

  // Use counting iterator to fill in the array of pointers.
  std::copy(boost::make_counting_iterator(numbers.begin()),
	    boost::make_counting_iterator(numbers.end()),
	    std::back_inserter(pointers));

  // Use indirect iterator to print out numbers by accessing
  // them through the array of pointers.
  std::cout &lt;&lt; "indirectly printing out the numbers from 0 to " 
	    &lt;&lt; N &lt;&lt; std::endl;
  std::copy(boost::make_indirect_iterator(pointers.begin()),
	    boost::make_indirect_iterator(pointers.end()),
	    std::ostream_iterator&lt;int&gt;(std::cout, " "));
  std::cout &lt;&lt; std::endl;
</pre>
The output is:
<pre>
indirectly printing out the numbers from 0 to 7
0 1 2 3 4 5 6 
</pre>

<hr>

<h2><a name="counting_iterator_traits">Counting Iterator Traits</a></h2>

The counting iterator adaptor needs to determine the appropriate
<tt>difference_type</tt> and <tt>iterator_category</tt> to use based on the
<tt>Incrementable</tt> type supplied by the user.  The
<tt>counting_iterator_traits</tt> class provides these types.  If the
<tt>Incrementable</tt> type is an integral type or an iterator, these types
will be correctly deduced by the <tt>counting_iterator_traits</tt> provided by
the library. Otherwise, the user must specialize
<tt>counting_iterator_traits</tt> for her type or add nested typedefs to
her type to fulfill the needs of
<a href="http://www.sgi.com/tech/stl/iterator_traits.html">
<tt>std::iterator_traits</tt></a>.

<p>The following pseudocode describes how the <tt>counting_iterator_traits</tt> are determined:

<pre>
template &lt;class Incrementable&gt;
struct counting_iterator_traits
{
  if (numeric_limits&lt;Incrementable&gt::is_specialized) {
    if (!numeric_limits&lt;Incrementable&gt::is_integer)
       COMPILE_TIME_ERROR;

    if (!numeric_limits&lt;Incrementable&gt::is_bounded
        &amp;&amp; numeric_limits&lt;Incrementable&gt;::is_signed) {
        typedef Incrementable difference_type;
    }
    else if (numeric_limits&lt;Incrementable&gt::is_integral) {
        typedef <i>next-larger-signed-type-or-intmax_t</i> difference_type;
    }
    typedef std::random_access_iterator_tag iterator_category;   
  } else {
    typedef std::iterator_traits&lt;Incrementable&gt;::difference_type difference_type;
    typedef std::iterator_traits&lt;Incrementable&gt;::iterator_category iterator_category;
  }
};
</pre>

<p>The italicized sections above are implementation details, but it is important
to know that the <tt>difference_type</tt> for integral types is selected so that
it can always represent the difference between two values if such a built-in
integer exists. On platforms with a working <tt>std::numeric_limits</tt>
implementation, the <tt>difference_type</tt> for any variable-length signed
integer type <tt>T</tt> is <tt>T</tt> itself.

<hr>
<p>Revised <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->19 Aug 2001<!--webbot bot="Timestamp" endspan i-checksum="14767" --></p>
<p> Copyright Jeremy Siek 2000. Permission to copy, use,
modify, sell and distribute this document is granted provided this copyright
notice appears in all copies. This document is provided &quot;as is&quot;
without express or implied warranty, and with no claim as to its suitability for
any purpose.</p>

</body>

</html>
<!--  LocalWords:  html charset alt gif hpp incrementable const namespace htm
 -->
<!--  LocalWords:  struct  typename iostream int Siek CopyConstructible pre
 -->