Filtered Range-Based For Loops

[JayhawkZombie]

I found myself recently curious as to why the standard library doesn't have a way to filter values from a range-based for loop and decided to have a shot at it.

I've only tested it for POD's, but is this the way I should be doing this, or is there a better way to accomplish this?

FilterIterators.h

template<typename Container_t, typename UnaryPredicate>
class IterateIfIterator
{
public:
  IterateIfIterator(typename Container_t::iterator curIter, typename Container_t::iterator endIter,
                    const UnaryPredicate &Func);
  bool operator == (const IterateIfIterator &Iter);
  bool operator != (const IterateIfIterator &Iter);
  typename Container_t::value_type& operator*();
  IterateIfIterator operator++();

private:

  typename Container_t::iterator m_EndIter;
  typename Container_t::iterator m_CurIter;

  const UnaryPredicate m_Predecate;

};

template<typename Container_t, typename UnaryPredicate>
class IterateIf
{
public:
  IterateIf(Container_t &container, const UnaryPredicate&Func);
  IterateIfIterator<Container_t, UnaryPredicate> begin() const;
  IterateIfIterator<Container_t, UnaryPredicate> end() const;

private:

  Container_t &m_Container;
  typename Container_t::iterator m_Begin;
  typename Container_t::iterator m_End;
  typename Container_t::iterator m_CurIter;

  const UnaryPredicate m_Predecate;

};

template<typename Container_t, typename UnaryPredicate>
IterateIf<Container_t, UnaryPredicate> FilterIfNot(Container_t &container, const UnaryPredicate &Func);

#include "FilterIterators.inl" 

FilterIterators.inl

template<typename Container_t, typename UnaryPredicate>
IterateIfIterator<Container_t, UnaryPredicate>::IterateIfIterator(typename Container_t::iterator curIter, typename Container_t::iterator endIter, const UnaryPredicate &Func)
  : m_Predecate(Func)
  , m_CurIter(curIter)
  , m_EndIter(endIter)
{ }

template<typename Container_t, typename UnaryPredicate>
IterateIfIterator<Container_t, UnaryPredicate> IterateIfIterator<Container_t, UnaryPredicate>::operator++()
{
  ++m_CurIter;

  while (m_CurIter != m_EndIter && !m_Predecate(*m_CurIter))
    ++m_CurIter;

  return IterateIfIterator(m_CurIter, m_EndIter, m_Predecate);
}

template<typename Container_t, typename UnaryPredicate>
typename Container_t::value_type& IterateIfIterator<Container_t, UnaryPredicate>::operator*()
{
  return *m_CurIter;
}

template<typename Container_t, typename UnaryPredicate>
bool IterateIfIterator<Container_t, UnaryPredicate>::operator!=(const IterateIfIterator &Iter)
{
  return ( m_CurIter != Iter.m_CurIter );
}

template<typename Container_t, typename UnaryPredicate>
bool IterateIfIterator<Container_t, UnaryPredicate>::operator==(const IterateIfIterator &Iter)
{
  return ( m_CurIter == Iter.m_CurIter );
}

template<typename Container_t, typename UnaryPredicate>
IterateIf<Container_t, UnaryPredicate>::IterateIf(Container_t &container, const UnaryPredicate &Func)
  : m_Predecate(Func), m_Container(container)
  , m_End(container.end()), m_Begin(container.begin()), m_CurIter(container.begin())
{
  size_t i = 0;
  for (const auto & it : container) {
    if (m_Predecate.operator()(it)) break;
    i++;
  }

  if (i < container.size() - 1)
    m_Begin = m_Container.begin() + i;
  else
    m_Begin = m_End;

  m_CurIter = m_Begin;
}

template<typename Container_t, typename UnaryPredicate>
IterateIfIterator<Container_t, UnaryPredicate> IterateIf<Container_t, UnaryPredicate>::end() const
{
  return IterateIfIterator<Container_t, UnaryPredicate>(m_Container.end(), m_End, m_Predecate);
}

template<typename Container_t, typename UnaryPredicate>
IterateIfIterator<Container_t, UnaryPredicate> IterateIf<Container_t, UnaryPredicate>::begin() const
{
  return IterateIfIterator<Container_t, UnaryPredicate>(m_Begin, m_End, m_Predecate);
}

template<typename Container_t, typename UnaryPredicate>
IterateIf<Container_t, UnaryPredicate> FilterIfNot(Container_t &container, const UnaryPredicate &Func)
{
  return IterateIf<Container_t, UnaryPredicate>(container, Func);
}

HelperFunctors.h

template<typename T>
struct IsLess
{
  IsLess(T CompVal);
  bool operator ()( T ToComp ) const;

  const T compVal;
};

#include "HelperFunctors.inl" 

HelperFunctors.inl

template<typename T>
bool IsLess<T>::operator()(T ToComp) const
{
  return ( ToComp < compVal );
}

template<typename T>
IsLess<T>::IsLess(T CompVal)
  : compVal(CompVal)
{ }

And I can use range-based for loops like this:

int main(int argc, char **argv)
{
  std::vector<int> vec{ 1, 3, 6, 3, 14, 29, -12, 9 };

  //Super ugly way
  for (auto & i : IterateIf<std::vector<int>, IsLess<int>>(vec, IsLess<int>(10))) {
    std::cout << i << "\n";
  }

  //Not so ugly way
  for (auto & i : FilterIfNot(vec, IsLess<int>(10))) {
    std::cout << i << "\n";
  }
  return 0;
}

