正如“Iterator Must Go”中所说，STL的算法虽然设计的高效，但是基于迭代器的算法设计使得灵活性和简洁性受到很大的限制，也阻碍了STL算法的更广泛的使用。

range设计的目的就是弥补STL的这个缺陷，用range的概念来取代用迭代器对[first, one_past_last)来标识区间，使得使用算法可以更加灵活和紧凑。

Range的Concept定义

类似于STL中容器的概念，range维护了可以通过迭代器遍历的区间[first, one_past_last)，但是range对元素的要求比容器更少，只是访问而不是占有元素，本身也不具有拷贝语义（因为range不需要拷贝元素）。

基于range中迭代器遍历类型的不同（iterator_traversal<X>::type，新的迭代器的范畴详见“New Iterator Concepts”）。

range也给出了不同的逐步精细的定义：

1、单遍区间（Single Pass Range）
对于单遍区间类型X，boost::range_iterator<X>::type是单遍迭代器（Single Pass Iterator）的范畴。

支持正向遍历的迭代器表达式：

2、前向遍历区间（Forward Range）

boost::range_iterator<X>::type是一个前向迭代器（Forward Traversal Iterator）。

3、双向遍历区间（Bidirectional Range）
boost::range_iterator::type是一个双向遍历迭代器（Bidirectional Traversal Iterator）。

支持用于反向遍历的迭代器表达式： boost::rbegin(a) ：等价于boost::range_reverse_iterator::type( boost::end(a) ) boost::rend(a) ：等价于boost::range_reverse_iterator::type(boost::begin(a))

4、随机访问区间（Random Access Range）
boost::range_iterator<X>::type是一个随机访问迭代器（Random Access Traversal Iterator）。

支持区间长度：boost::size(a)

区间概念检查（Concept Checking）

提供4个类用BOOST_CONCEPT_ASSERT来对对应的range的类型进行concept check。

SinglePassRangeConcept
ForwardRangeConcept
BidirectionalRangeConcept
RandomAccessRangeConcept

例如：

typedef boost::iterator_range< std::vector<int>::iterator > RangeType;
BOOST_CONCEPT_ASSERT( ( boost::RandomAccessRangeConcept<RangeType> ) );

操作Range的功能函数及元函数

元函数

表达式 返回类型
range_iterator<X>::type Range的迭代器类型，有多种可能：T::iterator, P::first_type, A*
range_iterator<const X>::type T::const_iterator, P::first_type, const A*
range_value<X>::type boost::iterator_value<range_iterator<X>::type>::type
range_reference<X>::type boost::iterator_reference<range_iterator<X>::type>::type
range_pointer<X>::type boost::iterator_pointer<range_iterator<X>::type>::type
range_category<X>::type boost::iterator_category<range_iterator<X>::type>::type
range_difference<X>::type boost::iterator_difference<range_iterator<X>::type>::type
range_reverse_iterator<X>::type boost::reverse_iterator<range_iterator<X>::type>
range_reverse_iterator<const X>::type boost::reverse_iterator<range_iterator<const X>::type
has_range_iterator<X>::type mpl::true_ 如果range_mutable_iterator<X>::type 合法
has_range_const_iterator<X>::type mpl::true_如果 range_const_iterator<X>::type 合法

函数

表达式 返回类型 返回值说明
begin(x) range_iterator<X>::type p.first 如果p为std::pair<T> ; a本身如果a为指针或数组; range_begin(x) 如果该表达式能ADL找到 ; 否则为t.begin()
end(x) range_iterator<X>::type p.second - Pair; a + sz - 数组; range_end(x) 通过 ADL; t.end()
empty(x) bool boost::begin(x) == boost::end(x)
distance(x) range_difference<X>::type std::distance(boost::begin(x),boost::end(x))
size(x) range_difference<X>::type 默认boost::end(x) - boost::begin(x)；可以通过实现range_calculate_size(x) 来改变默认行为。
rbegin(x) range_reverse_iterator<X>::type range_reverse_iterator<X>::type(boost::end(x))
rend(x) range_reverse_iterator<X>::type range_reverse_iterator<X>::type(boost::begin(x))
const_begin(x) range_iterator<const X>::type range_iterator<const X>::type(boost::begin(x))
const_end(x) range_iterator<const X>::type range_iterator<const X>::type(boost::end(x))
const_rbegin(x) range_reverse_iterator<const X>::type range_reverse_iterator<const X>::type(boost::rbegin(x))
const_rend(x) range_reverse_iterator<const X>::type range_reverse_iterator<const X>::type(boost::rend(x))
as_literal(x) 如果x为指向string的指针，则为iterator_range<U>，U为Char*；否则U range_iterator<X>::type 如果s是Char* 或Char数组：[s,s + std::char_traits<X>::length(s)) ；否则：[boost::begin(x),boost::end(x))
as_array(x) iterator_range<X> [boost::begin(x),boost::end(x))

