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()
andclear()
instead of conversion tosize_t
and assignment fromnullptr
? - 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)?