Output iterator adapter to count but not copy

Question

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?

Voting to close as a resource request but you may want [`boost::counting_iterator`](http://www.boost.org/doc/libs/1_50_0/libs/iterator/doc/counting_iterator.html) — NathanOliver, Aug 02 '16 at 11:47
Your question is a little unclear: you want to know how many elements would contain the intersection of 2 sets without computing the intersection? — rocambille, Aug 02 '16 at 11:48
@wasthishelpful yes, in my example of set_difference but I am looking for a generic Ouput iterator solution for any such algorithm. — T33C, Aug 02 '16 at 11:49
@NathanOliver, boost::counting_iterator doesn't do what I am asking. Unless I misunderstood the documentation. What do you mean by resource request? I have already attempted to implement such an iterator with no luck. I might post my attempt later when I'm not bound to my mobile. — T33C, Aug 02 '16 at 12:13

ecatmur · Answer 1 · 2016-08-02T12:19:18.013

4

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);

edited Aug 02 '16 at 12:19

answered Aug 02 '16 at 12:13

ecatmur

152,476
27
293
366

Looks promising but code doesn't compile in VS2015U2 with Boost 1.59. Attempting to reference a deleted function. I replaced with a functor which compiles but counts 6 instead of 3. Weird! I'm still investigating. Thanks for your suggestion. – T33C Aug 02 '16 at 12:45
You have made substantial edits since I commented so trying these first which may invalidate my comment above. Thanks for your help. – T33C Aug 02 '16 at 12:49
Lambda solution still fails. The counting_output_operator works but depends on the algorithm returning the output iterator otherwise the value is not accessible. You have put me on the right track and I will experiment more. – T33C Aug 02 '16 at 12:59
Just return `*this` for `operator*` too, why have another type? – Barry Aug 02 '16 at 13:05
@T33C Don't worry about a return construct the iterator *outside* the algorithm pass it in as an L-value: `const auto arr = {0, 1, 2, 3}; counting_output_iterator it; copy(cbegin(arr), cend(arr), it); cout << it.value << endl;` – Jonathan Mee Aug 02 '16 at 13:20

score 0 · Accepted Answer · answered Aug 02 '16 at 14:15

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;
}

Output iterator adapter to count but not copy

2 Answers2

Linked