例如：

string s = "sjw";
boost::iterator_range<string::iterator> rg1 = boost::as_literal( s );

boost::iterator_range<char*> rg2 = 	boost::as_literal( s.c_str() );

区间配接器

Range配接器之于算法正如算法之于容器。使得算法的表达能力大大增强。

基本语法：rng | boost::adaptors::adaptor_generator

注意：

支持的配接器：

语法：rng | boost::adaptors::adjacent_filtered(bi_pred)

邻接过滤，返回的range中，所有相邻的[x，y]元素，满足bi_pred(x,y)为true。

例如：

int input[] = {1,1,2,2,2,3,4,5,6};
boost::copy(
	input | adjacent_filtered(std::not_equal_to<int>()),
	std::ostream_iterator<int>(std::cout, " "));

输出：1 2 3 4 5 6

语法：rng | boost::adaptors::copied(n, m)

取出一段子区间的元素，要求0 <= n && n <= m && m < distance(rng)

语法：rng | boost::adaptors::filtered(pred)

对range过滤，返回range中的每个元素x，满足pred(x)为true

例如：

#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/algorithm/copy.hpp>

#include <algorithm>
#include <iostream>

int main()
{
	using namespace boost::adaptors;

	int input[] = {1,2,3,4,5,6,7,8,9};

	struct is_even
	{
		bool operator()( int x ) const { return x % 2 == 0; }
	};
	boost::copy(
		input | filtered(is_even()),
		std::ostream_iterator<int>(std::cout, " "));
}

输出：2 4 6 8

语法：rng | boost::adaptors::indexed( N )

返回序列的元素从N开始进行了编号，可以通过访问返回的range的迭代器的index()方法取到对应的编号。

例如：

#include <boost/range/adaptor/indexed.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <algorithm>
#include <iostream>

template<class Iterator>
void display_element_and_index(Iterator first, Iterator last)
{
	for (Iterator it = first; it != last; ++it)
	{
		std::cout << "Element = " << *it << " Index = " << it.index() << std::endl;
	}
}

template<class SinglePassRange>
void display_element_and_index(const SinglePassRange& rng)
{
	display_element_and_index(boost::begin(rng), boost::end(rng));
}

int main()
{
	using namespace boost::adaptors;

	int input[] = {10,20,30,40};

	display_element_and_index( input | indexed(5) );

	return 0;
}

输出：
Element = 10 Index = 5
Element = 20 Index = 6
Element = 30 Index = 7
Element = 40 Index = 8

语法：rng | boost::adaptors::indirected

返回原序列元素解引用后的序列（如对指针或迭代器解引用）。

例如：

#include <boost/range/adaptor/indirected.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/shared_ptr.hpp>
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
	using namespace boost::adaptors;

	std::vector<boost::shared_ptr<int> > input;
	for (int i = 0; i < 10; ++i)
		input.push_back( boost::shared_ptr<int>(new int(i)) );

	boost::copy(
		input | indirected,
		std::ostream_iterator<int>(std::cout, " "));

	return 0;
}

输出：0 1 2 3 4 5 6 7 8 9

语法：rng | boost::adaptors::map_keys

对于原序列中的每个元素y，返回序列的每个元素x为对应的y.first。因此，原序列可以是关联容器如map<T, U>，或者是pair<T,U>的序列如vector< pair<T, U> >。

语法：rng | boost::adaptors::map_values

对于原序列中的每个元素y，返回序列的每个元素x为对应的y.second。

