Extending a STL algorithm

[Daleth]

This is more of a critique request.

I wrote a version of find_all() which searches through containers for matches and returns another container that holds iterators pointing to each match. When I compared what I wrote to what the authors of Professional C++ wrote, I found the two find_all() functions to be very different. I would like your help in comparing my and their functions. Here they are:

//Mine
template<typename Iterator, typename Predicate>
std::list<Iterator> find_all
    (Iterator front, Iterator back, const Predicate& match)
{
    std::list<Iterator> toreturn;
    for(; front != back; ++front) if(*front == match) toreturn.push_back(front);
    return toreturn;
}

//Verbatim from Professional C++
template <typename InputIterator, typename Predicate>
vector<InputIterator>
find_all(InputIterator first, InputIterator last, Predicate pred)
{
    vector<InputIterator> res;
    while(true) {
        // Find the next match in the current range.
        first = find_if(first, last, pred);
        // check if find_if failed to find a match
        if (first == last) {
            break;
        }
        // Store this match.
        res.push_back(first);
        // Shorten the range to start at one past the current match
        ++first;
    }
    return res;
}

I appreciate any responses.

[cire]

A "Predicate" is generally a function you call to to determine if a match occurs. It is not something to compare to elements.

Your functions are so different because they do different things.

[JLBorges]

I would prefer not to hard code the type of the container holding the result. Something like this:

#include <algorithm>

template < typename INPUT_ITERATOR, typename PREDICATE, typename OUTPUT_ITERATOR >
void find_all_iterators( INPUT_ITERATOR begin, INPUT_ITERATOR end,
                         PREDICATE predicate, OUTPUT_ITERATOR dest )
{
    while( ( begin = std::find_if( begin, end, predicate ) ) != end )
    {
        *dest = begin ;
        ++begin ;
        ++dest ;
    }
}

[Daleth]

@cire:
Ah, thanks for pointing that out. I totally forgot that the last argument in STL algorithms are usually for function calls.

@JLBorges:
Makes sense, and it's very similar to other STL algorithm functions that takes output iterators as an argument.

Thanks guys. Now that you helped me realize my function doesn't even do the same thing at all, I'll revise it.

[kbw]

Don't you need an inserter on that output iterator?

[vlad from moscow]

I would declare the algorithm the following way

template < typename INPUT_ITERATOR, typename PREDICATE, typename OUTPUT_ITERATOR >
OUTPUT_ITERATOR find_all_iterators( INPUT_ITERATOR begin, INPUT_ITERATOR end,
PREDICATE predicate, OUTPUT_ITERATOR dest );


In this case it can be simply calculated for example how many iterators were found.