3
\$\begingroup\$

I need a copy_if_max() function, i.e. copy all the elements in an input range that are equal to the max in that range. The most obvious implementation does two passes over the data:

template<class InputIt, class OutputIt>
OutputIt copy_if_max2(InputIt first, InputIt last, OutputIt dst)
{
    using T = typename InputIt::value_type;
    auto m = *std::max_element(first, last);
    return std::copy_if(first, last, dst, [&](T const& elem) {
        return elem >= m; // NOTE: not elem == m, because we use equivalence, not equality
    });
} 

This is all nice and dandy (\$O(N)\$ complexity). However, for true input ranges, the two passes over the input data are a no go.

Note also that the maximum of the input range is defined in terms of an operator< that defines an equivalence relation, and not necessarily an equality relation. The suggested single-pass answer by @Yuushi would therefore not work.

I've come up with what I call a clearable back_inserter, that will reset the output range whenever the max is updated. I do that by having an assignment operator that takes a nullptr_t argument (which takes precedence in overload resolution over all other pointers, so even if the actual data would contain a nullptr, this would not match!). Furthermore, there is an implicit conversion to std::size_t so I can detect the underlying output container size.

template<class Container>
class clearable_back_insert_iterator
: 
    public std::iterator< std::output_iterator_tag, void, void, void, void >
{
private:
    Container* c_;

public:    
    using self_t = clearable_back_insert_iterator;    
    using value_type = typename Container::value_type;

    clearable_back_insert_iterator(Container& c): c_(&c) {}

    operator std::size_t() { return c_->size(); }

    self_t& operator=(value_type const& v)
    {
        std::cout << "push_back \n";
        c_->push_back(v);    
        return *this;
    }

    self_t& operator=(std::nullptr_t)
    {
        std::cout << "clear \n";
        c_->clear();
        return *this;
    }

    self_t& operator*() { return *this; }
    self_t& operator++() { return *this; }
    self_t& operator++(int) { return *this; }
};

template<class Container>
clearable_back_insert_iterator<Container> clearable_back_inserter(Container& c)
{
    return clearable_back_insert_iterator<Container>(c);    
}

This allows me to write a single-pass copy_if_max1() that uses a clearable_back_inserter and a std::transform():

template<class InputIt, class OutputIt>
OutputIt copy_if_max1(InputIt first, InputIt last, OutputIt dst)
{
    using T = typename InputIt::value_type;
    auto m = std::numeric_limits<T>::min();
    std::transform(first, last, dst, [&](T const& elem) {
        if (dst == 0) {             // size()
            m = elem;
            return dst = elem;      // push_back()
        }
        if (m <= elem) {
            if (m != elem) {
                m = elem;
                dst = nullptr;      // clear()
            }
            dst = elem;             // push_back()
        }
        return dst;        
    });
    return dst;
}    

Live example. I realize that this one-pass version does more copying because it will copy all elements of the input range as long as they match the intermediate maximum, only to be cleared whenever the max is updated.

My questions:

  • Which points in this design would you critique?
  • Do you think clearable back_inserters are a good and reusable concept?
  • Should I use named members size() and clear() instead of conversion to size_t and assignment from nullptr?
  • Does Boost have some other alternatives (filter_iterator perhaps?)
  • Is it better to avoid the complications altogether and use the two-pas version copy_if_max2() (perhaps with a full copy of the input to allow multi-passes)?
\$\endgroup\$
1
\$\begingroup\$

I think you're overcomplicating the solution a bit. Since you're making copies of what is the maximum in the range, all you need is something that keeps a value to store the current max, and another which keeps a count of the number of maximum values that have been found in the input data. For example:

#include <iterator>

template <typename InputIter, typename OutputIter>
void copy_if_max(InputIter begin, InputIter end, OutputIter out_begin)
{
    std::size_t count = 1;
    typedef typename std::iterator_traits<InputIter>::value_type T;

    if(begin == end) return;

    T current_max = *begin;
    ++begin;

    while(begin != end) {
        if(*begin > current_max) {
            current_max = *begin;
            count = 1;
        } 
        else if(*begin == current_max) {
            ++count;
        }
        ++begin;
    }

    for(std::size_t i = 0; i < count; ++i) {
        *out_begin++ = current_max;
    }
}

Note that this solution also uses std::iterator_traits<T>, which you should be using instead of relying on the InputIterator passed having a nested value_type typedef (which will of course be false if it is passed a T*, for example).

\$\endgroup\$
  • \$\begingroup\$ thanks, this would be a good solution (and therefore +1) if the input range contains non-class types. However, (and I didn't mention this in my original question, sorry!) the maximum over the input range is defined in terms of an equivalence relation operator<, e.g. the age of a Person class. The copy part of the algorithm needs to also copy the other parts of the input range, not just the member that defines the max. Do you have ideas to accomodate this more generalized behavior? \$\endgroup\$ – TemplateRex Aug 4 '13 at 10:05
  • \$\begingroup\$ @TemplateRex Ah, fair enough - that changes it somewhat. Let me have a think about it... \$\endgroup\$ – Yuushi Aug 4 '13 at 13:48
  • \$\begingroup\$ @TemplateRex I can't really see any problems with your solution, and having thought about it more, I don't think I'm going to come up with anything better. As you've mentioned, if it really is an input iterator, the two pass algorithm will be a no go. I think your design is in general reasonable (although I'm not a fan of implicit conversions). \$\endgroup\$ – Yuushi Aug 5 '13 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.