语法：rng | boost::adaptors::replaced(new_value, old_value)

将原序列中的old_value替换为new_value的序列。

语法：rng | boost::adaptors::replaced_if(pred, new_value)

对于原序列的每个元素x，对应的新序列元素满足 pred(x) ? new_value : x得到的序列。

语法：rng | boost::adaptors::reversed

得到一个逆向的range。

语法：rng | boost::adaptors::sliced(n, m) 与copied同义。

语法：rng | boost::adaptors::strided(n)

以间隔n的方式从第一个元素开始遍历得到的序列。

语法：

rng | boost::adaptors::tokenized(regex)
rng | boost::adaptors::tokenized(regex, i)
rng | boost::adaptors::tokenized(regex, rndRng)
rng | boost::adaptors::tokenized(regex, i, flags)
rng | boost::adaptors::tokenized(regex, rndRng, flags)

例如：

#include <boost/range/adaptor/tokenized.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/regex.hpp>

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using std::string;
using std::vector;

int main()
{
	// 3个数字加一个单词的格式
	boost::regex reg( "\\d{3}[a-zA-Z]+" );
	string str = "sjw 123sjw 234suninf00";
	vector<string> match_strs;
	boost::copy( str | boost::adaptors::tokenized(reg), std::back_inserter(match_strs) );
	return 0;
}

语法：rng | boost::adaptors::transformed(fun)

用fun对原序列中的元素进行转化而得到的序列，这个方式大大增加了序列变化的灵活性。

语法：rng | boost::adaptors::uniqued

保证得到的序列的相邻的元素不等，即对于相邻的[x,y]，有!( x==y )。

Range算法

基本上，基于Range的算法是STL算法的基于迭代器对算法的补充，另外，Range算法也新增了一些有用的算法和特征。

关于返回值的说明：

表达式 返回值
boost::unique<boost::return_found>(rng) 仅返回迭代器，同std::unique
boost::unique<boost::return_begin_found>(rng) 返回range [boost::begin(rng), found) 默认
boost::unique<boost::return_begin_next>(rng) [boost::begin(rng), boost::next(found))
boost::unique<boost::return_found_end>(rng) [found, boost::end(rng))
boost::unique<boost::return_next_end>(rng) [boost::next(found),boost::end(rng))
boost::unique<boost::return_begin_end>(rng) 返回整个range

变动性算法

不改变相同子区间元素顺序。

与remove_copy相比，多了个谓词判断。

拷贝到输出迭代器版本和谓词版本。

输出迭代器版本。

拷贝输出版本。

输出迭代器版本。

非变动性算法

谓词判断的版本。

返回“第一个大于value”或者pred( val, x )为true的元素位置。可以配置返回值。

与下search仅查找第一个子串与最后一个子串的区别。

最小元素对应的迭代器。

已序序列集合算法

堆算法

排列算法

数值算法

相比STL新增的一些算法（algorithm_ext）

例如：

#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext/erase.hpp>
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
	int input[] = { 1,3,5,7,9,2,4,6,8, 2,2,3,3,4,4 };
	std::vector<int> vec;
	boost::copy( input, std::back_inserter(vec) );

	// 排序并删除重复元素
	boost::erase(vec, boost::unique<boost::return_found_end>( boost::sort(vec) ));
	
	boost::copy( vec, std::ostream_iterator<int>(std::cout, " ") );

	return 0;
}

输出：1 2 3 4 5 6 7 8 9

工具类和函数

iterator_range

封装了两个迭代器，构造了前向Renge的概念。

声明：

template< class ForwardTraversalIterator >
class iterator_range
{
public: // Forward Range types
	typedef ForwardTraversalIterator   iterator;
	typedef ForwardTraversalIterator   const_iterator;
	typedef iterator_difference<iterator>::type difference_type;

public: // construction, assignment
	template< class ForwardTraversalIterator2 >
	iterator_range( ForwardTraversalIterator2 Begin, ForwardTraversalIterator2 End );

	template< class ForwardRange >
	iterator_range( ForwardRange& r );

	template< class ForwardRange >
	iterator_range( const ForwardRange& r );

	template< class ForwardRange >
	iterator_range& operator=( ForwardRange& r );

