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 ¤t,
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.