Re: [boost] [Boost] [iterator][utility] advance() and distance() for new iterator concepts (Was: [Boost-users] std::distance ignores random_access_traversal_tag)
David Abrahams wrote:
Sebastian Redl <sebastian.redl@getdesigned.at> writes:
(Dave: that might be a worthy addition to the iterator library: distance() and advance() for the new-style iterators. Like boost::TR1, the functions could just forward to implementations that are already updated.)
Patches (including docs and tests) welcomed.
Well, nearly a year after actually implementing the functions, I finally forced myself to write docs and tests. I made the functions part of the utility library, because it already contains the related next() and prior() functions. Tested on GCC-4.1.2 x86-64 (Gentoo Linux). The attached patch is against the current trunk. Sebastian Redl Index: boost/next_prior.hpp =================================================================== --- boost/next_prior.hpp (revision 39551) +++ boost/next_prior.hpp (working copy) @@ -8,11 +8,12 @@ // Revision History // 13 Dec 2003 Added next(x, n) and prior(x, n) (Daniel Walker) +// 26 Sep 2007 Made next(x, n) and prior(x, n) use Boost. (Sebastian Redl) #ifndef BOOST_NEXT_PRIOR_HPP_INCLUDED #define BOOST_NEXT_PRIOR_HPP_INCLUDED -#include <iterator> +#include <boost/utility/iterator.hpp> namespace boost { @@ -32,7 +33,7 @@ template <class T, class Distance> inline T next(T x, Distance n) { - std::advance(x, n); + boost::advance(x, n); return x; } @@ -42,7 +43,7 @@ template <class T, class Distance> inline T prior(T x, Distance n) { - std::advance(x, -n); + boost::advance(x, -n); return x; } Index: boost/utility/iterator.hpp =================================================================== --- boost/utility/iterator.hpp (revision 0) +++ boost/utility/iterator.hpp (revision 0) @@ -0,0 +1,40 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +#ifndef BOOST_UTILITY_ITERATOR_HPP_SR_H +#define BOOST_UTILITY_ITERATOR_HPP_SR_H + +#include <boost/iterator/iterator_categories.hpp> + +#include <boost/utility/detail/iterator_dispatch.hpp> + +namespace boost +{ + // A replacement for std::advance that uses the new iterator categories. + template <class IncrementableIterator, class Distance> + inline void advance(IncrementableIterator &i, Distance n) + { + typedef BOOST_DEDUCED_TYPENAME boost::iterator_traversal< + IncrementableIterator + >::type traversal; + detail::advance(traversal(), i, n); + } + + // A replacement for std::distance that uses the new iterator categories. + template <class SinglePassIterator> + inline BOOST_DEDUCED_TYPENAME std::iterator_traits< + SinglePassIterator>::difference_type + distance(SinglePassIterator first, + SinglePassIterator last) + { + typedef BOOST_DEDUCED_TYPENAME boost::iterator_traversal< + SinglePassIterator + >::type traversal; + return detail::distance(traversal(), first, last); + } +} + +#endif Index: boost/utility/detail/iterator_dispatch.hpp =================================================================== --- boost/utility/detail/iterator_dispatch.hpp (revision 0) +++ boost/utility/detail/iterator_dispatch.hpp (revision 0) @@ -0,0 +1,124 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +#ifndef BOOST_UTILITY_DETAIL_ITERATOR_DISPATCH_HPP_SR_H +#define BOOST_UTILITY_DETAIL_ITERATOR_DISPATCH_HPP_SR_H + +#include <boost/iterator/iterator_categories.hpp> +#include <boost/iterator/iterator_concepts.hpp> + +namespace boost +{ + namespace detail + { + // For incrementable, single-pass and forward traversable iterators: + // use the classic version, because that's the basic feature set anyway. + template <class IncrementableIterator, class Distance> + inline void advance(boost::incrementable_traversal_tag, + IncrementableIterator &i, Distance n) + { + boost::function_requires< + boost_concepts::IncrementableIterator< + IncrementableIterator + > + >(); + + while(n > 0) { + ++i; + --n; + } + } + + // Bi-directional iterators use this version. Negative distances are + // allowed. + template <class BidirectionalTraversalIterator, class Distance> + inline void advance(boost::bidirectional_traversal_tag, + BidirectionalTraversalIterator &i, Distance n) + { + boost::function_requires< + boost_concepts::BidirectionalTraversal< + BidirectionalTraversalIterator + > + >(); + + if(n > 0) { + while(n) { + ++i; + --n; + } + } else { + while(n) { + --i; + ++n; + } + } + } + + // Random-access traversal iterators get the shortcut. + template <class RandomAccessTraversalIterator, class Distance> + inline void advance(boost::random_access_traversal_tag, + RandomAccessTraversalIterator &i, Distance n) + { + boost::function_requires< + boost_concepts::RandomAccessTraversal< + RandomAccessTraversalIterator + > + >(); + + i += n; + } + + // Incrementable iterators cannot have their distance taken, since it is + // not possible to hold two valid iterators to different parts of a + // sequence; nor could they be compared. + + // This version is for single-pass, forward and bi-directional traversal + // iterators. The use cases for single-pass iterators are limited, but + // it can, for example, be used to determine the number of elements + // that can be extracted from an input stream iterator. + template <class SinglePassIterator> + inline BOOST_DEDUCED_TYPENAME std::iterator_traits< + SinglePassIterator>::difference_type + distance(boost::single_pass_traversal_tag, + SinglePassIterator first, + SinglePassIterator last) + { + boost::function_requires< + boost_concepts::SinglePassIterator< + SinglePassIterator + > + >(); + + BOOST_DEDUCED_TYPENAME std::iterator_traits< + SinglePassIterator>::difference_type dist = 0; + while(first != last) { + ++dist; + ++first; + } + return dist; + } + + + // Random-access traversal iterators get the shortcut. + template <class RandomAccessTraversalIterator> + inline BOOST_DEDUCED_TYPENAME std::iterator_traits< + RandomAccessTraversalIterator>::difference_type + distance(boost::random_access_traversal_tag, + RandomAccessTraversalIterator first, + RandomAccessTraversalIterator last) + { + boost::function_requires< + boost_concepts::RandomAccessTraversal< + RandomAccessTraversalIterator + > + >(); + + return last - first; + } + } +} + +#endif Index: boost/utility.hpp =================================================================== --- boost/utility.hpp (revision 39551) +++ boost/utility.hpp (working copy) @@ -12,6 +12,7 @@ #include <boost/utility/addressof.hpp> #include <boost/utility/base_from_member.hpp> #include <boost/utility/enable_if.hpp> +#include <boost/utility/iterator.hpp> #include <boost/checked_delete.hpp> #include <boost/next_prior.hpp> #include <boost/noncopyable.hpp> Index: libs/utility/utility.htm =================================================================== --- libs/utility/utility.htm (revision 39551) +++ libs/utility/utility.htm (working copy) @@ -17,6 +17,8 @@ Function templates <a href="#checked_delete">checked_delete() and checked_array_delete()</a></li> <li> + Function templates <a href="#functions_advance_distance">advance() and distance()</a></li> + <li> Function templates <a href="#functions_next_prior">next() and prior()</a></li> <li> Class <a href="#Class_noncopyable">noncopyable</a></li> @@ -30,6 +32,19 @@ checked_array_delete()</h2> <p>See <a href="checked_delete.html">separate documentation</a>.</p> <h2> + <a name="functions_advance_distance">Function</a> templates advance() and distance()</h2> + <p>The advance() and distance() functions provide the exact functionality of their standard library counterparts, but use the Boost.Iterators traversal category to decide on the correct implementation. This means, for example, that they work in constant time for vector<bool> iterators instead of linear time (provided that the iterator is correctly tagged).</p> + <blockquote> + <pre>template <class IncrementableIterator, class Distance> +void advance(IncrementableIterator &it, Distance n); + +template <class SinglePassIterator> +typename std::iterator_traits<SinglePassIterator>::difference_type +distance(SinglePassIterator first, SinglePassIterator last);</pre> + </blockquote> + <p>See the implementation of next() and prior() below to see a usage example.</p> + <p>You can include the header <boost/utility/iterator.hpp> directly to obtain these functions without the other utilities.</p> + <h2> <a name="functions_next_prior">Function</a> templates next() and prior()</h2> <p>Certain data types, such as the C++ Standard Library's forward and bidirectional iterators, do not provide addition and subtraction via operator+() or @@ -45,7 +60,7 @@ template <class T, class Distance> T next(T x, Distance n) { - std::advance(x, n); + boost::advance(x, n); return x; } @@ -55,7 +70,7 @@ template <class T, class Distance> T prior(T x, Distance n) { - std::advance(x, -n); + boost::advance(x, -n); return x; }</pre> </blockquote> Index: libs/utility/test/adv_ra_run.cpp =================================================================== --- libs/utility/test/adv_ra_run.cpp (revision 0) +++ libs/utility/test/adv_ra_run.cpp (revision 0) @@ -0,0 +1,26 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that advance() works for random access traversal iterators. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( advance_random_access ) +{ + mock_iterator<boost::random_access_traversal_tag> it; + boost::advance(it, 5); + boost::advance(it, -3); + BOOST_CHECK_EQUAL(*it, 2); + BOOST_CHECK_EQUAL(it.increment_calls(), 0); + BOOST_CHECK_EQUAL(it.decrement_calls(), 0); + BOOST_CHECK_EQUAL(it.advance_calls(), 2); +} Index: libs/utility/test/adv_forward_run.cpp =================================================================== --- libs/utility/test/adv_forward_run.cpp (revision 0) +++ libs/utility/test/adv_forward_run.cpp (revision 0) @@ -0,0 +1,26 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that advance() works for forward traversal iterators. +// Same implementation as for incrementable; this checks that non-exact matches +// get identified correctly. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( advance_forward ) +{ + mock_iterator<boost::forward_traversal_tag> it; + boost::advance(it, 5); + BOOST_CHECK_EQUAL(*it, 5); + BOOST_CHECK_EQUAL(it.increment_calls(), 5); + BOOST_CHECK_EQUAL(it.advance_calls(), 0); +} Index: libs/utility/test/adv_dist_hdr_compiles.cpp =================================================================== --- libs/utility/test/adv_dist_hdr_compiles.cpp (revision 0) +++ libs/utility/test/adv_dist_hdr_compiles.cpp (revision 0) @@ -0,0 +1,9 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Simple check to see if boost/utility/iterator.hpp even compiles on its own. + +#include <boost/utility/iterator.hpp> Index: libs/utility/test/adv_bidi_run.cpp =================================================================== --- libs/utility/test/adv_bidi_run.cpp (revision 0) +++ libs/utility/test/adv_bidi_run.cpp (revision 0) @@ -0,0 +1,26 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that advance() works for bidirectional traversal iterators. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( advance_bidirectional ) +{ + mock_iterator<boost::bidirectional_traversal_tag> it; + boost::advance(it, 5); + boost::advance(it, -3); + BOOST_CHECK_EQUAL(*it, 2); + BOOST_CHECK_EQUAL(it.increment_calls(), 5); + BOOST_CHECK_EQUAL(it.decrement_calls(), 3); + BOOST_CHECK_EQUAL(it.advance_calls(), 0); +} Index: libs/utility/test/dist_single_run.cpp =================================================================== --- libs/utility/test/dist_single_run.cpp (revision 0) +++ libs/utility/test/dist_single_run.cpp (revision 0) @@ -0,0 +1,23 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that distance() works for single pass traversal iterators. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( distance_single_pass ) +{ + mock_iterator<boost::single_pass_traversal_tag> it1, it2(5); + BOOST_CHECK_EQUAL(boost::distance(it1, it2), 5); + BOOST_CHECK_EQUAL(it1.increment_calls(), 5); + BOOST_CHECK_EQUAL(it1.distance_to_calls(), 0); +} Index: libs/utility/test/dist_ra_run.cpp =================================================================== --- libs/utility/test/dist_ra_run.cpp (revision 0) +++ libs/utility/test/dist_ra_run.cpp (revision 0) @@ -0,0 +1,23 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that distance() works for random access traversal iterators. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( distance_random_access ) +{ + mock_iterator<boost::random_access_traversal_tag> it1, it2(5); + BOOST_CHECK_EQUAL(boost::distance(it1, it2), 5); + BOOST_CHECK_EQUAL(it1.increment_calls(), 0); + BOOST_CHECK_EQUAL(it1.distance_to_calls(), 1); +} Index: libs/utility/test/adv_incr_run.cpp =================================================================== --- libs/utility/test/adv_incr_run.cpp (revision 0) +++ libs/utility/test/adv_incr_run.cpp (revision 0) @@ -0,0 +1,24 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that advance() works for incrementable traversal iterators. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( advance_incrementable ) +{ + mock_iterator<boost::incrementable_traversal_tag> it; + boost::advance(it, 5); + BOOST_CHECK_EQUAL(*it, 5); + BOOST_CHECK_EQUAL(it.increment_calls(), 5); + BOOST_CHECK_EQUAL(it.advance_calls(), 0); +} Index: libs/utility/test/dist_incr_fail.cpp =================================================================== --- libs/utility/test/dist_incr_fail.cpp (revision 0) +++ libs/utility/test/dist_incr_fail.cpp (revision 0) @@ -0,0 +1,17 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that distance() fails to compile for incrementable traversal iterators. + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +void distance_incrementable() +{ + mock_iterator<boost::incrementable_traversal_tag> it1, it2(5); + boost::distance(it1, it2); +} Index: libs/utility/test/mock_iterators.hpp =================================================================== --- libs/utility/test/mock_iterators.hpp (revision 0) +++ libs/utility/test/mock_iterators.hpp (revision 0) @@ -0,0 +1,72 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Implements a mock iterator template for checking iterator manipulations. + +#include <boost/iterator/iterator_facade.hpp> + +// Utility class. An iterator that globally counts calls to the core functions +// of all instances. +template <typename Traversal> +class mock_iterator + : public boost::iterator_facade< + mock_iterator<Traversal>, int, Traversal, + int, // Not a reference, to prevent merging into std:: categories. + int + > +{ +public: + mock_iterator() + : m_pos(0) + {} + mock_iterator(int pos) + : m_pos(pos) + {} + + int dereference_calls() const { return m_deref_count; } + int equal_calls() const { return m_equal_count; } + int increment_calls() const { return m_incr_count; } + int decrement_calls() const { return m_decr_count; } + int advance_calls() const { return m_advance_count; } + int distance_to_calls() const { return m_distance_count; } + +private: + friend class boost::iterator_core_access; + + int dereference() const { ++m_deref_count; return m_pos; } + bool equal(const mock_iterator &o) const { + ++m_equal_count; + return m_pos == o.m_pos; + } + void increment() { ++m_pos; ++m_incr_count; } + void decrement() { --m_pos; ++m_decr_count; } + void advance(int diff) { m_pos += diff; ++m_advance_count; } + int distance_to(const mock_iterator &o) const { + ++m_distance_count; + return o.m_pos - m_pos; + } + + int m_pos; + static int m_deref_count; + static int m_equal_count; + static int m_incr_count; + static int m_decr_count; + static int m_advance_count; + static int m_distance_count; +}; + +template <typename Traversal> +int mock_iterator<Traversal>::m_deref_count = 0; +template <typename Traversal> +int mock_iterator<Traversal>::m_equal_count = 0; +template <typename Traversal> +int mock_iterator<Traversal>::m_incr_count = 0; +template <typename Traversal> +int mock_iterator<Traversal>::m_decr_count = 0; +template <typename Traversal> +int mock_iterator<Traversal>::m_advance_count = 0; +template <typename Traversal> +int mock_iterator<Traversal>::m_distance_count = 0; Index: libs/utility/test/dist_forward_run.cpp =================================================================== --- libs/utility/test/dist_forward_run.cpp (revision 0) +++ libs/utility/test/dist_forward_run.cpp (revision 0) @@ -0,0 +1,25 @@ +// Copyright 2007 Sebastian Redl. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/utility/> for the library's home page. + +// Check that distance() works for forward traversal iterators. +// Same implementation as for single pass; this checks that non-exact matches +// get identified correctly. + +#define BOOST_TEST_MODULE Utility_Iterator +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#include <boost/utility/iterator.hpp> + +#include "mock_iterators.hpp" + +BOOST_AUTO_TEST_CASE( distance_forward ) +{ + mock_iterator<boost::forward_traversal_tag> it1, it2(5); + BOOST_CHECK_EQUAL(boost::distance(it1, it2), 5); + BOOST_CHECK_EQUAL(it1.increment_calls(), 5); + BOOST_CHECK_EQUAL(it1.distance_to_calls(), 0); +} Index: libs/utility/test/Jamfile.v2 =================================================================== --- libs/utility/test/Jamfile.v2 (revision 39551) +++ libs/utility/test/Jamfile.v2 (working copy) @@ -13,6 +13,11 @@ test-suite utility : [ run ../addressof_test.cpp ] + [ compile adv_dist_hdr_compiles.cpp ] + [ run adv_bidi_run.cpp ../../test/build//boost_unit_test_framework ] + [ run adv_forward_run.cpp ../../test/build//boost_unit_test_framework ] + [ run adv_incr_run.cpp ../../test/build//boost_unit_test_framework ] + [ run adv_ra_run.cpp ../../test/build//boost_unit_test_framework ] [ run ../assert_test.cpp ] [ run ../base_from_member_test.cpp ] [ run ../binary_search_test.cpp ] @@ -20,6 +25,10 @@ [ compile-fail ../checked_delete_test.cpp ] [ run ../compressed_pair_test.cpp ../../test/build//boost_test_exec_monitor/<link>static : -u ] [ run ../current_function_test.cpp : : : <test-info>always_show_run_output ] + [ run dist_forward_run.cpp ../../test/build//boost_unit_test_framework ] + [ compile-fail dist_incr_fail.cpp ] + [ run dist_ra_run.cpp ../../test/build//boost_unit_test_framework ] + [ run dist_single_run.cpp ../../test/build//boost_unit_test_framework ] [ run ../iterators_test.cpp ../../test/build//boost_test_exec_monitor/<link>static ] [ run next_prior_test.cpp ../../test/build//boost_test_exec_monitor/<link>static ] [ compile-fail ../noncopyable_test.cpp ]
participants (1)
-
Sebastian Redl