	template< class ForwardRange >
	iterator_range& operator=( const ForwardRange& r );

public: // Forward Range functions
	iterator  begin() const;
	iterator  end() const;

public: // convenience
	operator    unspecified_bool_type() const; 
	bool        equal( const iterator_range& ) const;

	value_type& front() const;
	value_type& back() const;
	iterator_range& advance_begin(difference_type n);
	iterator_range& advance_end(difference_type n);
	bool      empty() const;

	// for Random Access Range only: 
	reference operator[]( difference_type at ) const;
	value_type operator()( difference_type at ) const;
	size_type size() const;
};

非成员函数：

template< class ForwardTraversalIterator >
iterator_range< ForwardTraversalIterator >
make_iterator_range( ForwardTraversalIterator Begin, 
					ForwardTraversalIterator End );

template< class ForwardRange >
iterator_range< typename range_iterator<ForwardRange>::type >
make_iterator_range( ForwardRange& r );

template< class ForwardRange >
iterator_range< typename range_iterator<const ForwardRange>::type >
make_iterator_range( const ForwardRange& r );

template< class Range >
iterator_range< typename range_iterator<Range>::type >
make_iterator_range( Range& r,
				typename range_difference<Range>::type advance_begin,
					typename range_difference<Range>::type advance_end );

template< class Range >
iterator_range< typename range_iterator<const Range>::type >
make_iterator_range( const Range& r, 
			typename range_difference<const Range>::type advance_begin,
			typename range_difference<const Range>::type advance_end );

sub_range

template< class ForwardRange >
class sub_range : 
	public iterator_range< typename range_iterator<ForwardRange>::type >
{
	//...
};

sub_range的模板参数为Range，直接继承自iterator_range，只不过迭代器模板参数是计算出来。

例如：

std::string str("hello");
iterator_range<std::string::iterator> ir = find_first( str, "ll" );
sub_range<std::string>               sub = find_first( str, "ll" );

join

template<typename SinglePassRange1, typename SinglePassRange2>
iterator_range<...>
join(const SinglePassRange1& rng1, const SinglePassRange2& rng2)

template<typename SinglePassRange1, typename SinglePassRange2>
iterator_range<...>
join(SinglePassRange1& rng1, SinglePassRange2& rng2);
将两个range连接起来。

Range库扩展

1、 使自己的序列满足range概念的序列：

2、使用配接器由于可以多次operator|折叠，这样使得range的配接可以非常的灵活

比如：取出奇数并平方输出

#include <boost/range/algorithm.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include <vector> 
#include <iostream>

int main()
{
	int input[] = {1,2,3,4,5,6,7};

	struct is_odd
	{
		bool operator() (int n) const {return n%2==1; }
	};

	struct square 
	{
		typedef int result_type; // 标准仿函数返回类型声明
		int operator() (int n) const {return n*n;}
	};

	boost::copy( input | boost::adaptors::filtered( is_odd() )
		                  | boost::adaptors::transformed( square() ), 
		           std::ostream_iterator<int>(std::cout, " ") );

	return 0;
}

输出：1 9 25 49

总之，灵活的使用range配接器和算法，让代码更加直接清晰，富有表达力。

3、Range配接器的实现

一般来说，已有的配接器已经具有很大的灵活性，一般不需要直接进行adaptor底层扩展，如果需要的话，也是有套路的。

(1)、实现无参数配接器 如：reversed

namespace boost
{
    namespace range_detail
    {
        template< class R >
        struct reverse_range : // 实现了Range概念的逆向range类型
            public boost::iterator_range< 
                      boost::reverse_iterator<
                        typename range_iterator<R>::type >
                                         >
        {
        private:
            typedef boost::iterator_range< 
                      boost::reverse_iterator<
                        typename range_iterator<R>::type >
                                         >   base;
            
        public:
            typedef boost::reverse_iterator<typename range_iterator<R>::type> iterator;

            reverse_range( R& r ) 
                : base( iterator(boost::end(r)), iterator(boost::begin(r)) )
            { }
        };

        struct reverse_forwarder {};	// Adaptor的标识，用于operator|()
        
