AdjacentElementsIteratorAdaptor for Random Access Iterators

Question

Inspired by this comment I decided to implement an iterator adaptor that takes another iterator and returns each element and a given number of its neighbors.

The final solution should be applicable to most iterator types but this review is only about my first solution for random access iterators and can be found here.

adjacent_element_iterator.hpp

#ifndef ADJACENT_ELEMENT_ITERATOR_HPP_
#define ADJACENT_ELEMENT_ITERATOR_HPP_

#include <cstdint>
#include <iterator>
#include <boost/iterator/iterator_adaptor.hpp>
#include <tuple>

template <std::size_t NumberOfElements, class WrappedIterator>
struct AdjacentElementRandomAccessIterator;

/**
 * @brief Helps dereferencing into a tuple of the given size
 */
template <std::size_t NumberOfElements, class WrappedIterator,
          std::size_t CurrentRepeatNumber = 0>
struct DereferenceHelper {
  template <class... Arguments>
  static auto dereference(WrappedIterator const &current,
                          Arguments... arguments)
      -> decltype(DereferenceHelper<NumberOfElements, WrappedIterator,
                                    (sizeof...(Arguments) +
                                     1)>::dereference(current,
                                                      std::forward<Arguments>(
                                                          arguments)...,
                                                      current)) {
    auto next = std::next(current);
    return DereferenceHelper<NumberOfElements, WrappedIterator,
                             (sizeof...(Arguments) +
                              1)>::dereference(next,
                                               std::forward<Arguments>(
                                                   arguments)...,
                                               next);
  }
};

/**
 * @brief Ends the recursion and actually creates the tuple
 */
template <std::size_t NumberOfElements, class WrappedIterator>
struct DereferenceHelper<NumberOfElements, WrappedIterator, NumberOfElements> {
  template <class... Arguments>
  static auto dereference(WrappedIterator const & /*current*/,
                          Arguments... arguments)
      -> decltype(std::tie(*arguments...)) {
    return std::tie(*arguments...);
  }
};

/**
 * @brief Shorthand for a NumberOfElements tuple of dereference WrappedIterators
 */
template <std::size_t NumberOfElements, class WrappedIterator>
using AdjacentElementValue =
    decltype(DereferenceHelper<NumberOfElements, WrappedIterator>::dereference(
        std::declval<WrappedIterator>(), std::declval<WrappedIterator>()));

/**
 * @brief An iterator adaptor that returns NumberOfElements neighboring elements
 *        at once
 */
template <std::size_t NumberOfElements, class WrappedIterator>
struct AdjacentElementRandomAccessIterator
    : boost::iterator_adaptor<
          AdjacentElementRandomAccessIterator<NumberOfElements,
                                              WrappedIterator>,
          WrappedIterator,
          AdjacentElementValue<NumberOfElements, WrappedIterator>,
          boost::use_default,
          AdjacentElementValue<NumberOfElements, WrappedIterator>> {
  static_assert(NumberOfElements >= 2, "Need at least two adjacent elements");

  using BaseClass = typename boost::iterator_adaptor<
      AdjacentElementRandomAccessIterator<NumberOfElements, WrappedIterator>,
      WrappedIterator, AdjacentElementValue<NumberOfElements, WrappedIterator>,
      boost::use_default,
      AdjacentElementValue<NumberOfElements, WrappedIterator>>;

  AdjacentElementRandomAccessIterator() = default;

  AdjacentElementRandomAccessIterator(WrappedIterator const &wrappedIterator)
      : BaseClass{wrappedIterator} {}

private:
  friend class boost::iterator_core_access;

  typename BaseClass::reference dereference() const {
    return DereferenceHelper<NumberOfElements, WrappedIterator>::dereference(
        this->base(), this->base());
  }
};

/**
 * @brief Wrap an iterator into an AdjacentElementIterator
 *
 * Use make_AdjacentElementRange instead of this function to generate the
 * iterators of a range.
 *
 * Do not use this on end iterators! Use make_AdjacentElementEndIterator
 * instead!                                                  ~~~
 */
template <std::size_t NumberOfElements, class WrappedIterator>
AdjacentElementRandomAccessIterator<NumberOfElements, WrappedIterator>
make_AdjacentElementIterator(WrappedIterator const &wrappedIterator) {
  return {wrappedIterator};
}

/**
 * @brief Create an end AdjacentElementIterator
 *
 * Use make_AdjacentElementRange instead of this function to generate the
 * iterators of a range. This function will not work properly if the range is
 * smaller than NumberOfElements.
 */
