Click here to Skip to main content
15,886,512 members
Articles / Programming Languages / C++
Article

Functional STL using Range Adaptors

Rate me:
Please Sign up or sign in to vote.
3.75/5 (20 votes)
16 Feb 200723 min read 38.2K   236   13  
Introduction to Functional STL Library using Boost.Range Adaptors.

1 Introduction

Oven provides an experimental Range Adaptor implementation of Range Library Proposal:

typedef
    any_range<int, boost::single_pass_traversal_tag>
range;

range sieve(range rng)
{
    return rng|dropped(1)|filtered(regular(lambda::_1 % front(rng) != 0));
}

range primes
    = iteration(range(counting_from(2)), &::sieve)|transformed(front);

int main()
{
    std::cout << (primes|taken(200));
}

All the types and functions are defined in namespace pstade::oven at <pstade/oven.hpp> unless otherwise specified.

2 Requirements

3 Tested Under

  • Microsoft Visual C++ 2005 Express Edition SP1
  • Microsoft Visual C++ .NET Version 7.1 SP1
  • GCC 3.4.4

4 Specification

This document is based on the following specifications.

std::string src("hello, specification");

boost::result_of<op_make_filtered(std::string&, bool(*)(char))>::type
    result = make_filtered(src, &is_upper);
BOOST_CHECK( equals(result, src|filtered(&is_upper)) );

All the ranges Oven defines are InputStreamable and OutputStreamable if <pstade/oven/io.hpp> is included.

[1]The function type is not supported as rfun. Instead, add & to make a function pointer.

5 Range Algorithms

Oven provides some range-based algorithms. <pstade/oven/functions.hpp> includes all the following functions unless otherwise specified.

5.1 STL Algorithms

Oven has all the range-based STL algorithms, which are ported from Boost.RangeEx with some compiler workarounds:

std::string str;

// iterator-based
str = "gfedcba";
std::sort(str.begin(), str.end());
BOOST_CHECK( str == "abcdefg" );

// Oven range-based
str = "gfedcba";
oven::sort(str);
BOOST_CHECK( str == "abcdefg" );
  • Header: <pstade/oven/algorithm.hpp> and <pstade/oven/numeric.hpp>
  • Valid expression: algo(rng,a0,a1,..,aN), where algo is a Function Object.
  • Precondition: std::algo(boost::begin(rng),boost::end(rng),a0,a1,..,aN) is a valid expression, where algo is one of the STL algorithms.
  • Returns: std::algo(boost::begin(rng),boost::end(rng),a0,a1,..,aN)

5.2 adapted_to/to_base

adapted_to gets the base_type iterator of adapted iterators:

std::string src("cjaigvwzenqhe");
std::string::iterator it = oven::adapted_to<std::string::iterator>(
    oven::max_element(
        src
            | filtered(regular(lambda::_1 != 'z'))
            | filtered(regular(lambda::_1 != 'w'))
    )
);

BOOST_CHECK( *it == 'v' );
  • Header: <pstade/oven/adapted_to_base.hpp>
  • Valid expression: base = oven::adapted_to<BaseIter>(it); or BaseIter base = it|to_base; [2]
  • Precondition: The type of base is BaseIter, and it is an adapted iterator.
[2]to_base adds the automatic type deduction to adapted_to.

5.3 begin/end

begin/end is a pipable version of boost::begin/end:

std::string src("abcDefg");   
oven::copy(src|reversed|transformed(to_upper), src|reversed|begin);
BOOST_CHECK( oven::equals(src, std::string("ABCDEFG")) );
  • Header: <pstade/oven/begin_end.hpp>
  • Valid expression: rng|begin and rng|end
  • Precondition: boost::begin(rng) and boost::end(rng) is a valid expression.
  • Returns: boost::begin(rng) and boost::end(rng) respectively.

5.4 compile

Pending...

compile introduces the syntax sugar for jointed etc:

std::string       rng1("12");
std::list<char>   rng2 = std::string("34")|copied;
std::vector<char> rng3 = std::string("56")|copied;

BOOST_CHECK( equals(
    compile( +(rng1 >> (rng2|as_term) >> rng3) ) | taken(17),
    std::string("12345612345612345")
) );
  • Header: <pstade/oven/compile.hpp>
  • Valid expression: compile(rngExpr)

5.5 copied

copied adds the automatic type deduction to copy_range which calls the range constructor of the STL Sequences:

std::vector<int> vec = oven::counting(3, 9)|copied;
vec.push_back(9);
BOOST_CHECK( oven::equals(vec, oven::counting(3, 10)) );
  • Header: <pstade/oven/copy_range.hpp>
  • Valid expression: Seq seq = rng|copied; [3]
  • Precondition: Seq seq = boost::copy_range<Seq>(rng); is a valid expression.
  • Effect: Seq seq = boost::copy_range<Seq>(rng);
[3]Seq seq(rng|copied); is not a valid expression.

5.6 distance

The upcoming Boost.Range will replace boost::size by boost::distance. oven::distance that is the same as boost::distance makes your code portable:

std::string str("012345");
BOOST_CHECK( oven::distance(str) == 6 );
  • Header: <pstade/oven/distance.hpp>
  • Valid expression: distance(rng)
  • Precondition: std::distance(boost::begin(rng),boost::end(rng)) is a valid expression.
  • Returns: std::distance(boost::begin(rng),boost::end(rng))

5.7 equals

equals is the range-based std::equal that takes two ranges as the arguments:

std::string str("hello, equals");
std::vector<char> vec = str|copied;
BOOST_CHECK( oven::equals(str, vec) );
  • Header: <pstade/oven/equals.hpp>
  • Valid expression: equals(rng1,rng2)
  • Precondition: equal(rng1,boost::begin(rng2)) is a valid expression.
  • Returns: true if and only if the oven::equal(rng1,boost::begin(rng2)) and boost::size(rng1) == boost::size(rng2) returns true. [4]
[4]The size of two ranges too is checked.

