15
\$\begingroup\$

C++11 is great. Probably one of the most beautiful features (in my opinion) is the so-called range-based-for-loop. Instead of

for ( std::size_t i(0); i < range.size(); ++i )
{
   // do something to range[i];
}

or

for ( Range::iterator it(range.begin()); it != range.end(); ++it )
{
   // do something to *it;
}

or simplified with C++11 auto:

for ( auto it(range.begin()); it != range.end(); ++it )
{
   // do something to *it;
}

we can say this:

for ( auto& entry : range )
{
   // do something with entry.
}

This is very expressive: We talk about the entry, rather than the i^th position in the range or the iterator pointing to an entry. However, this syntax lacks the ability of having subranges (e.g. ignoring the last entry). In a series of small helper structs / methods, I want to add this functionality in a clean way.

So much for my motivation ;-) Now, for the real deal.

In this post, I address conditions on the entries of range. Basically, the helper code should perform the equivalent of

for ( auto& entry : range )
{
   if ( condition(entry) )
   {
       // do something to entry.
   }
}

but without that level of indentation.

Here is the code for ConditionalRange:

template <typename Range, typename Runnable>
ConditionalRange<Range, Runnable> makeConditionalRange(Range& range, Runnable&& condition)
{
   static_assert(std::is_same<decltype(condition(*std::declval<Range>().begin())), bool>::value, "Condition must return a boolean value.");
   return ConditionalRange<Range, Runnable>(range, std::forward<Runnable>(condition));
}

template <typename Range, typename Runnable>
struct ConditionalRange
{
   public:
      friend ConditionalRange makeConditionalRange<>(Range&, Runnable&&);
   public:
      using iterator_type = ConditionalIterator<decltype(std::declval<Range>().begin()), Runnable>;
      iterator_type begin() const
      {
         auto b = range.begin();
         while ( b != range.end() && !condition(*b) )
         {
            ++b;
         }
         return ConditionalIterator<decltype(std::declval<Range>().begin()), Runnable>(b, range.end(), condition);
      }
      iterator_type end() const
      {
         return ConditionalIterator<decltype(std::declval<Range>().begin()), Runnable>(range.end(), range.end(), condition);
      }
   private:
      ConditionalRange(Range& range_, Runnable&& condition_)
      :
         range(range_),
         condition(std::forward<Runnable>(condition_))
      {
      }
   private:
      Range& range;
      Runnable condition;
};

This is the helper struct for the iterator:

template <typename Iterator, typename Runnable>
struct ConditionalIterator
{
   private:
      Iterator iterator;
      Iterator end;
      const Runnable& condition;
   public:
      ConditionalIterator(Iterator b, Iterator e, const Runnable& r)
      :
         iterator(b),
         end(e),
         condition(r)
      {
      }
      auto operator*() -> decltype(*iterator)
      {
         return *iterator;
      }
      ConditionalIterator& operator++()
      {
         do
         {
            ++iterator;
         }
         while ( iterator != end && !condition(*iterator) );
         return *this;
      }
      bool operator==(const ConditionalIterator& second)
      {
         return iterator == second.iterator;
      }
      bool operator!=(const ConditionalIterator& second)
      {
         return !(*this == second);
      }
};

The intended usage is:

std::vector<int> ns{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for ( const auto& n : makeConditionalRange(ns, [](int a) { return a % 2 == 0; }) )
{
   std::cout << n << " ";
}
std::cout << "\n";

Demo: click here!

What are weaknesses of my approach? With what kind of arguments does it fail, although it shouldn't in the perfect world?

\$\endgroup\$
  • 1
    \$\begingroup\$ I can see no weaknesses, but I think you should consider renaming makeConditionalRange with something that focuses on client code appearance, not on "making a conditional range". By that, I mean that client code should look like this instead: for(const auto& n: iterate_if(ns, [](int a) { return a % 2 == 0; }) ) \$\endgroup\$ – utnapistim Mar 3 '14 at 16:20
  • 1
    \$\begingroup\$ So does the intent here differ significantly from a Boost filter_iterator? \$\endgroup\$ – Jerry Coffin Mar 3 '14 at 17:37
  • \$\begingroup\$ @JerryCoffin No it doesn't. I simply haven't looked into Boost ;-) \$\endgroup\$ – stefan Mar 3 '14 at 17:39
  • 1
    \$\begingroup\$ The most common test for iterators operator!= optimize this over operator== \$\endgroup\$ – Martin York Mar 4 '14 at 1:48
  • 2
    \$\begingroup\$ @stefan: To be blunt that's silly. Its like saying I don't wont to buy a car from the standard manufacturers because I want to build one that runs off seaweed myself to guarantee that it does not cause pollution. The problem is your set of libraries are going to be infinitely more buggy than boost because you only have one set of eyes looking at them. Boost has thousands of people checking and validating the code fixing and providing feedback to make sure the correct idioms are used correctly. Read: stackoverflow.com/a/149305/14065 \$\endgroup\$ – Martin York Mar 5 '14 at 1:38
10
\$\begingroup\$

You can use braces to return from your functions. That way, you won't have to repeat long and cumbersome types (DRY, as much as possible). For example, ConditionalRange::end:

iterator_type end() const
{
    return { range.end(), range.end(), condition };
}

Also, you probably want your function to accept C-style arrays too. Therefore, you should use std::begin and std::end instead of calling the member functions:

iterator_type end() const
{
    return { std::end(range), std::end(range), condition };
}

With that (everywhere in your code) and some trivial changes, your code will also work for C-style arrays (tested here and it works fine).

Naming your function

The name makeConditionalRange is quite long. The function you created already exists in other libraries and programming languages (Python comes to my mind) under the name filter. You should consider changing its name in order for many users to recognize the name at first glance (moreover, it will be shorter).

\$\endgroup\$

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.