10
\$\begingroup\$

I have implemented a custom iterator to iterate over an array that is held by a pointer. The iterator accepts a unit which specifies by which amount the underlying pointer is increased (or decreased) at each increment (or decrement).

I.e. when

auto data = new int[100];
ArrayIterator<int, false> it(data, 2); // 2nd argument is unit

it + 1 refers to the same element as data + 2.

PointerIterator.hpp

#pragma once

#include <iterator>


/**
 * \brief A class for iterating over pointers. This class allows to specify a unit, by which the underlying pointers are 
 * incremented (or decremented) when increasing (or decreasing) it. 
 * I.e. this allows to easily iterate over columns of a matrix that is represented by a single pointer in row major order.
 * \tparam DataT The data type the pointer is pointing to.
 * \tparam Reverse True, if the iterator is used as a reverse iterator (incrementing the iterator is decrementing the pointer, and vice versa).
 */
template <typename DataT, bool Reverse = false>
class ArrayIterator
{
public:
    using difference_type = long long;
    using value_type = DataT;
    using pointer = DataT*;
    using const_pointer = const DataT*;
    using reference = DataT&;
    using const_reference = const DataT&;
    using iterator_category = std::random_access_iterator_tag;

    using const_iterator = ArrayIterator<const std::remove_const_t<DataT>, Reverse>;


    /**
     * \brief Creates an invalid iterator.
     */
    ArrayIterator() = default;

    /**
     * \brief Creates a pointer iterator for the specified pointer.
     * \tparam DataT The underlying data type of the pointer.
     * \param data The pointer.
     * \param unit The amount by which the pointer is increased (or decreased) at each increment (or decrement). 
     */
    explicit ArrayIterator(DataT* data, size_t unit = 1);

    operator const_iterator() const; // allow implicit conversion from iterator to const iterator

    ArrayIterator& operator++();
    ArrayIterator operator++(int);

    ArrayIterator& operator--();
    ArrayIterator operator--(int);

    ArrayIterator& operator+=(int n);
    ArrayIterator& operator-=(int n);

    ArrayIterator operator+(int n) const;

    ArrayIterator operator-(int n) const;
    difference_type operator-(ArrayIterator other) const;

    reference operator[](int n);
    const_reference operator[](int n) const;

    bool operator<(ArrayIterator other) const;
    bool operator<=(ArrayIterator other) const;
    bool operator>(ArrayIterator other) const;
    bool operator>=(ArrayIterator other) const;

    bool operator==(ArrayIterator other) const;
    bool operator!=(ArrayIterator other) const;

    pointer operator->();
    const_pointer operator->() const;
    reference operator*();
    const_reference operator*() const;

    void swap(ArrayIterator& other) noexcept;
    size_t getUnit() const;

private:
    pointer _ptr = nullptr;
    size_t _unit = 0;
};


template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>::ArrayIterator(DataT* data, size_t unit)
    : _ptr(data), _unit(unit)
{
}


