Re: [boost] [iterators] Iterator Operations

From: Shunsuke Sogame (mb2act_at_[hidden])
Date: 2006-11-23 17:56:55

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