template <std::size_t NumberOfElements, class WrappedIterator>
AdjacentElementRandomAccessIterator<NumberOfElements, WrappedIterator>
make_AdjacentElementEndIterator(WrappedIterator const &wrappedIterator) {
  return {std::prev(wrappedIterator, NumberOfElements - 1)};
}

#endif /* ADJACENT_ELEMENT_ITERATOR_HPP_ */

adjacent_element_range.hpp

#ifndef ADJACENT_ELEMENT_RANGE_HPP_
#define ADJACENT_ELEMENT_RANGE_HPP_

#include "adjacent_element_iterator.hpp"
#include <boost/range/iterator_range.hpp>

/**
 * @brief Create a range of AdjacentElementiterators from begin/end iterators
 * @tparam NumberOfElements that should be returned by the AdjacentElementIteror
 */
template <std::size_t NumberOfElements, class WrappedIterator>
boost::iterator_range<
    AdjacentElementRandomAccessIterator<NumberOfElements, WrappedIterator>>
make_AdjacentElementRange(WrappedIterator const &begin,
                          WrappedIterator const &end) {
  if (std::distance(begin, end) >= NumberOfElements) {
    return {make_AdjacentElementIterator<NumberOfElements>(begin),
            make_AdjacentElementEndIterator<NumberOfElements>(end)};
  } else {
    /* The range is shorter than the resulting tuple size.
     * the EndIterator function would move the iterator in front of the begin
     * iterator. Logically, this is an empty range so we create one.
     */
    return boost::make_iterator_range_n(
        make_AdjacentElementIterator<NumberOfElements>(begin), 0);
  }
}

/**
 * @brief Create a range of AdjacentElementIterators from the given range
 * @tparam NumberOfElements that should be returned by the AdjacentElementIteror
 */
template <std::size_t NumberOfElements, class Range>
auto make_AdjacentElementRange(Range &range)
    -> boost::iterator_range<AdjacentElementRandomAccessIterator<
        NumberOfElements, decltype(std::begin(range))>> {
  return make_AdjacentElementRange<NumberOfElements>(std::begin(range),
                                                     std::end(range));
}

#endif /* ADJACENT_ELEMENT_RANGE_HPP_ */

unittests/random_access.cpp

#include "../adjacent_element_iterator.hpp"
#include "../adjacent_element_range.hpp"
#include <boost/test/unit_test.hpp>
#include <vector>

namespace {

using Vector = std::vector<int>;

/**
 * @brief Return the demangled type name as string
 */
template <class T> std::string type_name() {
  return boost::core::demangle(typeid(T).name());
}
}

namespace Fixtures {

struct VectorOfSize10 {
  const Vector vectorOfSize10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
};
}

BOOST_FIXTURE_TEST_CASE(
    Test_make_AdjacentElementIterator_returns_AdjacentElementRandomAccessIterator_for_vector,
    Fixtures::VectorOfSize10) {
  auto adjacentElementIterator =
      make_AdjacentElementIterator<2>(vectorOfSize10.begin());
  BOOST_REQUIRE_EQUAL(
      (type_name<
          AdjacentElementRandomAccessIterator<2, Vector::const_iterator>>()),
      (type_name<typeof(adjacentElementIterator)>()));
}

BOOST_FIXTURE_TEST_CASE(
    Test_make_AdjacentElementEndIterator_returns_AdjacentElementRandomAccessIterator_for_vector,
    Fixtures::VectorOfSize10) {
  auto adjacentElementIterator =
      make_AdjacentElementEndIterator<2>(vectorOfSize10.end());
  BOOST_REQUIRE_EQUAL(
      (type_name<
          AdjacentElementRandomAccessIterator<2, Vector::const_iterator>>()),
      (type_name<typeof(adjacentElementIterator)>()));
}

BOOST_AUTO_TEST_CASE(
    Test_make_AdjacentElementRange_with_too_small_ranges_are_empty) {
  {
    Vector emptyVector;
    BOOST_REQUIRE(make_AdjacentElementRange<2>(emptyVector).empty());
  }
  {
    Vector vectorOfSize1 = {1};
    BOOST_REQUIRE(make_AdjacentElementRange<2>(vectorOfSize1).empty());
  }
}

BOOST_FIXTURE_TEST_CASE(Test_range_length_reduced_by_NumberOfElements_minus_1,
                        Fixtures::VectorOfSize10) {
  {
    BOOST_REQUIRE_EQUAL(
        boost::size(make_AdjacentElementRange<2>(vectorOfSize10)), 9);
  }
  {
    BOOST_REQUIRE_EQUAL(
        boost::size(make_AdjacentElementRange<5>(vectorOfSize10)), 6);
  }
}

