Add double-bounded version of outputting algorithms

[Daryle Walker]

(I thought there was an algorithms component. But I don't see it, so I left the "Component" field as "None.")

Many of the standard algorithms transfer data from one sequence to another, using iterators to define the bounds of said sequences. Parameters for such sequences always include the beginning iterator. But, frequently, only the first sequence has its ending iterator also passed; all the other sequences are assumed to be at least as long as the first one. Confirming this is essential for robustness, and sometimes determining the length of a sequence relative to another in advance is non-trivial. (It may involve manual counting through iterating over the whole sequence, which could be slow. And it could be devastating if one of the measured sequences is single-pass.)

The alternative is to make algorithms that take both the beginning and ending iterators for every sequence and automatically stop as soon as any of them end. Obviously, this cannot work with output iterators, and such sequences need to work with forward (or above) iteration instead. For instance, std::copy can go from:

template < typename InIter, typename OutIter >
OutIter  copy( InIter b, InIter e, OutIter o )
{ while ( b != e )  *o++ = *b++; return o; }

to:

template < typename InIter, typename ForIter >
pair<bool, ForIter>  copy_db( InIter sb, InIter se, ForIter db, ForIter de )  {
    while ( sb != se && db != de )
        *db++ = *sb++;
    return make_pair( sb == se, db );
}

The first sequence may be a single-pass input-iterator, so it can only return a Boolean flag if it reached its end. The second sequence must be (at least) a forward-iterator, so a copy of the updated iterator can be returned.

Examples from the (C++ 2003) standard that could use such adaptations are: equal, mismatch, copy, copy_backward, transform, swap_ranges, replace_copy, replace_copy_if, remove_copy, remove_copy_if, unique_copy, reverse_copy, rotate_copy, merge, set_union, set_intersection, set_difference, set_symmetric_difference, inner_product, partial_sum, and adjacent_difference. (Some return types may vary.)

[viboes]

I think that nobody can take care of your ticket, so I propose you to close it and open the debate on the ML.

[Neil Groves]

Currently I have provided better alternatives than the two iterator versions of algorithms. I have commented in the Boost.Range documentation that it is better to use the functions under the boost/range/algorithm_ext folder to achieve the same job.

Your copy example can be achived in a superior manner by using boost::overwrite(source, target); However a superior idiom is frequently to use my push_back algorithm. For example:

#include <boost/range/algorithm_ext/push_back.hpp> #include <boost/range/adaptor/reversed.hpp> #include <vector>

int main() {

... :TODO: populate a source vector snipped for emphasis of the relevant concept std::vector<int> v; boost::push_back(v, source | boost::adaptors::reversed); return 0;

}

This will populate the vector v in an efficient manner with the range of information in 'source' in reverse order. It is my experience that I very rarely miss the target iterator versions of algorithms. The main occasion I still use them is for output stream iterators, which is typically a safe idiom.

There has been discussion on the ML in the past about the formalisation of some 'Sink' Concepts, but so far I have been surprised by the satisfactory nature of the current functions in algorithm_ext. I welcome peoples experiences, and particularly their use cases for sinks, output iterators or other target concepts.

[Neil Groves]

I consider this situation to have been resolved with a superior solution to the one proposed by the introduction of Boost.Range algorithms and algorithm extensions in 1.43.