5.8 front/back

  • Header: <pstade/oven/front_back.hpp>
  • Valid expression: front(rng) and back(biRng).
  • Precondition: boost::range_value of rng is CopyConstructible.
  • Returns: V(*boost::begin(rng)) and V(*--boost::end(biRng)) respectively, where V is boost::range_value of rng. [5]
[5]They don't return references because of 24.1/9.

6 Utilities

Some helper function objects are given to fill the gap between Oven and other libraries.

6.1 innumerable

As discribed below, the function object generation needs is slightly different from the Generator concept defined by the Standard. innumerable turns the Generator function object into the Standard conforming one, which creates an infinite range, working with generation.

  • Header: <pstade/oven/generation.hpp>
  • Valid expression: innumerable(rfun)
  • Returns: A generation conforming function object.

6.2 regular

Boost.Lambda functors are neither DefaultConstructible nor CopyAssignable. An iterator holding such a functor cannot conform to even InputIterator. So that, regular converts it to comfortable one for iterators. [6]

  • Header: <pstade/oven/regular.hpp>
  • Valid expression: regular(lambdaFunctor)
  • Returns: A rfun which is DefaultConstructible and CopyAssignable.

In principle, call regular before a lambda functor is passed to Range Adaptors.

[6]regular incidentally converts the functor into the one which can take non-const rvalues.

6.3 shared_regular

shared_regular converts a noncopyable function object type to copyable one.

  • Header: <pstade/oven/regular.hpp>
  • Valid expression: shared_regular(p).
  • Precondition: boost::shared_ptr is constructible from p.
  • Returns: A rfun which is DefaultConstructible and CopyAssignable.

7 Ranges

Oven provides some predefined range types. <pstade/oven/ranges.hpp> includes every range header unless otherwise specified.

7.1 any_range

Oven supports boost::result_of, but it is sometimes cumbersome to get the type of the adapted range. any_range behaves as the type erasure of ranges:

any_range<int, boost::single_pass_traversal_tag> factorials =
    counting_from(1) |
        scanned(1, regular(lambda::_1 * lambda::_2));
  • Header: <pstade/oven/any_range.hpp>
  • Valid expression: any_range<R,T> any_;, any_range<R,T> any_(rng); and any_range<R,T> any_ = rng; , where the iterators of any_ are Interoperatable if and only if rngs are the same type.
  • Precondition: boost::range_reference of rng is convertible to R without creating rvalue. T is a TraversalTag.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in any_iterator

7.2 array_range

array_range is a non-Copyable Random Access Range which delivers a range presentation of dynamically allocated arrays:

std::string str("hello, array_range!");
boost::array<char, 19> sarr;
oven::copy(str, sarr|begin);
oven::array_range<char> darr(19);
oven::copy(str, darr|begin);

BOOST_CHECK( oven::equals(sarr, darr) );
  • Header: <pstade/oven/array_range.hpp>
  • Valid expression: array_range<T> rng(sz);
  • Precondition: new T[sz]; is a valid expression.

7.3 directory_range

directory_range is a Single Pass Range which accesses the contents of a directory:

BOOST_FOREACH (
    filesystem::path const& pt,
    directory_range(filesystem::current_path()))
{
    std::cout << pt.leaf() << std::endl;
}
  • Header: <pstade/oven/directory_range.hpp>; not included by <pstade/oven/ranges.hpp>
  • Valid expression: directory_range rng(p); and wdirectory_range wrng(wp);
  • Precondition: The type of p is boost::filesystem::path and the type of wp is boost::filesystem::wpath.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in directory_iterator

7.4 empty_range

empty_range is a Random Access Range which is always empty:

BOOST_CHECK( boost::empty(empty_range<int>()) );
  • Header: <pstade/oven/empty_range.hpp>
  • Valid expression: empty_range<T> rng;

7.5 file_range

file_range is a constant Random Access Range for files:

std::vector<char> vec;
oven::copy(file_range<char>("data.txt"), std::back_inserter(vec));
  • Header: <pstade/oven/file_range.hpp>
  • Valid expression: file_range<C> rng; and rng.is_open();
  • Precondition: boost::spirit::file_iterator<C> is a valid expression.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in file_iterator

The member is_open() returns true if and only if the file opening is succeeded. If is_open() is not true, the range is empty.

8 Range Makers

Oven provides some predefined functions which produce a range. All the range returned from the following makers are CopyConstructible and Inheritable. <pstade/oven/functions.hpp> includes every maker header unless otherwise specified.

8.1 as_array

The current Boost.Range regards char array as literal, which as_array works around.

  • Header: <pstade/oven/as_array.hpp>
  • Valid expression: as_array(arr) and arr|as_array
  • Effect: same as TR2 as_array

8.2 as_c_str

as_c_str makes a Random Access Range from null-terminated c-style string:

{
    wchar_t const *psz = L"hello range";
    BOOST_CHECK( oven::equals(psz|as_c_str, std::wstring(L"hello range")) );
}
{
    std::string src("hello range");
    BOOST_CHECK( oven::equals(src.c_str()|as_c_str, src) );
}
  • Header: <pstade/oven/as_c_str.hpp>
  • Valid expression2: as_c_str(x) and x|as_c_str.
  • Returns: If x is convertible to a char pointer, [x,x+strlen(psz)); otherwise, [boost::begin(x),oven::find(x,0)).

8.3 as_literal

as_literal makes a Random Access Range from character array. as_literal doesn't support any pointer type but array type. So it is safe and fast. Compare it with as_c_str:

{
    BOOST_CHECK( oven::equals("hello range"|as_literal, std::string("hello range")) );
}
{
    BOOST_CHECK( oven::equals(
        "hello\0range"|as_c_str,
        std::string("hello")
    ) );
    BOOST_CHECK( oven::equals(
        "hello\0range"|as_literal,
        std::string("hello")|jointed('\0'|as_single)|jointed(std::string("range"))
    ) );
}
  • Header: <pstade/oven/as_literal.hpp>
  • Valid expression1: as_literal(x) and x|as_literal
  • Returns:If x is an array, [&x[0],&x[0]+sz-1) where sz is the size of arr; otherwise, x as is. [7]
