mirror of
https://github.com/boostorg/utility.git
synced 2025-10-12 08:35:21 +02:00
Compare commits
2 Commits
svn-branch
...
svn-branch
| Author | SHA1 | Date | |
|---|---|---|---|
|
e608036e99 | ||
|
91c135c0af |
@@ -9,6 +9,7 @@
|
|||||||
// See http://www.boost.org for most recent version including documentation.
|
// See http://www.boost.org for most recent version including documentation.
|
||||||
|
|
||||||
// Revision History
|
// Revision History
|
||||||
|
// 04 Mar 01 Workaround for Borland (Dave Abrahams)
|
||||||
// 19 Feb 01 Take adavantage of improved iterator_traits to do more tests
|
// 19 Feb 01 Take adavantage of improved iterator_traits to do more tests
|
||||||
// on MSVC. Hack around an MSVC-with-STLport internal compiler
|
// on MSVC. Hack around an MSVC-with-STLport internal compiler
|
||||||
// error. (David Abrahams)
|
// error. (David Abrahams)
|
||||||
@@ -384,8 +385,13 @@ main()
|
|||||||
#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
||||||
, dummyT
|
, dummyT
|
||||||
#endif
|
#endif
|
||||||
>::type filter_iter;
|
> filter_iter_gen;
|
||||||
|
|
||||||
|
#ifndef __BORLANDC__
|
||||||
|
typedef filter_iter_gen::type filter_iter;
|
||||||
|
#else
|
||||||
|
# define filter_iter filter_iter_gen::type // Borland has a problem with the above
|
||||||
|
#endif
|
||||||
filter_iter i(array, filter_iter::policies_type(one_or_four(), array + N));
|
filter_iter i(array, filter_iter::policies_type(one_or_four(), array + N));
|
||||||
boost::forward_iterator_test(i, dummyT(1), dummyT(4));
|
boost::forward_iterator_test(i, dummyT(1), dummyT(4));
|
||||||
|
|
||||||
|
|||||||
331
reverse_iterator.htm
Normal file
331
reverse_iterator.htm
Normal file
@@ -0,0 +1,331 @@
|
|||||||
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
|
||||||
|
|
||||||
|
<html>
|
||||||
|
<head>
|
||||||
|
<meta name="generator" content="HTML Tidy, see www.w3.org">
|
||||||
|
<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>Reverse 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>Reverse Iterator Adaptor</h1>
|
||||||
|
Defined in header <a href=
|
||||||
|
"../../boost/iterator_adaptors.hpp">boost/iterator_adaptors.hpp</a>
|
||||||
|
|
||||||
|
<p>The reverse iterator adaptor flips the direction of a base iterator's
|
||||||
|
motion. Invoking <tt>operator++()</tt> moves the base iterator backward and
|
||||||
|
invoking <tt>operator--()</tt> moves the base iterator forward. The Boost
|
||||||
|
reverse iterator adaptor is better to use than the
|
||||||
|
<tt>std::reverse_iterator</tt> class in situations where pairs of
|
||||||
|
mutable/constant iterators are needed (e.g., in containers) because
|
||||||
|
comparisons and conversions between the mutable and const versions are
|
||||||
|
implemented correctly.
|
||||||
|
|
||||||
|
<h2>Synopsis</h2>
|
||||||
|
<pre>
|
||||||
|
namespace boost {
|
||||||
|
template <class <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>,
|
||||||
|
class Value, class Reference, class Pointer, class Category, class Distance>
|
||||||
|
struct reverse_iterator_generator;
|
||||||
|
|
||||||
|
template <class <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>>
|
||||||
|
typename reverse_iterator_generator<BidirectionalIterator>::type
|
||||||
|
make_reverse_iterator(BidirectionalIterator base)
|
||||||
|
}
|
||||||
|
</pre>
|
||||||
|
<hr>
|
||||||
|
|
||||||
|
<h2><a name="reverse_iterator_generator">The Reverse Iterator Type
|
||||||
|
Generator</a></h2>
|
||||||
|
The <tt>reverse_iterator_generator</tt> template is a <a href=
|
||||||
|
"../../more/generic_programming.html#type_generator">generator</a> of
|
||||||
|
reverse iterator types. The main template parameter for this class is the
|
||||||
|
base <tt>BidirectionalIterator</tt> type that is being adapted. In most
|
||||||
|
cases the associated types of the base iterator can be deduced using
|
||||||
|
<tt>std::iterator_traits</tt>, but in some situations the user may want to
|
||||||
|
override these types, so there are also template parameters for the base
|
||||||
|
iterator's associated types.
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
template <class <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>,
|
||||||
|
class Value, class Reference, class Pointer, class Category, class Distance>
|
||||||
|
class reverse_iterator_generator
|
||||||
|
{
|
||||||
|
public:
|
||||||
|
typedef <tt><a href=
|
||||||
|
"./iterator_adaptors.htm#iterator_adaptor">iterator_adaptor</a><...></tt> type; // the resulting reverse iterator type
|
||||||
|
};
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
|
||||||
|
<h3>Example</h3>
|
||||||
|
In this example we sort a sequence of letters and then output the sequence
|
||||||
|
in descending order using reverse iterators.
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
#include <boost/config.hpp>
|
||||||
|
#include <iostream>
|
||||||
|
#include <algorithm>
|
||||||
|
#include <boost/iterator_adaptors.hpp>
|
||||||
|
|
||||||
|
int main(int, char*[])
|
||||||
|
{
|
||||||
|
char letters[] = "hello world!";
|
||||||
|
const int N = sizeof(letters)/sizeof(char) - 1;
|
||||||
|
std::cout << "original sequence of letters:\t"
|
||||||
|
<< letters << std::endl;
|
||||||
|
|
||||||
|
std::sort(letters, letters + N);
|
||||||
|
|
||||||
|
// Use reverse_iterator_generator to print a sequence
|
||||||
|
// of letters in reverse order.
|
||||||
|
|
||||||
|
boost::reverse_iterator_generator<char*>::type
|
||||||
|
reverse_letters_first(letters + N),
|
||||||
|
reverse_letters_last(letters);
|
||||||
|
|
||||||
|
std::cout << "letters in descending order:\t";
|
||||||
|
std::copy(reverse_letters_first, reverse_letters_last,
|
||||||
|
std::ostream_iterator<char>(std::cout));
|
||||||
|
std::cout << std::endl;
|
||||||
|
|
||||||
|
// to be continued...
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
The output is:
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
original sequence of letters: hello world!
|
||||||
|
letters in descending order: wroolllhed!
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
|
||||||
|
<h3>Template Parameters</h3>
|
||||||
|
|
||||||
|
<table border>
|
||||||
|
<tr>
|
||||||
|
<th>Parameter
|
||||||
|
|
||||||
|
<th>Description
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt><a href=
|
||||||
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a></tt>
|
||||||
|
|
||||||
|
|
||||||
|
<td>The iterator type being wrapped.
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt>Value</tt>
|
||||||
|
|
||||||
|
<td>The value-type of the base iterator and the resulting reverse
|
||||||
|
iterator.<br>
|
||||||
|
<b>Default:</b><tt>std::iterator_traits<BidirectionalIterator>::value_type</tt>
|
||||||
|
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt>Reference</tt>
|
||||||
|
|
||||||
|
<td>The <tt>reference</tt> type of the resulting iterator, and in
|
||||||
|
particular, the result type of <tt>operator*()</tt>.<br>
|
||||||
|
<b>Default:</b> If <tt>Value</tt> is supplied, <tt>Value&</tt> is
|
||||||
|
used. Otherwise
|
||||||
|
<tt>std::iterator_traits<BidirectionalIterator>::reference</tt>
|
||||||
|
is used.
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt>Pointer</tt>
|
||||||
|
|
||||||
|
<td>The <tt>pointer</tt> type of the resulting iterator, and in
|
||||||
|
particular, the result type of <tt>operator->()</tt>.<br>
|
||||||
|
<b>Default:</b> If <tt>Value</tt> was supplied, then <tt>Value*</tt>,
|
||||||
|
otherwise
|
||||||
|
<tt>std::iterator_traits<BidirectionalIterator>::pointer</tt>.
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt>Category</tt>
|
||||||
|
|
||||||
|
<td>The <tt>iterator_category</tt> type for the resulting iterator.<br>
|
||||||
|
<b>Default:</b>
|
||||||
|
<tt>std::iterator_traits<BidirectionalIterator>::iterator_category</tt>
|
||||||
|
|
||||||
|
|
||||||
|
<tr>
|
||||||
|
<td><tt>Distance</tt>
|
||||||
|
|
||||||
|
<td>The <tt>difference_type</tt> for the resulting iterator.<br>
|
||||||
|
<b>Default:</b>
|
||||||
|
<tt>std::iterator_traits<BidirectionalIterator&gt::difference_type</tt>
|
||||||
|
|
||||||
|
</table>
|
||||||
|
|
||||||
|
<h3>Concept Model</h3>
|
||||||
|
The indirect iterator will model whichever <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/Iterators.html">standard iterator concept
|
||||||
|
category</a> is modeled by the base iterator. Thus, if the base iterator is
|
||||||
|
a model of <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access
|
||||||
|
Iterator</a> then so is the resulting indirect iterator. If the base
|
||||||
|
iterator models a more restrictive concept, the resulting indirect iterator
|
||||||
|
will model the same concept. The base iterator must be at least a <a href=
|
||||||
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">Bidirectional
|
||||||
|
Iterator</a>
|
||||||
|
|
||||||
|
<h3>Members</h3>
|
||||||
|
The reverse 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:
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
reverse_iterator_generator::type(const BidirectionalIterator& it)
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
|
||||||
|
|
||||||
|
<br>
|
||||||
|
<br>
|
||||||
|
|
||||||
|
<hr>
|
||||||
|
|
||||||
|
<p>
|
||||||
|
|
||||||
|
<h2><a name="make_reverse_iterator">The Reverse Iterator Object
|
||||||
|
Generator</a></h2>
|
||||||
|
The <tt>make_reverse_iterator()</tt> function provides a more convenient
|
||||||
|
way to create reverse iterator objects. The function saves the user the
|
||||||
|
trouble of explicitly writing out the iterator types.
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
template <class BidirectionalIterator>
|
||||||
|
typename reverse_iterator_generator<BidirectionalIterator>::type
|
||||||
|
make_reverse_iterator(BidirectionalIterator base);
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
|
||||||
|
<h3>Example</h3>
|
||||||
|
In this part of the example we use <tt>make_reverse_iterator()</tt> to
|
||||||
|
print the sequence of letters in reverse-reverse order, which is the
|
||||||
|
original order.
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
// continuing from the previous example...
|
||||||
|
|
||||||
|
std::cout << "letters in ascending order:\t";
|
||||||
|
std::copy(boost::make_reverse_iterator(reverse_letters_last),
|
||||||
|
boost::make_reverse_iterator(reverse_letters_first),
|
||||||
|
std::ostream_iterator<char>(std::cout));
|
||||||
|
std::cout << std::endl;
|
||||||
|
|
||||||
|
return 0;
|
||||||
|
}
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
The output is:
|
||||||
|
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
letters in ascending order: !dehllloorw
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
<hr>
|
||||||
|
|
||||||
|
<h2><a name="interactions">Constant/Mutable Iterator Interactions</a></h2>
|
||||||
|
|
||||||
|
<p>One failing of the standard <tt><a
|
||||||
|
href="http://www.sgi.com/tech/stl/ReverseIterator.html">reverse_iterator</a></tt>
|
||||||
|
adaptor is that it doesn't properly support interactions between adapted
|
||||||
|
<tt>const</tt> and non-<tt>const</tt> iterators. For example:
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
#include <vector>
|
||||||
|
|
||||||
|
template <class T> void convert(T x) {}
|
||||||
|
|
||||||
|
// Test interactions of a matched pair of random access iterators
|
||||||
|
template <class Iterator, class ConstIterator>
|
||||||
|
void test_interactions(Iterator i, ConstIterator ci)
|
||||||
|
{
|
||||||
|
bool eq = i == ci; // comparisons
|
||||||
|
bool ne = i != ci;
|
||||||
|
bool lt = i < ci;
|
||||||
|
bool le = i <= ci;
|
||||||
|
bool gt = i > ci;
|
||||||
|
bool ge = i >= ci;
|
||||||
|
std::size_t distance = i - ci; // difference
|
||||||
|
ci = i; // assignment
|
||||||
|
ConstIterator ci2(i); // construction
|
||||||
|
convert<ConstIterator>(i); // implicit conversion
|
||||||
|
}
|
||||||
|
|
||||||
|
void f()
|
||||||
|
{
|
||||||
|
typedef std::vector<int> vec;
|
||||||
|
vec v;
|
||||||
|
const vec& cv;
|
||||||
|
|
||||||
|
test_interactions(v.begin(), cv.begin()); // <font color="#007F00">OK</font>
|
||||||
|
test_interactions(v.rbegin(), cv.rbegin()); // <font color="#FF0000">ERRORS ON EVERY TEST!!</font>
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
Reverse iterators created with <tt>boost::reverse_iterator_generator</tt> don't have this problem, though:
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
typedef boost::reverse_iterator_generator<vec::iterator>::type ri;
|
||||||
|
typedef boost::reverse_iterator_generator<vec::const_iterator>::type cri;
|
||||||
|
test_interactions(ri(v.begin()), cri(cv.begin())); // <font color="#007F00">OK!!</font>
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
Or, more simply,
|
||||||
|
<blockquote>
|
||||||
|
<pre>
|
||||||
|
test_interactions(
|
||||||
|
boost::make_reverse_iterator(v.begin()),
|
||||||
|
boost::make_reverse_iterator(cv.begin())); // <font color="#007F00">OK!!</font>
|
||||||
|
}
|
||||||
|
</pre>
|
||||||
|
</blockquote>
|
||||||
|
|
||||||
|
<p>If you are wondering why there is no
|
||||||
|
<tt>reverse_iterator_pair_generator</tt> in the manner of <tt><a
|
||||||
|
href="projection_iterator.htm#projection_iterator_pair_generator">projection_iterator_pair_generator</a></tt>,
|
||||||
|
the answer is simple: we tried it, but found that in practice it took
|
||||||
|
<i>more</i> typing to use <tt>reverse_iterator_pair_generator</tt> than to
|
||||||
|
simply use <tt>reverse_iterator_generator</tt> twice!<br><br>
|
||||||
|
|
||||||
|
<hr>
|
||||||
|
|
||||||
|
|
||||||
|
<p>Revised
|
||||||
|
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->26 Feb 2001<!--webbot bot="Timestamp" endspan i-checksum="14386" -->
|
||||||
|
|
||||||
|
|
||||||
|
<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 "as is" without express or
|
||||||
|
implied warranty, and with no claim as to its suitability for any purpose.
|
||||||
|
<!-- LocalWords: html charset alt gif hpp BidirectionalIterator const namespace struct
|
||||||
|
-->
|
||||||
|
|
||||||
|
<!-- LocalWords: ConstPointer ConstReference typename iostream int abcdefg
|
||||||
|
-->
|
||||||
|
<!-- LocalWords: sizeof PairGen pre Siek wroolllhed dehllloorw
|
||||||
|
-->
|
||||||
|
</body>
|
||||||
|
</html>
|
||||||
|
|
||||||
Reference in New Issue
Block a user