template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>::operator const_iterator() const
{
    using type = const std::remove_const_t<DataT>;
    return ArrayIterator<type, Reverse>(reinterpret_cast<type*>(_ptr), _unit);
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>& ArrayIterator<DataT, Reverse>::operator++()
{
    if constexpr (Reverse)
        _ptr -= _unit;
    else
        _ptr += _unit;

    return *this;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse> ArrayIterator<DataT, Reverse>::operator++(int)
{
    auto it = *this;
    ++*this;
    return it;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>& ArrayIterator<DataT, Reverse>::operator--()
{
    if constexpr (Reverse)
        _ptr += _unit;
    else
        _ptr -= _unit;

    return *this;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse> ArrayIterator<DataT, Reverse>::operator--(int)
{
    auto it = *this;
    --*this;
    return it;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>& ArrayIterator<DataT, Reverse>::operator+=(int n)
{
    if constexpr (Reverse)
        _ptr -= n * _unit;
    else
        _ptr += n * _unit;

    return *this;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse>& ArrayIterator<DataT, Reverse>::operator-=(int n)
{
    if constexpr (Reverse)
        _ptr += n * _unit;
    else
        _ptr -= n * _unit;

    return *this;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse> ArrayIterator<DataT, Reverse>::operator+(int n) const
{
    auto it = *this;
    it += n;
    return it;
}

template <typename DataT, bool Reverse>
ArrayIterator<DataT, Reverse> ArrayIterator<DataT, Reverse>::operator-(int n) const
{
    auto it = *this;
    it -= n;
    return it;
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::difference_type ArrayIterator<DataT, Reverse>::operator-(ArrayIterator other) const
{
    if (_unit != other._unit)
        throw std::logic_error("Cannot calculate differnce for iterators with different unit.");

    if constexpr (Reverse)
        return (_ptr - other._ptr) / _unit;
    else
        return (other._ptr - _ptr) / _unit;
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::reference ArrayIterator<DataT, Reverse>::operator[](int n)
{
    return *(*this + n);
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::const_reference ArrayIterator<DataT, Reverse>::operator[](int n) const
{
    return *(*this + n);
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator<(ArrayIterator other) const
{
    if constexpr (Reverse)
        return other._ptr < _ptr;
    else
        return _ptr < other._ptr;
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator<=(ArrayIterator other) const
{
    if constexpr (Reverse)
        return other._ptr <= _ptr;
    else
        return _ptr <= other._ptr;
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator>(ArrayIterator other) const
{
    if constexpr (Reverse)
        return other._ptr > _ptr;
    else
        return _ptr > other._ptr;
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator>=(ArrayIterator other) const
{
    if constexpr (Reverse)
        return other._ptr >= _ptr;
    else
        return _ptr >= other._ptr;
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator==(ArrayIterator other) const
{
    return _ptr == other._ptr;
}

template <typename DataT, bool Reverse>
bool ArrayIterator<DataT, Reverse>::operator!=(ArrayIterator other) const
{
    return !(*this == other);
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::pointer ArrayIterator<DataT, Reverse>::operator->()
{
    return _ptr;
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::const_pointer ArrayIterator<DataT, Reverse>::operator->() const
{
    return _ptr;
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::reference ArrayIterator<DataT, Reverse>::operator*()
{
    return *_ptr;
}

template <typename DataT, bool Reverse>
typename ArrayIterator<DataT, Reverse>::const_reference ArrayIterator<DataT, Reverse>::operator*() const
{
    return *_ptr;
}

template <typename DataT, bool Reverse>
void ArrayIterator<DataT, Reverse>::swap(ArrayIterator& other) noexcept
{
    auto mPtr = _ptr;
    auto mUnit = _unit;
    _ptr = other._ptr;
    _unit = other._unit;
    other._ptr = mPtr;
    other._unit = mUnit;
}

template <typename DataT, bool Reverse>
size_t ArrayIterator<DataT, Reverse>::getUnit() const
{
    return _unit;
}


/**
 * \brief Creates an iterator for the specified pointer.
 * \tparam DataT The underlying data type of the pointer.
 * \param ptr The pointer.
 * \param unit The amount by which the pointer is increased (or decreased) at each increment (or decrement). 
 */
template <typename DataT>
ArrayIterator<DataT, false> makeArrayIterator(DataT* ptr, size_t unit = 1)
{
    return ArrayIterator<DataT, false>(ptr, unit);
}


/**
 * \brief Creates a reversed iterator for the specified pointer. That is, if the iterator is increased by 
 * an arbitrary amount x, the underlying pointer is decreased by x (and vice versa). 
 * \tparam DataT The underlying data type of the pointer.
 * \param ptr The pointer.
 * \param unit The amount by which the pointer is increased (or decreased) at each increment (or decrement). 
 */
template <typename DataT>
ArrayIterator<DataT, true> makeArrayIterator(DataT* ptr, size_t unit = 1)
{
    return ArrayIterator<DataT, true>(ptr, unit);
}

/**
 * \brief Creates a const iterator for the specified pointer.
 * \tparam DataT The underlying data type of the pointer.
 * \param ptr The pointer.
 * \param unit The amount by which the pointer is increased (or decreased) at each increment (or decrement). 
 */
template <typename DataT>
ArrayIterator<DataT, false> makeConstArrayIterator(DataT* ptr, size_t unit = 1)
{
    return ArrayIterator<const std::remove_const_t<DataT>, false>(ptr, unit);
}


/**
 * \brief Creates a const reversed iterator for the specified pointer. That is, if the iterator is increased by 
 * an arbitrary amount x, the underlying pointer is decreased by x (and vice versa). 
 * \tparam DataT The underlying data type of the pointer.
 * \param ptr The pointer.
 * \param unit The amount by which the pointer is increased (or decreased) at each increment (or decrement). 
 */
template <typename DataT>
ArrayIterator<const DataT, true> makeConstReverseArrayIterator(DataT* ptr, size_t unit = 1)
{
    return ArrayIterator<const std::remove_const_t<DataT>, true>(ptr, unit);
}

Are there any mistakes or improvements?

\$\endgroup\$
  • 1
    \$\begingroup\$ makeConstArrayIterator with direction forward is missing a const on the 1st template argument for the return type. \$\endgroup\$ – Darhuuk Apr 16 '18 at 13:31
  • 1
    \$\begingroup\$ This seems an oddly specific template. A pointer-into-array is a RandomAccessIterator. I would generalise this to adapt any RandomAccessIterator \$\endgroup\$ – Caleth Apr 16 '18 at 17:44
  • \$\begingroup\$ @Caleth That is indeed a good point. \$\endgroup\$ – Timo Apr 16 '18 at 18:56
  • \$\begingroup\$ Why is units a constructor parameter and not a template parameter. You mention that pointers with different units are not comparable. So why not make them distinct types by putting the size into the template. It also reduces the size of your iterator object. \$\endgroup\$ – Martin York Apr 16 '18 at 22:09
  • \$\begingroup\$ @MartinYork Because in many cases unit is only known at run time (i.e. when iterating over an arbitrary array that represents a n by m matrix in row major order, unit can be set to the stride (n) to iterate over a specific column) \$\endgroup\$ – Timo Apr 16 '18 at 22:44
8
\$\begingroup\$

Design Issues

If there is one thing that bothers me about your code, it's that Reverse template parameter. First off all, why would you code that into your class if you could just use std::reverse_iterator and be done?

Secondly, I would argue against adding additional functionality to iterators. After all, the reason for having iterators in the first place is to have a uniform, pointer-like access to the contents of a collection. Adding additional functionality into this interface violates the principle of minimalism that the design is based on.

Other Things

  1. Fix your includes. You're missing #include <type_traits> (for std::remove_const_t), #include <stdexcept> (for std::logic_error) and #include <cstddef> or similar (for std::size_t).
  2. Don't rely on C legacy types being defined in the global namespace. ::size_t may not exist; use std::size_t instead.
  3. using difference_type = long long; should be using difference_type = std::ptrdiff_t. The latter is arguably more correct here and expresses your intents better.
  4. Why do you take an int as argument for operator[]? This limits your dereference to the size of int, whereas the underlying container can have a size of std::size_t.
  5. It appears you have typo'ed "difference" in throw std::logic_error("Cannot calculate differnce for iterators with different unit.");.
\$\endgroup\$
  • \$\begingroup\$ I completely forgot about std::reverse_iterator. Thanks for pointing that out. About your second design issue: what additional functionality are you referring to? The only overhead I can see is getUnit(), which I thought would be helpful if it's accessible from outside. Other Things: 3: I thought I read on cppreference that std::ptrdiff_t is marked as deprecated in C++17, but looks like I messed that up. I will fix the other points asap. \$\endgroup\$ – Timo Apr 16 '18 at 14:51
  • \$\begingroup\$ @Timo I was referring to the reverse_iterator issue with my second design point as well, so I guess you don't need to consider that anymore. \$\endgroup\$ – Ben Steffan Apr 16 '18 at 15:01
  • \$\begingroup\$ Alright. I think I fixed everything. Can you confirm, please? \$\endgroup\$ – Timo Apr 16 '18 at 15:06
  • \$\begingroup\$ @Timo I'm sorry, but you will have to roll back your edit. The validity and usefulness of answers on Code Review depends on code in questions not being edited after there is at least one review. If you still have doubts about your code, please post a follow up question instead. \$\endgroup\$ – Ben Steffan Apr 16 '18 at 15:13
  • 1
    \$\begingroup\$ @yuri, for standard library it is not hard to remember (may be if you're working on a project with bizillion includes). There are off course edge cases, which for me is multithreading stuff. \$\endgroup\$ – Incomputable Apr 16 '18 at 16:25
0
\$\begingroup\$

Take a look at Boost.Iterator.

You can write what you want by a simple use of Boost’s iterator_adaptor, changing only what you need to change (e.g. advance member). Seriously, it does all that code you wrote, already in the can and well reviewed for edge cases. You only have to write what’s different from the underlying iterator, and everything else comes through.

Or, if you’re living on the bleeding edge, just use a view::stride in the Range v3 library.

Given a source range and an integral stride value, return a range consisting of every Nth element, starting with the first.

\$\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.