[7]as_literal doesn't use strlen. TR2 as_literal does.

8.4 as_single

as_single makes a Random Access Range which delivers a range presentation of one object:

BOOST_CHECK( oven::equals('a'|as_single, std::string("a")) );
  • Header: <pstade/oven/as_single.hpp>
  • Valid expression: as_single(v) and v|as_single
  • Returns: A range which behaves as if it were [&v,&v+1).

8.5 as_shared_single

  • Header: <pstade/oven/as_single.hpp>
  • Valid expression: as_shared_single(p) and p|as_shared_single
  • Precondition: boost::shared_ptr is constructible from p.
  • Returns: A range which behaves as if it were [&*p,&*p+1).

8.6 counting

counting introduces the replacement of for loop:

int ans[] = { 2, 3, 4, 5, 6 };
BOOST_CHECK( oven::equal(counting(2, 7), ans) );

std::vector<int> vec;
BOOST_FOREACH (int i, counting(0, 5)) {
    vec.push_back(i);
}
  • Header: <pstade/oven/counting.hpp>
  • Valid expression: counting(n, m), where n and m is Incrementable.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in counting_iterator

8.7 counting_from

  • Header: <pstade/oven/counting.hpp>
  • Valid expression: counting_from(n), where n is Incrementable.
  • Returns: A range which behaves as if counting(n,std::numeric_limits<N>::max()), where N is the type of n.

8.8 generation

generation returns a range whose iterators were originally written as generator_iterator:

struct rand_generator
{
    typedef boost::optional<long> result_type;

    result_type operator()()
    {
        long result = std::rand();
        if (result % 3 == 0)
            return result_type(); // range is end.

        return result;
    }
};

void test()
{
    rand_generator X;
    BOOST_FOREACH (long x, oven::generation(X)) {
        std::cout << x << std::endl;
    }
}
  • Header: <pstade/oven/generation.hpp>
  • Valid expression: generation(rfun)
  • Precondition:rfun call returns initialized boost::optional if range is not end; Otherwise, returns uninitialized one.
  • Returns: A Single Pass Range whose values are the results of invoking rfun.

If you have a Standard conforming Generator, you can convert it to generation conforming one by using innumerable.

8.9 indexing

Pending...

8.10 iteration

iteration makes an infinite range where the first item is calculated by applying the function on the first argument, the second item by applying the function on the previous result and so on:

int answer[] = { 1,2,4,8,16 };
BOOST_CHECK( oven::equals(answer,
    oven::iteration(1, regular(lambda::_1 * 2))|oven::taken(5)
) );
  • Header: <pstade/oven/iteration.hpp>
  • Valid expression: iteration(x,fun)
  • Returns: An infinite [8] Single Pass Range of repeated applications of fun to x.
[8]Strictly speaking, the Single Pass Range concept doesn't allow an infinite range. So assume here the end iterator is reachable from the begin iterator in the googolplex number of increments.

8.11 recursion

recursion, collaborating with any_range, creates a recursive [9] range:

typedef any_range<int const&, boost::forward_traversal_tag> range_t;
range_t fibs;
memo_table tb;
int const start[] = { 1, 1 };
fibs =
    start
        | transformed(pstade::as_value)
        | jointed(
            boost::make_tuple(recursion(fibs), recursion(fibs)|dropped(1))
                | zipped_with(regular(lambda::_1 + lambda::_2))
            )
        | memoized(tb)
;

std::cout << (fibs|taken(howMany));
  • Header: <pstade/oven/recursion.hpp>
  • Valid expression: recursion(fwdRng), where fwdRng is an any_range object.
  • Returns: An infinite range up to Bidirectional Range.
[9]In a recursive range, memoized must take a named memo_table object. A recursive range tends to be inefficient without memoization.

8.12 repeated

repeated makes a Random Access Range where all values are the first argument:

BOOST_CHECK( oven::equals(
    'A'|repeated(6),
    std::string("AAAAAA")
) );
  • Header: <pstade/oven/repeated.hpp>
  • Valid expression: v|repeated(c) and make_repeated(v,c)
  • Returns: A range which behaves as if it were as_single(v)|cycled(c).

8.13 stream_input

stream_input makes a Single Pass Range from std::cout etc:

std::string src("hello,stream_input!");

std::stringstream ss;
ss << src;

std::string result;
oven::copy(oven::stream_input<char>(ss), std::back_inserter(result));

BOOST_CHECK( oven::equals(result, src) );
  • Valid expression: oven::stream_input<V>(stm)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in istream_iterator

8.14 streambuf_input

  • Header: <pstade/oven/stream_input.hpp>
  • Valid expression: oven::streambuf_input(stm)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in istreambuf_iterator

9 Range Adaptors

A Range Adaptor delivers an altered presentation of one or more underlying ranges. Range Adaptors are lazy, meaning that their elements are only computed on demand. The underlying ranges are not modified. Additional information is available at Range Library Proposal. <pstade/oven/adaptors.hpp> includes all the following Range Adaptors unless otherwise specified.

Note that all the range returned from the following adaptors are CopyConstructible and Inheritable. Also, if a0|xxx(a1,..,aN) is a valid expression, then make_xxx(a0,..,aN) too is a valid expression which has the same effect.

9.1 adjacent_filtered

9.2 adjacent_transformed

  • Header: <pstade/oven/adjacent_transformed.hpp>
  • Valid expression: fwdRng|adjacent_transformed(rfun)
  • Precondition: boost::empty(fwdRng) == false
  • Returns: A range where adjacent pairs of fwdRng are transformed by using rfun.

9.3 advanced

  • Header: <pstade/oven/advanced.hpp>
  • Valid expression: fwdRng|advanced(d1,d2)
  • Precondition: fwdRng must be a Bidirectional Range if either d1 or d2 is negative.
  • Returns: [boost::next(boost::begin(fwdRng),d1),boost::next(boost::end(fwdRng),d2)).

