Sebastian Redl wrote:

Hi,

A few days ago, I made a comment about std::distance() and std::advance() being reimplemented for the new style iterator concepts. Dave said that patches are welcome.

So I sat down and wrote some preliminary versions of the two functions. They are in the attached file. The file parses cleanly, but I have not tried instantiating any of the templates yet.

I have a question, though. Does it make sense to implement boost::distance for single pass iterators? Is there anything useful that could be done with the resulting information?

I have the same question. Range Library Proposal requires Forward, but 'std::distance' requires Input.

Aside from that, I'd be happy to receive any suggestions for code improvement, adherence to Boost standards, and so on.

Sebastian Redl

------------------------------------------------------------------------

#ifndef BOOST_ITERATOR_ITERATOR_OPS_HPP #define BOOST_ITERATOR_ITERATOR_OPS_HPP

#include <boost/iterator/iterator_categories.hpp> #include <boost/iterator/iterator_concepts.hpp>

namespace boost { namespace detail {

template <class IncrementableIterator, class Distance> void advance(boost::incrementable_traversal_tag, IncrementableIterator &i, Distance n) { boost::function_requires< boost_concepts::IncrementableIteratorConcept< IncrementableIterator > >();

while(n) { ++i; --n; } }

FWIW, it seems the new Concept Check library is under construction (cvs head).

// Single pass and forward traversal is the same.

template <class BidirectionalTraversableIterator, class Distance> void advance(boost::bidirectional_traversal_tag, BidirectionalTraversableIterator &i, Distance n) { boost::function_requires< boost_concepts::BidirectionalTraversalConcept< BidirectionalTraversableIterator > >();

if(n > 0) { while(n) { ++i; --n; } } else { while(n) { --i; ++n; } } }

Can't forward it to 'std::advance'?

template <class RandomAccessTraversableIterator, class Distance> void advance(boost::random_access_traversal_tag, RandomAccessTraversableIterator &i, Distance n) { boost::function_requires< boost_concepts::RandomAccessTraversalConcept< RandomAccessTraversableIterator > >();

i += n; } }

// A replacement for std::advance that uses the new iterator categories. template <class IncrementableIterator, class Distance> void advance(IncrementableIterator &i, Distance n) { typedef BOOST_DEDUCED_TYPENAME boost::iterator_traversal< IncrementableIterator >::type traversal; detail::advance(traversal(), i, n); }

namespace detail { template <class SinglePassIterator> BOOST_DEDUCED_TYPENAME std::iterator_traits< SinglePassIterator>::difference_type distance(boost::single_pass_traversal_tag, SinglePassIterator first, SinglePassIterator last) { boost::function_requires< boost_concepts::SinglePassIteratorConcept< SinglePassIterator > >();

BOOST_DEDUCED_TYPENAME std::iterator_traits<SinglePassIterator>::difference_type n = 0; while(first != last) { ++first; ++n; } return n; }

Can't forward it to 'std::distance'?

// Forward and bidirectional are the same.

template <class RandomAccessTraversableIterator> BOOST_DEDUCED_TYPENAME std::iterator_traits< RandomAccessTraversableIterator>::difference_type distance(boost::random_access_traversal_tag, RandomAccessTraversableIterator first, RandomAccessTraversableIterator last) { boost::function_requires< boost_concepts::RandomAccessTraversalConcept< RandomAccessTraversableIterator > >();

return last - first; } }

// A replacement for std::distance that uses the new iterator categories. template <class SinglePassIterator> 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); } }

Can give the difference_type to 'detail::distance' by using boost::type or explicit template parameter, which makes the code cute?

#endif

IMHO, std::advance is conceptually redundant. First <boost/next_prior.hpp> should be patched with your implementation if possible? Also, I think this 'distance' might be contributed to Boost.Range, which has really 'boost::distance'(cvs head). The current implementation just forwards it to 'std::distance'. -- Shunsuke Sogame