BOOST_AUTO_TEST_CASE(Test_AdjacentElementValue_has_correct_type) {
  BOOST_REQUIRE_EQUAL(
      (type_name<AdjacentElementValue<2, Vector::iterator>>()),
      (type_name<std::tuple<Vector::reference, Vector::reference>>()));
}

namespace boost {

namespace {
template <std::size_t...> struct seq {};

template <std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N - 1, N - 1, Is...> {};

template <std::size_t... Is> struct gen_seq<0, Is...> : seq<Is...> {};

template <class Tuple, std::size_t... Is>
void print_tuple(wrap_stringstream::wrapped_stream &os, Tuple const &t,
                 seq<Is...>) {
  using swallow = int[];
  (void)swallow{0,
                (void(os << (Is == 0 ? "" : ", ") << std::get<Is>(t)), 0)...};
}
}

template <class... TupleTypes>
inline wrap_stringstream::wrapped_stream &
operator<<(wrap_stringstream::wrapped_stream &wrapped,
           std::tuple<TupleTypes...> const &tuple) {
  wrapped << '<';
  print_tuple(wrapped, tuple, gen_seq<sizeof...(TupleTypes)>());
  wrapped << '>';
  return wrapped;
}
}

BOOST_AUTO_TEST_CASE(Test_make_AdjacentElementRange_returns_correct_elements) {
  Vector vectorOfSize4 = {0, 1, 2, 3};
  using std::make_tuple;
  {
    std::vector<std::tuple<int, int>> expected = {
        make_tuple(0, 1), make_tuple(1, 2), make_tuple(2, 3)};
    auto actual = make_AdjacentElementRange<2>(vectorOfSize4);
    BOOST_REQUIRE_EQUAL_COLLECTIONS(actual.begin(), actual.end(),
                                    expected.begin(), expected.end());
  }
  {
    std::vector<std::tuple<int, int, int>> expected = {make_tuple(0, 1, 2),
                                                       make_tuple(1, 2, 3)};
    auto actual = make_AdjacentElementRange<3>(vectorOfSize4);
    BOOST_REQUIRE_EQUAL_COLLECTIONS(actual.begin(), actual.end(),
                                    expected.begin(), expected.end());
  }
  {
    std::vector<std::tuple<int, int, int, int>> expected = {
        make_tuple(0, 1, 2, 3)};
    auto actual = make_AdjacentElementRange<4>(vectorOfSize4);
    BOOST_REQUIRE_EQUAL_COLLECTIONS(actual.begin(), actual.end(),
                                    expected.begin(), expected.end());
  }
}

For me the most important goals in reviewing this are:

• correctness
  • missing corner case handling
  • invalid assumptions about the wrapped type
• usability/readability
  • misleading/unreadable error messages
  • lacking interface description
• performance
  • unnecessary copies
  • slow compilation speed
• better naming

I feel that the unittests are lacking so if you have ideas (or better proof of) what is missing I would like to hear about them.

Answer 1

Generally speaking, the code is really well-written and looks as idiomatic as it could possibly be. That's probably why you didn't get any answer since you asked it. So... well, I will make a small and highly subjective review since I still can't see any obvious problem with your code:

• It seems that Boost and the standard library do things in subtly different ways when it comes to iterators. The standard library iterator adapters use explicit constructors to transform iterators when the constructors have only one parameter while Boost does not seem to follow the practice. You might want to make AdjacentElementRandomAccessIterator's constructor explicit.

  On the other hand, it means that you won't be able to use the nice syntax return { /* ... */ } when construct-returning an instance of AdjacentElementRandomAccessIterator.

• Yet another difference: the standard library tends to pass iterators by value while Boost tends to pass them by const reference. It seems that you followed the Boost way to do things. I can't say which is better but you may want to think again about it and change or not your decision.

• I generally don't talk about case because that's often a matter of taste, but when writing library components that look like those you can find in Boost or the standard library, I find it better to use the snake_case so that it looks more consistent. The mixed case of make_AdjacentElementIterator looks especially bad to my eye :/

• You may want to only use lower case letters for the static_assert error message, which is the case compilers tend to use for their diagnostics.

As you can see, that's as subjective a review as you will get. If I try to comment further, I will talk more and more about style (and there is nothing wrong with your style, so that would be pointless) or about C++14 but your code seems to explicitly target C++11 so that would be pointless too.