9.4 always

always returns a range which does not change as the base range vary:

BOOST_CHECK( oven::equals(
    std::string("labor")
        | jointed(std::string("will be"))
        | always("lost"),
    std::string("lost")
) );
  • Header: <pstade/oven/always.hpp>
  • Valid expression: unusedRng|always(rng)
  • Returns: [boost::begin(rng),boost::end(rng)).

9.5 appended

appended returns a range which is appended with its argument:

std::string const str("hello, appen");

BOOST_CHECK( oven::equals(
    str|appended('d')|appended('e')|appended('d')|appended('!'),
    std::string("hello, appended!")
) );
  • Header: <pstade/oven/appended.hpp>
  • Valid expression: rng|appended(v)
  • Returns: A range which behaves as if it were rng|jointed(as_single(v)).

9.6 applied

applied, taking a Function Object which represents an algorithm, creates the range adaptor:

namespace lambda = boost::lambda;
std::string src("abcdefghijk");
std::string s1("efg");
BOOST_CHECK((
    oven::equals(
        std::string("efghijk"),
        src|applied(lambda::bind(oven::search, lambda::_1, s1), oven::end)
    )
));
  • Header: <pstade/oven/applied.hpp>
  • Valid expression1: rng|applied(f1,f2), where f1(rng) and f2(rng) must return iterators that are convertible to rng's.
  • Valid expression2: rng|applied(f), where f(rng) must return a range whose iterators are convertible to rng's.
  • Returns: [f1(rng),f2(rng)), or [boost::begin(r),boost::end(r)) where r = f(rng), respectively.

9.7 broken_into

broken_into is the adaptor version of boost::tokenizer:

int const offsets[] = { 2,2,4 };
std::string src("12252001");
std::vector<std::string> ans; {
    ans.push_back("12");
    ans.push_back("25");
    ans.push_back("2001");
}

BOOST_CHECK( oven::equals(
    ans,
    src|broken_into<std::string>(boost::offset_separator(offsets, offsets+3))
) );
  • Header: <pstade/oven/broken_into.hpp>
  • Valid expression: rng|broken_into<t>(f), where f is a TokenizerFunction.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::token_iterator.

9.8 checked

checked adds the bounds checking ability to the base range:

std::string in("012345");
std::string out("01234");

try {
    oven::copy(in, boost::begin(out|checked));
}
catch (check_error const& ) {
    return;
}

BOOST_CHECK(false);
  • Header: <pstade/oven/checked.hpp>
  • Valid expression: rng|checked
  • Effect: Throws check_error derived from std::range_error if iterators go out of rng.
  • Returns: [boost::begin(rng),boost::end(rng))

9.9 cleared

cleared returns a range which is always empty:

BOOST_CHECK( boost::empty(
    std::string("labor")
        | jointed(std::string("lost"))
        | cleared
) );
  • Header: <pstade/oven/cleared.hpp>
  • Valid expression: rng|cleared
  • Returns: [boost::end(rng),boost::end(rng)).

9.10 concatenated

concatenated accepts a range whose value_type is a range and concatenates them:

std::string input("This is his face");
boost::regex re("\\w+");
BOOST_CHECK( oven::equals(
    input|tokenized(re)|concatenated,
    std::string("Thisishisface")
) );
  • Header: <pstade/oven/concatenated.hpp>
  • Valid expression: rngs|concatenated
  • Specification: SegmentIterator is an iterator of rngs, and LocalIterator is an iterator of the range which the dereference of SegmentIterator returns.
  • Precondition: The LocalIterator must be valid after copying of SegmentIterator.

9.11 constants

  • Header: <pstade/oven/constants.hpp>
  • Valid expression: rng|constants
  • Returns: [boost::end(rng),boost::end(rng)) whose iterators are constant.

9.12 const_lvalues

const_lvalues turns the associated reference type of the base range into reference type, which makes iterators of Forward Range conform to ForwardIterator. Thus, STL that doesn't know traversal concepts can choose effective algorithms.

  • Header: <pstade/oven/const_lvalues.hpp>
  • Valid expression: rng|const_lvalues
  • Precondition: value_type of rng is CopyConstructible, Assignable and DefaultConstructible.
  • Returns: [boost::begin(rng),boost::end(rng)) whose iterators are constant.

9.13 copied_out

copied_out makes a side-effect that copies the base range to its argument:

std::string src("axaxaxbxbxbx");
std::string snapshot;
std::string answer("bbb");

BOOST_CHECK( oven::equals(
    src
        | filtered(regular(lambda::_1 != 'x'))
        | copied_out(std::back_inserter(snapshot))
        | filtered(regular(lambda::_1 != 'a')),
    answer
) );

BOOST_CHECK( snapshot == "aaabbb" );
  • Header: <pstade/oven/copied_out.hpp>
  • Valid expression: rng|copied_out(it)
  • Precondition: oven::copy(rng,it) is a valid expression.
  • Effect: oven::copy(rng,it)
  • Returns: rng.

9.14 cycled

cycled creates a circular range from the base range:

BOOST_CHECK( oven::equals(
    std::string("xyz")|cycled(3),
    std::string("xyzxyzxyz")
) );
  • Header: <pstade/oven/cycled.hpp>
  • Valid expression: rng|cycled(n)
  • Returns: A constant range that repeats [boost::begin(rng),boost::end(rng)) n times.

9.15 delimited

delimited adds a delimiter to the base range:

BOOST_CHECK( equals(
    std::string("abcde")|transformed(as_single)|
        delimited("--"|as_literal)|dropped(2),
    std::string("a--b--c--d--e")
) );
  • Header: <pstade/oven/delimited.hpp>
  • Valid expression: rngs|delimited(delim), where delim is a Range to specify the delimiter.
  • Returns: A range which behaves as if it were rngs|transformed(with)|concatenated, where with is a Function Object which calls make_jointed to joint delim. [10]
