ceph/src/boost/libs/range/doc/reference/utilities.qbk

   1 [/
   2     Copyright 2010 Neil Groves
   3     Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 /]
   6 [section:utilities Utilities]
   7
   8 Having an abstraction that encapsulates a pair of iterators is very useful. The standard library uses `std::pair` in some circumstances, but that class is cumbersome to use because we need to specify two template arguments, and for all range algorithm purposes we must enforce the two template arguments to be the same. Moreover, `std::pair<iterator,iterator>` is hardly self-documenting whereas more domain specific class names are. Therefore these two classes are provided:
   9
  10 * Class `iterator_range`
  11 * Class `sub_range`
  12 * Function `combine`
  13 * Function `join`
  14
  15 The `iterator_range` class is templated on an __forward_traversal_iterator__ and should be used whenever fairly general code is needed. The `sub_range` class is templated on an __forward_range__ and it is less general, but a bit easier to use since its template argument is easier to specify. The biggest difference is, however, that a `sub_range` can propagate constness because it knows what a corresponding `const_iterator` is.
  16
  17 Both classes can be used as ranges since they implement the __minimal_interface__ required for this to work automatically.
  18
  19 [section:iterator_range Class `iterator_range`]
  20
  21 The intention of the `iterator_range` class is to encapsulate two iterators so they fulfill the __forward_range__ concept. A few other functions are also provided for convenience.
  22
  23 If the template argument is not a model of __forward_traversal_iterator__, one can still use a subset of the interface. In particular, `size()` requires Random Access Traversal Iterators whereas `empty()` only requires Single Pass Iterators.
  24
  25 Recall that many default constructed iterators are [*/singular/] and hence can only be assigned, but not compared or incremented or anything. However, if one creates a default constructed `iterator_range`, then one can still call all its member functions. This design decision avoids the `iterator_range` imposing limitations upon ranges of iterators that are not singular. Any singularity limitation is simply propagated from the underlying iterator type.
  26
  27
  28 [h4 Synopsis]
  29
  30 The core functionality is in the header file
  31 `<boost/range/iterator_range_core.hpp>` this includes all of the functionality
  32 except the `boost::hash_value` and `std::iostream` support.
  33
  34 The `std::iostream` support is in the header `<boost/range/iterator_core.hpp>`
  35 while the `boost::hash_value` support is in
  36 `<boost/range/iterator_range_hash.hpp>`
  37
  38 ``
  39 namespace boost
  40 {
  41     template< class ForwardTraversalIterator >
  42     class iterator_range
  43     {
  44     public: // Forward Range types
  45         typedef ForwardTraversalIterator   iterator;
  46         typedef ForwardTraversalIterator   const_iterator;
  47         typedef iterator_difference<iterator>::type difference_type;
  48
  49     public: // construction, assignment
  50         template< class ForwardTraversalIterator2 >
  51         iterator_range( ForwardTraversalIterator2 Begin, ForwardTraversalIterator2 End );
  52
  53         template< class ForwardRange >
  54         iterator_range( ForwardRange& r );
  55
  56         template< class ForwardRange >
  57         iterator_range( const ForwardRange& r );
  58
  59         template< class ForwardRange >
  60         iterator_range& operator=( ForwardRange& r );
  61
  62         template< class ForwardRange >
  63         iterator_range& operator=( const ForwardRange& r );
  64
  65     public: // Forward Range functions
  66         iterator  begin() const;
  67         iterator  end() const;
  68
  69     public: // convenience
  70         operator    unspecified_bool_type() const;
  71         bool        equal( const iterator_range& ) const;
  72         value_type& front() const;
  73         void        drop_front();
  74         void        drop_front(difference_type n);
  75         bool      empty() const;
  76
  77         iterator_range& advance_begin(difference_type n);
  78         iterator_range& advance_end(difference_type n);
  79
  80         // for Bidirectional:
  81         value_type& back() const;
  82         void drop_back();
  83         void drop_back(difference_type n);
  84         // for Random Access only:
  85         reference operator[]( difference_type at ) const;
  86         value_type operator()( difference_type at ) const;
  87         size_type size() const;
  88     };
  89
  90     // stream output
  91     template< class ForwardTraversalIterator, class T, class Traits >
  92     std::basic_ostream<T,Traits>&
  93     operator<<( std::basic_ostream<T,Traits>& Os,
  94                 const iterator_range<ForwardTraversalIterator>& r );
  95
  96     // comparison
  97     template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
  98     bool operator==( const iterator_range<ForwardTraversalIterator>& l,
  99                      const iterator_range<ForwardTraversalIterator2>& r );
 100
 101     template< class ForwardTraversalIterator, class ForwardRange >
 102     bool operator==( const iterator_range<ForwardTraversalIterator>& l,
 103                      const ForwardRange& r );
 104
 105     template< class ForwardTraversalIterator, class ForwardRange >
 106     bool operator==( const ForwardRange& l,
 107                      const iterator_range<ForwardTraversalIterator>& r );
 108
 109     template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
 110     bool operator!=( const iterator_range<ForwardTraversalIterator>& l,
 111                      const iterator_range<ForwardTraversalIterator2>& r );
 112
 113     template< class ForwardTraversalIterator, class ForwardRange >
 114     bool operator!=( const iterator_range<ForwardTraversalIterator>& l,
 115                      const ForwardRange& r );
 116
 117     template< class ForwardTraversalIterator, class ForwardRange >
 118     bool operator!=( const ForwardRange& l,
 119                      const iterator_range<ForwardTraversalIterator>& r );
 120
 121     template< class ForwardTraversalIterator, class ForwardTraversalIterator2 >
 122     bool operator<( const iterator_range<ForwardTraversalIterator>& l,
 123                     const iterator_range<ForwardTraversalIterator2>& r );
 124
 125     template< class ForwardTraversalIterator, class ForwardRange >
 126     bool operator<( const iterator_range<ForwardTraversalIterator>& l,
 127                     const ForwardRange& r );
 128
 129     template< class ForwardTraversalIterator, class ForwardRange >
 130     bool operator<( const ForwardRange& l,
 131                     const iterator_range<ForwardTraversalIterator>& r );
 132
 133     // external construction
 134     template< class ForwardTraversalIterator >
 135     iterator_range< ForwardTraversalIterator >
 136     make_iterator_range( ForwardTraversalIterator Begin,
 137                          ForwardTraversalIterator End );
 138
 139     // Make an iterator_range [first, boost::next(first, n) )
 140     template< class ForwardTraversalIterator, class Integer >
 141     iterator_range< ForwardTraversalIterator >
 142     make_iterator_range_n( ForwardTraversalIterator first, Integer n );
 143
 144
 145     template< class ForwardRange >
 146     iterator_range< typename range_iterator<ForwardRange>::type >
 147     make_iterator_range( ForwardRange& r );
 148
 149     template< class ForwardRange >
 150     iterator_range< typename range_iterator<const ForwardRange>::type >
 151     make_iterator_range( const ForwardRange& r );
 152
 153     template< class Range >
 154     iterator_range< typename range_iterator<Range>::type >
 155     make_iterator_range( Range& r,
 156                          typename range_difference<Range>::type advance_begin,
 157                          typename range_difference<Range>::type advance_end );
 158
 159     template< class Range >
 160     iterator_range< typename range_iterator<const Range>::type >
 161     make_iterator_range( const Range& r,
 162                          typename range_difference<const Range>::type advance_begin,
 163                          typename range_difference<const Range>::type advance_end );
 164
 165     // convenience
 166     template< class Sequence, class ForwardRange >
 167     Sequence copy_range( const ForwardRange& r );
 168
 169 } // namespace 'boost'
 170 ``
 171
 172 If an instance of `iterator_range` is constructed by a client with two iterators, the client must ensure that the two iterators delimit a valid closed-open range [begin,end).
 173
 174 It is worth noticing that the templated constructors and assignment operators allow conversion from `iterator_range<iterator>` to `iterator_range<const_iterator>`. Similarly, since the comparison operators have two template arguments, we can compare ranges whenever the iterators are comparable; for example when we are dealing with const and non-const iterators from the same container.
 175
 176 [h4 Details member functions]
 177
 178 `operator unspecified_bool_type() const;`
 179
 180 [:['[*Returns]] `!empty();`]
 181
 182 `bool equal( iterator_range& r ) const;`
 183
 184 [:['[*Returns]] `begin() == r.begin() && end() == r.end();`]
 185
 186 [h4 Details functions]
 187
 188 `bool operator==( const ForwardRange1& l, const ForwardRange2& r );`
 189
 190 [:['[*Returns]] `size(l) != size(r) ? false : std::equal( begin(l), end(l), begin(r) );`]
 191
 192 `bool operator!=( const ForwardRange1& l, const ForwardRange2& r );`
 193
 194 [:['[*Returns]] `!( l == r );`]
 195
 196 `bool operator<( const ForwardRange1& l, const ForwardRange2& r );`
 197
 198 [:['[*Returns]] `std::lexicographical_compare( begin(l), end(l), begin(r), end(r) );`]
 199
 200 ``
 201 iterator_range make_iterator_range( Range& r,
 202                                     typename range_difference<Range>::type advance_begin,
 203                                     typename range_difference<Range>::type advance_end );
 204 ``
 205
 206 [:['[*Effects:]]]
 207
 208 ``
 209     iterator new_begin = begin( r ),
 210     iterator new_end   = end( r );
 211     std::advance( new_begin, advance_begin );
 212     std::advance( new_end, advance_end );
 213     return make_iterator_range( new_begin, new_end );
 214 ``
 215
 216 `Sequence copy_range( const ForwardRange& r );`
 217
 218 [:['[*Returns]] `Sequence( begin(r), end(r) );`]
 219
 220 [endsect]
 221
 222 [section:sub_range Class `sub_range`]
 223
 224 The `sub_range` class inherits all its functionality from the __iterator_range__ class. The `sub_range` class is often easier to use because one must specify the __forward_range__ template argument instead of an iterator. Moreover, the `sub_range` class can propagate constness since it knows what a corresponding `const_iterator` is.
 225
 226 [h4 Synopsis]
 227
 228 ``
 229 namespace boost
 230 {
 231     template< class ForwardRange >
 232     class sub_range : public iterator_range< typename range_iterator<ForwardRange>::type >
 233     {
 234     public:
 235         typedef typename range_value<ForwardRange>::type value_type;
 236         typedef typename range_iterator<ForwardRange>::type iterator;
 237         typedef typename range_iterator<const ForwardRange>::type  const_iterator;
 238         typedef typename range_difference<ForwardRange>::type difference_type;
 239         typedef typename range_size<ForwardRange>::type size_type;
 240         typedef typename range_reference<ForwardRange>::type reference;
 241         typedef typename range_reference<const ForwardRange>::type const_reference;
 242
 243     public: // construction, assignment
 244         sub_range();
 245
 246         template< class ForwardTraversalIterator >
 247         sub_range( ForwardTraversalIterator Begin, ForwardTraversalIterator End );
 248
 249         template< class ForwardRange2 >
 250         sub_range( ForwardRange2& r );
 251
 252         template< class ForwardRange2 >
 253         sub_range( const Range2& r );
 254
 255         template< class ForwardRange2 >
 256         sub_range& operator=( ForwardRange2& r );
 257
 258         template< class ForwardRange2 >
 259         sub_range& operator=( const ForwardRange2& r );
 260
 261         // iterator accessors
 262         const_iterator begin() const;
 263         iterator begin();
 264         const_iterator end() const;
 265         iterator end();
 266
 267         reference front();
 268         const_reference front() const;
 269
 270         sub_range& advance_begin(difference_type n);
 271         sub_range& advance_end(difference_type n);
 272
 273         // If traversal >= bidirectional:
 274         reference back();
 275         const_reference back();
 276
 277         // If traversal >= random-access:
 278         reference operator[](difference_type n);
 279         const_reference operator[](difference_type n) const;
 280
 281     public:
 282         // rest of interface inherited from iterator_range
 283     };
 284
 285 } // namespace 'boost'
 286 ``
 287
 288 The class should be trivial to use as seen below. Imagine that we have an algorithm that searches for a sub-string in a string. The result is an iterator_range, that delimits the match. We need to store the result from this algorithm. Here is an example of how we can do it with and without `sub_range`
 289
 290 ``
 291 std::string str("hello");
 292 iterator_range<std::string::iterator> ir = find_first( str, "ll" );
 293 sub_range<std::string>               sub = find_first( str, "ll" );
 294 ``
 295
 296 [endsect]
 297
 298 [section:combine Function combine]
 299
 300 The `combine` function is used to make one range from multiple ranges. The
 301 `combine` function returns a `combined_range` which is an `iterator_range` of
 302 a `zip_iterator` from the Boost.Iterator library.
 303
 304 [h4 Synopsis]
 305
 306 ``
 307 namespace boost
 308 {
 309     namespace range
 310     {
 311
 312 template<typename IterTuple>
 313 class combined_range
 314     : public iterator_range<zip_iterator<IterTuple> >
 315 {
 316 public:
 317     combined_range(IterTuple first, IterTuple last);
 318 };
 319
 320 template<typename... Ranges>
 321 auto combine(Ranges&&... rngs) ->
 322     combined_range<decltype(boost::make_tuple(boost::begin(rngs)...))>
 323
 324     } // namespace range
 325 } // namespace boost
 326 ``
 327
 328 * [*Precondition:] For each type `r` in `Ranges`, `r` is a model of
 329 __single_pass_range__ or better.
 330 * [*Return Type:] `combined_range<tuple<typename range_iterator<Ranges>::type...> >`
 331 * [*Returned Range Category:] The minimum of the range category of every range
 332 `r` in `Ranges`.
 333
 334 [h4 Example]
 335
 336 ``
 337 #include <boost/range/combine.hpp>
 338 #include <boost/foreach.hpp>
 339 #include <iostream>
 340 #include <vector>
 341 #include <list>
 342
 343 int main(int, const char*[])
 344 {
 345     std::vector<int> v;
 346     std::list<char> l;
 347     for (int i = 0; i < 5; ++i)
 348     {
 349         v.push_back(i);
 350         l.push_back(static_cast<char>(i) + 'a');
 351     }
 352
 353     int ti;
 354     char tc;
 355     BOOST_FOREACH(boost::tie(ti, tc), boost::combine(v, l))
 356     {
 357         std::cout << '(' << ti << ',' << tv << ')' << '\n';
 358     }
 359
 360     return 0;
 361 }
 362 ``
 363
 364 This produces the output:
 365 ``
 366 (0,a)
 367 (1,b)
 368 (2,c)
 369 (3,d)
 370 (4,e)
 371 ``
 372
 373 [endsect]
 374
 375 [section:join Function join]
 376
 377 The intention of the `join` function is to join two ranges into one longer range.
 378
 379 The resultant range will have the lowest common traversal of the two ranges supplied as parameters.
 380
 381 Note that the joined range incurs a performance cost due to the need to check if the end of a range has been reached internally during traversal.
 382
 383 [h4 Synopsis]
 384
 385 ``
 386 template<typename SinglePassRange1, typename SinglePassRange2>
 387 joined_range<const SinglePassRange1, const SinglePassRange2>
 388 join(const SinglePassRange1& rng1, const SinglePassRange2& rng2)
 389
 390 template<typename SinglePassRange1, typename SinglePassRange2>
 391 joined_range<SinglePassRange1, SinglePassRange2>
 392 join(SinglePassRange1& rng1, SinglePassRange2& rng2);
 393 ``
 394
 395 For the const version:
 396
 397 * [*Precondition:] The `range_value<SinglePassRange2>::type` must be convertible to `range_value<SinglePassRange1>::type`. The `range_reference<const SinglePassRange2>::type` must be convertible to `range_reference<const SinglePassRange1>::type`.
 398 * [*Range Category:] Both `rng1` and `rng2` must be a model of __single_pass_range__ or better.
 399 * [*Range Return Type:] `joined_range<const SinglePassRange1, const SinglePassRange2>` which is a model of the lesser of the two range concepts passed.
 400 * [*Returned Range Category:] The minimum of the range category of `rng1` and `rng2`.
 401
 402 For the mutable version:
 403
 404 * [*Precondition:] The `range_value<SinglePassRange2>::type` must be convertible to `range_value<SinglePassRange1>::type`. The `range_reference<SinglePassRange2>::type` must be convertible to `range_reference<SinglePassRange1>::type`.
 405 * [*Range Category:] Both `rng1` and `rng2` must be a model of __single_pass_range__ or better.
 406 * [*Range Return Type:] `joined_range<SinglePassRange1, SinglePassRange2>` which is a model of the lesser of the two range concepts passed.
 407 * [*Returned Range Category:] The minimum of the range category of `rng1` and `rng2`.
 408
 409 [h4 Example]
 410
 411 The expression `join(irange(0,5), irange(5,10))` would evaluate to a range representing an integer range `[0,10)`
 412
 413
 414 [endsect]
 415
 416 [endsect]
 417