		// 灵活的operator|()操作，返回reverse_range对象
        template< class BidirectionalRng >
        inline reverse_range<BidirectionalRng> 
        operator|( BidirectionalRng& r, reverse_forwarder )
        {
            return reverse_range<BidirectionalRng>( r );   
        }
    
        template< class BidirectionalRng >
        inline reverse_range<const BidirectionalRng> 
        operator|( const BidirectionalRng& r, reverse_forwarder )
        {
            return reverse_range<const BidirectionalRng>( r );   
        }
        
    } // 'range_detail'
    
    using range_detail::reverse_range;

    namespace adaptors
    { 
        namespace
        {
			// 写一个标识对象，用于operator|()的右参数
            const range_detail::reverse_forwarder reversed = 
                                            range_detail::reverse_forwarder();
        }
        
		// 支持函数调用来返回reverse_range的版本，但是不实用
        template<class BidirectionalRange>
        inline reverse_range<BidirectionalRange>
        reverse(BidirectionalRange& rng)
        {
            return reverse_range<BidirectionalRange>(rng);
        }
        
        template<class BidirectionalRange>
        inline reverse_range<const BidirectionalRange>
        reverse(const BidirectionalRange& rng)
        {
            return reverse_range<const BidirectionalRange>(rng);
        }
    } // 'adaptors'
    
} // 'boost'

(2)、实现带参数的配接器如 replaced

namespace boost
{
    namespace range_detail
    {
		// 实际配接运算的仿函数
        template< class Value >
        class replace_value
        {
        public:
            typedef const Value& result_type;
            typedef const Value& first_argument_type;

            replace_value(const Value& from, const Value& to)
                :   m_from(from), m_to(to)
            {
            }

            const Value& operator()(const Value& x) const
            {
                return (x == m_from) ? m_to : x;
            }

        private:
            Value m_from;
            Value m_to;
        };

        template< class R >
        class replaced_range : // 配接返回的Range类型
            public boost::iterator_range<
                boost::transform_iterator< // 使用boost.iterator库
                    replace_value< typename range_value<R>::type >,
                    typename range_iterator<R>::type > >
        {
        private:
            typedef replace_value< typename range_value<R>::type > Fn; // 操作

            typedef boost::iterator_range<
                boost::transform_iterator<
                    replace_value< typename range_value<R>::type >,
                    typename range_iterator<R>::type > > base_t;

        public:
            typedef typename range_value<R>::type value_type;

            replaced_range( R& r, value_type from, value_type to )
                : base_t( make_transform_iterator( boost::begin(r), Fn(from, to) ),
                          make_transform_iterator( boost::end(r), Fn(from, to) ) )
            { }
        };

		// Adaptor的标识类，带参数的需要写上holder
        template< class T >
        class replace_holder : public holder2<T>
        {
        public:
            replace_holder( const T& from, const T& to )
                : holder2<T>(from, to)
            { }
        private:
            // not assignable
            void operator=(const replace_holder&);
        };

        template< class InputRng >
        inline replaced_range<InputRng>
        operator|( InputRng& r,
                   const replace_holder<typename range_value<InputRng>::type>& f )
        {
            return replaced_range<InputRng>(r, f.val1, f.val2);
        }

        template< class InputRng >
        inline replaced_range<const InputRng>
        operator|( const InputRng& r,
                   const replace_holder<typename range_value<InputRng>::type>& f )
        {
            return replaced_range<const InputRng>(r, f.val1, f.val2);
        }
    } // 'range_detail'

    using range_detail::replaced_range;

    namespace adaptors
    {
        namespace
        {
            const range_detail::forwarder2<range_detail::replace_holder>
                replaced =
                    range_detail::forwarder2<range_detail::replace_holder>();
        }

        template<class InputRange>
        inline replaced_range<InputRange>
        replace(InputRange& rng,
                typename range_value<InputRange>::type from,
                typename range_value<InputRange>::type to)
        {
            return replaced_range<InputRange>(rng, from, to);
        }

        template<class InputRange>
        inline replaced_range<const InputRange>
        replace(const InputRange& rng,
                typename range_value<const InputRange>::type from,
                typename range_value<const InputRange>::type to)
        {
            return replaced_range<const InputRange>(rng, from ,to);
        }

    } // 'adaptors'
} // 'boost'