[10]delimited prepends the delimiter. dropped is useful to remove it.

9.16 directed

directed returns a range whose values are iterators of the base range:

std::string const str("gefadcb");
std::string const answer("abcdefg");

std::vector<std::string::const_iterator> iters;
oven::copy(str|directed, std::back_inserter(iters));
oven::sort( iters, boost::make_indirect_fun(::less_than()) );

BOOST_CHECK( oven::equals(iters|indirected, answer) );
  • Header: <pstade/oven/directed.hpp>
  • Valid expression: rng|directed
  • Returns: A range which behaves as if it were counting(boost::begin(rng),boost::end(rng)).

9.17 dropped

dropped returns the suffix of the base range after the first n elements:

BOOST_CHECK( oven::equals(
    std::string("hello, dropped!")|dropped(7),
    std::string("dropped!")
) );
  • Header: <pstade/oven/dropped.hpp>
  • Valid expression: rng|dropped(n)
  • Precondition: 0 <= n
  • Returns: [boost::next(boost::begin(rng),std::min(n,distance(rng))),boost::end(rng))

9.18 dropped_while

dropped_while returns the remaining suffix of the base range of elements that satisfy Predicate:

std::string src("11111234516313!");

BOOST_CHECK( oven::equals(
    src|dropped_while(lambda::_1 == '1'),
    std::string("234516313!")
) );
  • Header: <pstade/oven/dropped_while.hpp>
  • Valid expression: rng|dropped_while(pred)
  • Returns: [oven::find_if(rng, not_(pred)),boost::end(rng))

9.19 filtered

filtered returns a range which is filtered by using a Predicate [11]

int src[]    = { 2,5,2,6,1,3,2 };
int answer[] = { 0,5,0,6,1,3,0 };

BOOST_FOREACH (int& i, src|filtered(regular(lambda::_1 == 2))) {
    i = 0;
}

BOOST_CHECK( oven::equals(answer, src) );
[11]A non-assignable lambda functor makes filtered non-conforming, so it needs regular to be applied before it is passed.

9.20 firsts

  • Header: <pstade/oven/firsts.hpp>
  • Valid expression: rng|firsts
  • Returns: A range which behaves as if it were rng|map_keys.

9.21 got_at

Pending...

  • Header: <pstade/oven/got_at.hpp>
  • Valid expression: rng|got_at<N>() or rng|got_at_c<N>(), where value_type of rng is a Fusion Sequence.

9.22 identities

identities returns a range which is identical to the base range:

BOOST_CHECK( oven::equals(
    std::string("hello, identities!")|identities,
    std::string("hello, identities!")
) );
  • Header: <pstade/oven/identities.hpp>
  • Valid expression: rng|identities and rng|identities(trv), where trv is a traversal tag object.
  • Precondition: rng's traversal tag is convertible to trv.
  • Returns: [boost::begin(rng),boost::end(rng)).

9.23 indirected

indirected adapts the base range by applying an extra dereference inside of operator*():

int src[]    = { 1,2,0,4,5 };
int answer[] = { 1,2,3,4,5 };
int *ptrs[]  = {&src[0],&src[1],&src[2],&src[3],&src[4]};

BOOST_FOREACH (int& i, ptrs|indirected) {
    if (i == 0)
        i = 3;
}

BOOST_CHECK( oven::equals(src, answer) );

9.24 jointed

jointed returns a range which is jointed with its argument:

std::string str0("every range");
std::vector<char> str1 = std::string(" is")|copied;
std::list<char> str2 = std::string(" string!?")|copied;

BOOST_CHECK( oven::equals(
    str0|jointed(str1)|jointed(str2),
    std::string("every range is string!?")
) );
  • Header: <pstade/oven/jointed.hpp>
  • Valid expression: rng1|jointed(rng2)
  • Precondition: The boost::range_reference of rng2 is convertible to rng1's without creating a rvalue.
  • Returns: A range that joints [boost::begin(rng1),boost::end(rng1)) and [boost::begin(rng2),boost::end(rng2)).

9.25 map_keys

map_keys returns a range whose values are the keys of the base associative container:

std::map<int, std::string> m;
m[12] = "hello";
m[4]  = "map";
m[99] = "keys";

BOOST_FOREACH (int k, m|map_keys) {
    BOOST_CHECK( k != 12 || m[k] == "hello" );
    BOOST_CHECK( k != 4  || m[k] == "map" );
    BOOST_CHECK( k != 99 || m[k] == "keys" );
}

9.26 map_values

map_values returns a range whose values are the mapped values of the base associative container:

std::map<int, std::string> m;
m[12] = "hello";
m[4]  = "map";
m[99] = "keys";

BOOST_FOREACH (std::string& v, m|map_values) {
    if (v == "keys")
        v = "values";
}

BOOST_CHECK( m[12] == "hello" );
BOOST_CHECK( m[4]  == "map" );
BOOST_CHECK( m[99] == "values" );

9.27 matches

  • Header: <pstade/oven/matches.hpp>; not included by <pstade/oven/ranges.hpp>
  • Valid expression: biRng|matches(re) or biRng|matches(re,flag)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::regex_iterator.

9.28 memoized

memoized returns a range whose values are cached for speed, preparing for repeated dereferences:

std::stringstream ss;
ss << "hello, memoized!";

::very_complicated_algorithm(
    oven::stream_input<char>(ss)
        | memoized
        | directed
        | indirected
        | sorted
        | memoized
);
  • Header: <pstade/oven/memoized.hpp>
  • Valid expression: rng|memoized and rng|memoized(tb), where tb is a named memo_table object.
  • Precondition: boost::range_value of rng is CopyConstructible. tb has longer lifetime than the use of returned range.
  • Returns: A Forward Range whose values are memoized. [12]
[12]memoized can return a Forward Range even if the base range is a Single Pass Range.

9.29 merged

merged combines two sorted ranges into a single sorted range:

