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