There are various STL algorithms that rely on an output iterator to store the result of the algorithm.
For example, std::set_intersection
will store all the common elements between two sorted ranges in an Output iterator that is then post incremented per element outputted.
Sometimes, I am not interested in the actual elements but only the number of output elements. In such cases it is a waste of memory and performance to copy the elements. Is there an iterator adapter that I can use to count and avoid the copy of the elements? If not can you suggest a generic implementation of such an adapter?
Boost's Function Output Iterator can do what you want:
std::size_t count = 0u;
int arr[]{0, 1, 2, 3};
std::copy(std::begin(arr), std::end(arr),
boost::make_function_output_iterator([&](auto const&) { ++count; }));
assert(count == 4u);
The only issue is that you have to declare the count variable outside the iterator, because there's no way to extract the stored function object from a boost::function_output_iterator
(and also no way to extract the closure values from a lambda, even if you got past that hurdle). If you want to be able to write one-liners, you'll have to write the iterator class yourself, but it's not a huge amount of code; for example:
class counting_output_iterator {
public:
using iterator_category = std::output_iterator_tag;
using value_type = void;
using difference_type = void;
using pointer = void;
using reference = void;
std::size_t value = 0u;
struct output_proxy {
output_proxy(std::size_t& value) : m_value(value) { }
template<class T> output_proxy& operator=(T const&) {
++m_value;
return *this;
}
std::size_t& m_value;
};
output_proxy operator*() { return output_proxy(value); }
counting_output_iterator& operator++() { return *this; }
counting_output_iterator& operator++(int) { return *this; }
};
Usage:
int arr[]{0, 1, 2, 3};
auto const count = std::copy(std::begin(arr), std::end(arr),
counting_output_iterator{}).value;
assert(count == 4u);
Thanks to a lot of help from @ecatmur answer and comments, I have the following solution, which I invite comments. I had hoped to get the boost::make_function_output_iterator
working but it seems that there is a bug in the library which fails to define the assignment operator.
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <cassert>
class counting_output_iterator
{
public:
counting_output_iterator& operator=(const counting_output_iterator&) { return *this; };
explicit counting_output_iterator(std::size_t& count) : m_count(count) {}
template<typename T> void operator=(const T&) {}; //NULL op
using iterator_category = std::output_iterator_tag;
using value_type = void;
using difference_type = void;
using pointer = void;
using reference = void;
counting_output_iterator& operator*() { return *this; }
counting_output_iterator& operator++() { ++m_count; return *this; }
std::size_t& m_count;
};
int main(int, char*[])
{
std::vector<int> arr{ 1,2,3,4 };
std::size_t count = 0;
std::copy(std::begin(arr), std::end(arr), counting_output_iterator{ count } );
assert(count == 4u);
return 0;
}