std::string A1("abbbfH");
std::string A2("ABbCDFFhh");
std::string AA("aAbbbBbCDfFFHhh");
BOOST_CHECK( oven::equals(A1|merged(A2, &::lt_nocase), AA) );
  • Header: <pstade/oven/merged.hpp>
  • Valid expression: rng1|merged(rng2) and rng1|merged(rng2,pred)
  • Precondition: rng1 and rng2 are sorted.
  • Returns: A constant range up to Forward Range which behaves as if they were made by std::merge.

9.30 permuted

  • Header: <pstade/oven/permuted.hpp>
  • Valid expression: rndRng|permuted(rng)
  • Precondition: rng is a range of the indices of rndRng.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::permutation_iterator.

9.31 pointed

pointed provides an interface to have a conversation with legacy APIs:

std::string const src("hello, pointed");
std::vector<char> vec;
vec.resize(oven::distance(src) + 1);
std::strcpy(boost::begin(vec|pointed), src.c_str());
BOOST_CHECK(( oven::equals(vec|null_terminated, src) ));
  • Header: <pstade/oven/pointed.hpp>
  • Valid expression: vec|pointed
  • Precondition: vec is a template instantiation of std::vector.
  • Returns: [&*boost::begin(vec),&*boost::begin(vec)+oven::distance(vec)) if vec is not empty; otherwise, [0,0).

9.32 popped

  • Header: <pstade/oven/popped.hpp>
  • Valid expression: fwdRng|popped
  • Precondition: boost::empty(fwdRng) == false
  • Returns: [boost::begin(fwdRng),boost::next(boost::begin(fwdRng),oven::distance(fwdRng)-1))

9.33 prepended

  • Header: <pstade/oven/prepended.hpp>
  • Valid expression: rng|prepended(v)
  • Returns: A range which behaves as if it were as_single(v)|jointed(rng).

9.34 reversed

9.35 rotated

  • Header: <pstade/oven/rotated.hpp>
  • Valid expression: fwdRng|rotated(fun)
  • Returns: [fun(fwdRng),boost::end(fwdRng))|jointed([boost::begin(fwdRng),fun(fwdRng)))

9.36 scanned

scanned is similar to oven::accumulate, but returns a range of successive reduced values from the base range:

int const src[] = { 1,2,3,4,5 };
std::string null;

BOOST_FOREACH (std::string str, src|scanned(null, &::stringize)) {
    std::cout << "\"" << str << "\" ";
}
// outputs: "" "1" "12" "123" "1234" "12345"
  • Header: <pstade/oven/scanned.hpp>
  • Valid expression: rng|scanned(init,fun), where the type of init is DefaultConstructible, CopyConstructible and CopyAssignable.
  • Precondition: fun(s,r) is a valid expression, where the type of s is the same as init and r is the iterator dereference of rng.
  • Returns: A range up to Forward Range which behaves as if it were made by std::partial_sum.

9.37 seconds

  • Header: <pstade/oven/seconds.hpp>
  • Valid expression: rng|seconds
  • Returns: A range which behave as if it were rng|map_values.

9.38 set_cap

  • Header: <pstade/oven/set_cap.hpp>
  • Valid expression: rng1|set_cap(rng2) and rng1|set_cap(rng2,pred)
  • Precondition: rng1 and rng2 are sorted.
  • Returns: A constant range up to Forward Range which behaves as if they were made by std::set_intersection.

9.39 set_cup

  • Header: <pstade/oven/set_cup.hpp>
  • Valid expression: rng1|set_cup(rng2) and rng1|set_cup(rng2,pred)
  • Precondition: rng1 and rng2 are sorted.
  • Returns: A constant range up to Forward Range which behaves as if they were made by std::set_union.

9.40 set_delta

  • Header: <pstade/oven/set_delta.hpp>
  • Valid expression: rng1|set_delta(rng2) and rng1|set_delta(rng2,pred)
  • Precondition: rng1 and rng2 are sorted.
  • Returns: A constant range up to Forward Range which behaves as if they were made by std::set_symmetric_difference.

9.41 set_minus

  • Header: <pstade/oven/set_minus.hpp>
  • Valid expression: rng1|set_minus(rng2) and rng1|set_minus(rng2,pred)
  • Precondition: rng1 and rng2 are sorted.
  • Returns: A constant range up to Forward Range which behaves as if they were made by std::set_difference.

9.42 shared

shared, taking a pointer to heap-allocated range, makes a range whose iterators manage its lifetime:

BOOST_FOREACH (char ch, std::string("dangling")|identities) {
    // will crash; 'std::string' object doesn't exist anymore. 
    std::cout << ch;
}

BOOST_FOREACH (char ch, new std::string("ok")|shared|identities) {
    // works fine.
    std::cout << ch;
}
  • Header: <pstade/oven/shared.hpp>
  • Valid expression: p|shared
  • Precondition: boost::shared_ptr is constructible from p.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in shared_container_iterator.

You can find a more elaborate example at <pstade/oven/sorted.hpp>.

9.43 sliced

sliced [13] provides the column view of the base range:

int const answer[] = { 2,6,10,14 };
BOOST_CHECK( oven::equals(answer,
    counting(0, 16)|sliced(2, 4)
) );
  • Header: <pstade/oven/sliced.hpp>
  • Valid expression: rndRng|sliced(start,stride)
  • Precondition: d == 0 || d % stride == 0 and 0 <= start && start < stride, where d = oven::distance(rndRng);
[13]This name is different from Range Library Proposal's, which is the role of advanced or window.

9.44 string_found

  • Header: <pstade/oven/string_found.hpp>
  • Valid expression: rng|string_found(finder)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::algorithm::find_iterator.

9.45 string_split

  • Header: <pstade/oven/string_split.hpp>
  • Valid expression: rng|string_split(finder)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::algorithm::split_iterator.

9.46 taken

taken, applied to the base range, returns the prefix of the range of length n:

