itk::NeighborhoodRange: a new class for efficient modern C++ style iteration

Engineering
37

I’m preparing another patch set which I’ll try to submit later today. It should include renaming the range class, as we discussed here. Hopefully this will be the final patch set before the merge to the master branch of ITK!

But there’s something I need to tell you… While developing the range class, I was informed by two C++ experts, Anthony Williams and Jonathan Wakely, that the iterators I’m proposing here do not entirely satisfy the iterator requirements as specified by the current C++ Standard! :open_mouth: So what does that mean…?

itk::NeighborhoodRange::iterator supports everything you would expect from a bidirectonal iterator: ++it, --it, it++, it--, *it, auto it2{it1}, it2 = it1, it1 == it2, it1 != it2. However, it does not satisfy the following requirements (quoted from the current Working Draft of the C++ Standard):

From section [iterator.requirements.general]:

An iterator i for which the expression (*i).m is well-defined supports the expression i->m with the same semantics as (*i).m.

From section [forward.iterators]:

  • if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T

itk::NeighborhoodRange::iterator does not have an operator->(), so it does not support it->m. Moreover, itk::NeighborhoodRange::iterator::reference (the return type of iterator::operator*()) is not a real C++ reference type (PixelType &), instead, it’s a proxy class (PixelProxy).

Strictly speaking, that implies that itk::NeighborhoodRange::iterator is not guaranteed to work well as argument to a C++ Standard Library function that requires a standard compliant iterator.

Fortunately itkNeighborhoodRangeGTest.cxx tests such use cases, and they all pass successfully:

std::vector<PixelType>(range.cbegin(), range.cend());
std::reverse_copy(range.begin(), range.end(), stdVector.begin());
std::inner_product(range.begin(), range.end(), range.begin(), 0.0);
std::for_each(range.begin(), range.end(), [](const PixelType&){});

Moreover: some iterators in the C++ Standard Library don’t satisfy these particular requirement either! std::istreambuf_iterator does not have an operator->() (as reported by Jonathan Wakely) And std::vector<bool>::iterator also has a proxy as iterator::reference type.

Even more hopeful: There is a very detailed proposal to get full support for proxy iterators into the C++ Standard Library: Proxy Iterators for the Ranges Extensions by Eric Niebler.

Summary: itk::NeighborhoodRange::iterator (patch set 19) may not yet officially satisfy all iterator requirements from the current C++ Standard, but in practice, it just appears to work well, as argument to an std function. And of course, the other advantages are still there as well: a significant performance improvement, support for multi-threading and support for range-based for loops. :smiley:

5 Likes