And both print out

1
3
6
3
-12
9

[ne555]

> or is there a better way to accomplish this?

for(auto i: vec)
   if(i<10){
      //...
   }

[Duthomhas]

While true, that little condition inside the loop only works inside a loop (as OP asked, fairly).

It is also nice to have filters on any iterated range.

Have you looked at the Boost.Range library?
http://www.boost.org/doc/libs/release/libs/range/doc/html/index.html

    Less pretty

#include <iostream>
#include <vector>
#include <boost/range/adaptor/filtered.hpp>

int main()
{
  std::vector<int> xs{ 1, 3, 6, 3, 14, 29, -12, 9 };

  for (auto x : xs | boost::adaptors::filtered( []( int n ) { return n < 10; } ))
    std::cout << x << "\n";
}

    More pretty

#include <iostream>
#include <vector>
#include <boost/range/adaptor/filtered.hpp>

int main()
{
  std::vector<int> xs{ 1, 3, 6, 3, 14, 29, -12, 9 };

  // using a function object
  auto less_than_10 = boost::adaptors::filtered( []( int n ) { return n < 10; } );

  for (auto x : xs|less_than_10)
    std::cout << x << "\n";
}

Finally, as per your question about the C++ Standard, the answer is that it has become such a highly-politicized and contested thing that only the most common use for a “for” iteration is now part of the language. It could have been significantly more powerful.

Still, Boost.Range adaptors and the like make up for it nicely.

Hope this helps.

[JayhawkZombie]

@Duthomhas, it does, thank you. I use Boost often because it adds a plethora of utilities, but I hadn't tried using Boost.Range before.

I would say the Boost syntax is a little verbose, but that's perhaps more of a style thing.

I wanted to tackle it as a learning opportunity as well.
Another extensions that a check in a loop wouldn't be adequate for is

auto filtered = FilterIfNot(vec, IsLess<int>(10));
  
for (auto & i : filtered) {
  std::cout << i * i << "\n";
}

for which it behaves as expected.
Thanks for the feedback.

[Duthomhas]

Your code is actually very correct. It is how the Boost and other range type iterators work underneath.

The check in the loop would work just fine, though:

for (auto & i : vec)
  if (i < 10)
    std::cout << (i * i) << "\n";

One other thing, though. The “filter” idiom, by convention, takes a predicate that selects the items to keep. And yes, I know it seems backwards, but both POVs are correct. It just happens that the keep predicate version has become common where the remove predicate version has not. (“Filter” is a functional language idiom that has become common in other languages as well.)

[JayhawkZombie]

That makes sense, the standard library follows the same pattern. A poor naming choice on my part. Something like auto filtered = Filter(vec, IsLess<int>(10)); makes more sense.
Would it make sense to have a version of it that filters out values (without also removing those items from the container) , ie auto filtered = FilterOut(vec, IsGreater<int>(10));.

[Duthomhas]

In the Standard Library it’s called remove_if(), but it is a mutator algorithm and not a accessor algorithm.

[JLBorges]

Boost.Iterator library has facilities to ease the implementation of different custom standard-conforming iterators. It also provides several iterator adapters, one of which is filter_iterator
http://www.boost.org/doc/libs/1_65_1/libs/iterator/doc/index.html#specialized-adaptors

Ideally, an iterator adapter should retain the semantics of the iterator being adapted: for instance, the iterator which adapts a mutable bidirectional iterator should also be a mutable bidirectional iterator.

It can be used in conjunction with facilities in std::experimental::ranges (The change in the core language, introduced in C++17, for the range-based loop is to support some kind of ranges in the Ranges TS.)
http://en.cppreference.com/w/cpp/experimental/ranges

Usage is quite straight-forward; for example, filtering:

#include <iostream>
#include <iterator>
#include <boost/iterator/filter_iterator.hpp>

template < typename ITERATOR, typename ITERATOR_E = ITERATOR > struct range
{
     range( ITERATOR first, ITERATOR_E last ) : first(first), last(last) {}

     ITERATOR begin() const { return first ; }
     ITERATOR end() const { return last ; }

     ITERATOR first ;
     ITERATOR_E last ;
};

template < typename SEQ, typename PREDICATE > auto in( SEQ& seq, PREDICATE fn )
{
    return range { boost::make_filter_iterator( fn, std::begin(seq), std::end(seq) ),
                   boost::make_filter_iterator( fn, std::end(seq), std::end(seq) ) } ;
}

template < typename SEQ, typename PREDICATE > auto in_reverse( SEQ& seq, PREDICATE fn )
{
    return range { boost::make_filter_iterator( fn, std::rbegin(seq), std::rend(seq) ),
                   boost::make_filter_iterator( fn, std::rend(seq), std::rend(seq) ) } ;
}

int main()
{
    const int arr[] { 1, 22, 3, 44, 5, 66, 7, 88, 9 } ;

    const auto gt9 = []( int v ) { return v > 9 ; };
    for( const auto& value : in_reverse( arr, gt9 ) ) std::cout << value << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/aefc3d781c0e33a9
Note: C++17 class template argument deduction (for range<>) is used for brevity.