std::string src("hello, taken!");
std::string ans("hello");
BOOST_CHECK( oven::equals(src|taken(7)|taken(5), ans) );
  • Header: <pstade/oven/taken.hpp>
  • Valid expression: rng|taken(n)
  • Precondition: 0 <= n
  • Returns: A range up to Forward Range which behaves as if it were [boost::begin(rng),boost::next(boost::begin(rng),std::min(n, distance(rng)))).

9.47 taken_while

taken_while, applied to a Predicate and the base range, returns the longest prefix (possibly empty) of the range of elements that satisfy Predicate:

std::string src("11111234516313!");

BOOST_CHECK( oven::equals(
    src|taken_while(lambda::_1 == '1'),
    std::string("11111")
) );
  • Header: <pstade/oven/taken_while.hpp>
  • Valid expression: rng|taken_while(pred)
  • Returns: A range up to Forward Range which behaves as if it were [boost::begin(rng),oven::find_if(rng,not_(pred)))

9.48 tokenized

9.49 transformed

9.50 uniqued

9.51 unzipped

unzipped reverses zipped:

std::cout <<
    (
        assign::list_of
            (boost::make_tuple(1,2))
            (boost::make_tuple(2,3))
            (boost::make_tuple(3,4))
            | unzipped
    );

// output> ({1,2,3} {2,3,4})
  • Header: <pstade/oven/unzipped.hpp>
  • Valid expression: tuples|unzipped, where tuples is a range whose value_type is boost::tuple.
  • Returns: A boost::tuple whose elements are unzipped ranges.

9.52 utf8_decoded

  • Header: <pstade/oven/utf8_decoded.hpp>
  • Valid expression: biRng|utf8_decoded
  • Returns: A Bidirectional Range whose iterators behave as if they were the original iterators wrapped in boost::u8_to_u32_iterator.

9.53 window

  • Header: <pstade/oven/window.hpp>
  • Valid expression: fwdRng|window(n,m)
  • Returns: [boost::next(boost::begin(rng),n),boost::next(boost::begin(rng),m)).

9.54 with_position

  • Header: <pstade/oven/with_position.hpp>
  • Valid expression: rng|with_position
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::spirit::position_iterator.

9.55 xpressive_matches

  • Header: <pstade/oven/xpressive_matches.hpp>; not included by <pstade/oven/ranges.hpp>
  • Valid expression: biRng|xpressive_matches(re) or biRng|xpressive_matches(re,flag)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::xpressive::regex_iterator.

9.56 xpressive_tokenized

  • Header: <pstade/oven/xpressive_tokenized.hpp>; not included by <pstade/oven/ranges.hpp>
  • Valid expression: biRng|xpressive_tokenized(re) or biRng|xpressive_tokenized(re,subMatches,flag)
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::xpressive::regex_token_iterator.

9.57 zipped

zipped takes a tuple of ranges and returns a range of corresponding tuples. If one input range is short, excess elements of the longer range are discarded:

std::cout <<
    (
        boost::make_tuple(
            assign::list_of(1)(2)(3),
            assign::list_of(2)(3)(4)
        )
            | zipped
    );

// output> {(1 2),(2 3),(3 4)}
  • Header: <pstade/oven/zipped.hpp>
  • Valid expression: rngs|zipped, where rngs is a boost::tuple of ranges.
  • Returns: A range whose iterators behave as if they were the original iterators wrapped in boost::zip_iterator.

9.58 zipped_with

zipped_with generalises zipped by zipping with the Function Object, given as the first argument, instead of a tupling:

int xs[]  = { 0, 1, 2, 3, 4, 5, 6 };
int ys[]  = { 1, 6, 1, 2, 7, 8, 3 };
int ans[] = { 1, 7, 3, 5,11,13, 9 };

BOOST_CHECK( oven::equals(
    boost::tie(xs, ys)|zipped_with(::plus()),
    ans
) );
  • Header: <pstade/oven/zipped_with.hpp>
  • Valid expression: rngs|zipped_with(rfun), where rngs is a boost::tuple of ranges.
  • Precondition1: The arity of rfun is the length of rngs.
  • Returns: A range whose values are zipped by using rfun.

10 Output Iterator Adaptors

10.1 to_counter

to_counter takes an initial count and increments it every output. adapted_to/to_base can extract the result of the counting:

int const rng[] = { 0,0,1,1,2,3,3,3,4,4,4,4,4,5,5 };
int i = oven::copy(rng|uniqued, oven::to_counter(0))|to_base;
BOOST_CHECK( i == 6 );

BOOST_CHECK( 7 == oven::adapted_to<int>(oven::unique_copy(rng, oven::to_counter(1))) );
  • Header: <pstade/oven/to_counter.hpp>
  • Valid expression: to_counter(i), where i is an Incrementable.
  • Returns: An OutputIterator which counts the output.

10.2 to_function

to_function returns an OutputIterator which is a port of boost::function_output_iterator with some workarounds.

  • Header: <pstade/oven/to_function.hpp>
  • Valid expression: to_function(fun)
  • Returns: An OutputIterator which behaves as if it were boost::function_output_iterator.

10.3 to_stream

to_stream returns an OutputItertor which is a shorthand version of std::ostream_iterator. It needs no an explicit template parameter to specify the value_type to output, but one precondition below must be kept. Generally, the boost::iterator_reference of InputIterator must be the same as value_type of it except for reference qualifier.

  • Header: <pstade/oven/to_stream.hpp>
  • Valid expression: to_stream(os)
  • Precondition: The type to be assigned to dereference of an iterator which to_stream returns must be an OutputStreamable.
  • Returns: An OutputIterator which behave as if it were std::ostream_iterator.

10.4 to_utf8_encoder

  • Header: <pstade/oven/to_utf8_encoder.hpp>
  • Valid expression: to_utf8_encoder(oit), where oit is an OutputIterator.
  • Returns: An OutputIterator which behave as if it were boost::utf8_output_iterator.

11 Extending Boost.Range

