6
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ The explicit is definitely a good idea and was pure oversight on my side. I tend towards const& to avoid unnecessary copies but maybe the stdlib has a rationale behind passing by value, do you know of any? Regarding the case mixing: I presume that these names are an artifact of my transition phase from CamelCase to snake_case. A started this project in CamelCase ... However, I like the make_<TypeName> layout. Would a make<typename> be acceptable/more readable? Regarding the static_assert I just wrote a sentence (without period) and did not bother much more. \$\endgroup\$ May 26, 2015 at 8:37
  • \$\begingroup\$ @Nobody The standard library passes iterators by value because they tend to be very small. I guess that Boost doesn't because it also has bigger iterator classes; the assumptions are not the same. The choice is up to you in the end. Concerning the case, you can use either make_type_name or makeTypeName, the important is for it to be understandable in the end, but mixed case name tend not to please anyone, so you better pick just one case and be consistent :) \$\endgroup\$
    – Morwenn
    May 26, 2015 at 8:41
  • \$\begingroup\$ Also: I am currently tied to supporting C++11 at minimum but I would be very keen to learn some C++14 tricks so I would not mind if you posted improvements there. I suppose you would do tuple unpacking via integer_sequence? \$\endgroup\$ May 26, 2015 at 8:41
  • \$\begingroup\$ @Nobody Yes, and I would also turn the big decltype in the return type of dereference into a simple decltype(auto) since the current form only duplicates code and does not really help anybody reading the code to know what type will be returned in the end. \$\endgroup\$
    – Morwenn
    May 26, 2015 at 8:42
  • \$\begingroup\$ Also, just to make sure: Did you have a look at the unittests and the questions regarding them? \$\endgroup\$ May 26, 2015 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.