The extension way of Boost.Range seems to assume the future C++ ability decltype. For now, it is not practical to apply the way to a large library something like MFC. Oven provides yet another extension way, which is similar to Conceptualizing the Range-Based for Loop proposal to simplify the Boost.Range one:

namespace Foo {

    template< class T >
    struct Pair
    {
        T first, last;
    };

} // namespace Foo

namespace pstade_oven_extension {

    template< class T >
    struct Range< Foo::Pair<T> >
    {
        // X == Foo::Pair<T>
        template< class X >
        struct associate
        {
            typedef T mutable_iterator;
            typedef T constant_iterator;
        };

        // if X is not const, Iterator == mutable_iterator;
        // otherwise, Iterator == constant_iterator.
        template< class Iterator, class X >
        Iterator begin(X& x)
        {
            return x.first;
        }

        template< class Iterator, class X >
        Iterator end(X& x)
        {
            return x.last;
        }
    };

} // namespace pstade_oven_extension

PSTADE_OVEN_EXTENSION_OF_TEMPLATE((Foo)(Pair), (class))
// PSTADE_OVEN_EXTENSION_OF_TEMPLATE((Foo)(Pair), 1) // also ok.
  1. Specialize ::pstade_oven_extension::Range.
  2. Define template associate, begin and end.
  3. Call the macro, in global namespace, to act as a bridge between Oven and Boost.Range.

Note that the const overloads can be sometimes omitted like above. Also, Range has the second template parameter for pstade::enable_if. boost::size is automatically extended by Oven.

  • Header: <pstade/oven/extension.hpp>
  • Valid expression1: PSTADE_OVEN_EXTENSION_OF_TYPE(X)
  • Valid expression2: PSTADE_OVEN_EXTENSION_OF_TEMPLATE(X,N), where N is the number of template arguments. Only valid if all template arguments are typenames.
  • Valid expression3: PSTADE_OVEN_EXTENSION_OF_TEMPLATE(X,S), where S is a sequence of template arguments. Must be used when integral or template template parameters are present.
  • Precondition: X is a Boost.Preprocessor Sequence of type name.

12 MFC/ATL Extension

Oven provides Boost.Range support for MFC/ATL collection and string types. See Oven Range MFC/ATL Extension.

14 Release Notes

14.1 Version 0.90.0

  • Released initial version.

14.2 Version 0.90.1 - 0.90.6

  • Updated this document.
  • Implemented Range Algorithms.
  • Added some Ranges and Range Adaptors.
  • Added some Range Adaptors.
  • Changed the header of permuted.
  • Changed the header of pointed.
  • Changed a valid expression of zipped.
  • Changed checked to throw exception.
  • Renamed found to string_found.
  • Changed the header of Range Algorithms.
  • Added base_iterator.
  • Added some Range Adaptors.
  • Renamed accumulated to scanned.
  • Added workaround for Standard Library Defect #198.
  • Changed constants semantics, and added always instead.
  • Changed utf8_decoded valid expression.
  • shared accepts auto_ptr.

14.3 Version 0.90.7 - 0.90.9

  • Added matched, xpressive_matched and xpressive_tokenized.
  • Renamed base_iterator to to_base.
  • Renamed copied adaptor to copied_to.
  • Added concatenated.
  • Renamed copied_to to copied_out.
  • Fixed a bug of transformed and concatenated.
  • Added generated.
  • No longer supports function types as rfun.
  • Changed utf8_decoded valid expression.

14.4 Version 0.91.0 - 0.91.3

  • Added Output Iterator Adaptors.
  • Renamed generated to generation.
  • Renamed positioned to with_position.
  • Renamed matched to matches.
  • Renamed xpressive_matched to xpressive_matches.
  • Added Extending Boost.Range.
  • Rejected out_placed and sorted.
  • Added literal_range and c_str_range.
  • null_terminated no longer supports c-string.
  • Added as_single to single_range's valid expressions.
  • Added begins/ends.
  • Added merged, set_cup, set_cap, set_minus and set_delta.
  • Added rotated.
  • Removed stridden and changed effects of sliced.
  • Added through_window.
  • Added popped.
  • Changed the valid expression of array_protect_range and literal_range.
  • Added to_function.
  • Renamed shifted to advanced.

14.5 Version 0.91.4 - 0.91.9

  • Added any_range.
  • Removed popped and changed the valid expression of advanced.
  • Removed generation as adaptor and added it as range.
  • taken and taken_while supports Single Pass Range.
  • Added iterate_range.
  • Added adjacent_transformed.
  • Added popped_back.
  • Changed counting_range valid expressions.
  • Renamed repeated to cycled.
  • Added repeat_range.
  • Renamed popped_back to popped.
  • Changed the valid expressions of zipped and zipped_with.
  • Ported to VC++7.1 SP1.
  • Added MFC/ATL support.

14.6 Version 0.92.0 - 0.92.3

  • Renamed counting_range to count_range, and added a valid expression.
  • Removed the valid expression advanced(d).
  • Renamed tie to pack.
  • Added boost::result_of support to range-based algorithms.
  • Renamed Extending Boost.Range macros.
  • Renamed adaptor_to to adapted_to.

14.7 Version 0.93.0

  • Changed the names of some functions and headers.
  • Added delimited.

14.8 Version 0.93.1

  • Renamed begins/ends to begin/end.
  • adjacent_transformed rejects empty range.
  • Changed template parameter of any_range.
  • Replaced regularized with regular.
  • Removed to_regularized_function.
  • scanned range contains the init as the first element.

14.9 Version 0.93.2

  • taken and taken_while behave lazily.
  • taken and taken_while now return only up to ForwardRange.
  • dropped and taken accept n which is larger than the distance.
  • Removed null_terminated.
  • as_c_str accepts a range.
  • zipped and zipped_with accept any tuple.
  • Removed generation_copied.
  • Added shared_regular and innumerable.

14.10 Version 0.93.3

  • Fixed a bug of generation.
  • Added front and back.
  • Added recursion.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Japan Japan
I am worried about my poor English...

Comments and Discussions

 
-- There are no messages in this forum --