5
\$\begingroup\$

This is just like std::array<T, N>. I wrote this for practice. The class is in a different namespace, so the name array stands!!

There is only one bug (that I'm aware of) and that's the base() function for the reverse iterators. Works fine with const_reverse_iterator, but if I do the following:

auto i = arr.rbegin();  //i is array<T, N>::reverse_iterator
auto j = i.base();   //j is std::iterator<std::random_access_iterator_tag, T>

So I could use a little help with that!

Sorry about the lack of horizontal space! It looks too good in an IDE with more space!

Live example: http://coliru.stacked-crooked.com/a/e39f5760f67fa533

#include <cstddef>
#include <stdexcept>
#include <iterator>
#include <utility>
#include <type_traits>
#include <algorithm>
#include <functional>

template<class ArrType, std::size_t Size>
class array
{
public:     //TYPE ALIASES
    using value_type      = ArrType;
    using size_type       = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference       = ArrType&;
    using const_reference = const ArrType&;
    using pointer         = ArrType*;
    using const_pointer   = const ArrType*;

private:
    class array_iterator : public std::iterator<std::random_access_iterator_tag, value_type>
    {
    protected:
        pointer _pos;

    public:
        explicit constexpr array_iterator(pointer pos)
            : _pos(pos)
        {}

        constexpr array_iterator() = default;
        constexpr array_iterator(const array_iterator&) = default;
        constexpr array_iterator(array_iterator&&)      = default;

        //ASSIGNMENT OPERATORS
        array_iterator &operator=(const array_iterator&) = default;
        array_iterator &operator=(array_iterator&&)      = default;

        //COMPARISON OPERATORS
        constexpr bool operator==(const array_iterator& rhs) const { return _pos == rhs._pos; }
        constexpr bool operator!=(const array_iterator& rhs) const { return _pos != rhs._pos; }
        constexpr bool operator>(const array_iterator& rhs)  const { return _pos > rhs._pos; }
        constexpr bool operator<(const array_iterator& rhs)  const { return _pos < rhs._pos; }
        constexpr bool operator>=(const array_iterator& rhs) const { return _pos >= rhs._pos; }
        constexpr bool operator<=(const array_iterator& rhs) const { return _pos <= rhs._pos; }
    };

public:
    class const_iterator : public array_iterator
    {
    public:
        using array_iterator::array_iterator;

        //INCREMENT/DECREMENT OPERATORS
        const_iterator& operator++() { ++array_iterator::_pos; return *this; }
        const_iterator& operator--() { --array_iterator::_pos; return *this; }
        const_iterator  operator++(int) { const_iterator temp(*this); operator++(); return temp; }
        const_iterator  operator--(int) { const_iterator temp(*this); operator--(); return temp; }

        //ARITHMETIC OPERATORS
        const_iterator operator+(const difference_type& off) const { return const_iterator(array_iterator::_pos + off); }
        const_iterator operator-(const difference_type& off) const { return const_iterator(array_iterator::_pos - off); }

        const_iterator& operator+=(const difference_type& off) { array_iterator::_pos += off; return *this; }
        const_iterator& operator-=(const difference_type& off) { array_iterator::_pos -= off; return *this; }

        difference_type operator-(const const_iterator& rhs) const { return array_iterator::_pos - rhs._pos; }

        const_reference operator*()  const { return *array_iterator::_pos; }
        const_pointer   operator->() const { return  array_iterator::_pos; }
    };

    class iterator : public const_iterator
    {
    public:
        using const_iterator::const_iterator;

        //INCREMENT/DECREMENT OPERATORS
        iterator& operator++() { ++array_iterator::_pos; return *this; }
        iterator& operator--() { --array_iterator::_pos; return *this; }
        iterator  operator++(int) { iterator temp(*this); operator++(); return temp; }
        iterator  operator--(int) { iterator temp(*this); operator--(); return temp; }

        //ARITHMETIC OPERATORS
        iterator operator+(const difference_type& off) const { return iterator(array_iterator::_pos + off); }
        iterator operator-(const difference_type& off) const { return iterator(array_iterator::_pos - off); }

        iterator& operator+=(const difference_type& off) { array_iterator::_pos += off; return *this; }
        iterator& operator-=(const difference_type& off) { array_iterator::_pos -= off; return *this; }

        difference_type operator-(const iterator& rhs) const { return array_iterator::_pos - rhs._pos; }

        reference operator*()  const { return *array_iterator::_pos; }
        pointer   operator->() const { return  array_iterator::_pos; }
    };

    class const_reverse_iterator : public array_iterator
    {
    public:
        using array_iterator::array_iterator;

        //INCREMENT/DECREMENT OPERATORS
        const_reverse_iterator& operator++() { --array_iterator::_pos; return *this; }
        const_reverse_iterator& operator--() { ++array_iterator::_pos; return *this; }
        const_reverse_iterator  operator++(int) { const_reverse_iterator temp(*this); operator++(); return temp; }
        const_reverse_iterator  operator--(int) { const_reverse_iterator temp(*this); operator--(); return temp; }

        //ARITHMETIC OPERATORS
        const_reverse_iterator operator+(const difference_type& off) const { return const_reverse_iterator(array_iterator::_pos - off); }
        const_reverse_iterator operator-(const difference_type& off) const { return const_reverse_iterator(array_iterator::_pos + off); }

        const_reverse_iterator& operator+=(const difference_type& off) { array_iterator::_pos -= off; return *this; }
        const_reverse_iterator& operator-=(const difference_type& off) { array_iterator::_pos += off; return *this; }

        difference_type operator-(const const_reverse_iterator& rhs) const { return -(array_iterator::_pos - rhs._pos); }

        const_reference operator*()  const { return *array_iterator::_pos; }
        const_pointer   operator->() const { return  array_iterator::_pos; }

        const_iterator base() const { return const_iterator(array_iterator::_pos); }
    };

    class reverse_iterator : public const_reverse_iterator
    {
    public:
        using const_reverse_iterator::const_reverse_iterator;

        //INCREMENT/DECREMENT OPERATORS
        reverse_iterator& operator++() { --array_iterator::_pos; return *this; }
        reverse_iterator& operator--() { ++array_iterator::_pos; return *this; }
        reverse_iterator  operator++(int) { reverse_iterator temp(*this); operator++(); return temp; }
        reverse_iterator  operator--(int) { reverse_iterator temp(*this); operator--(); return temp; }

        //ARITHMETIC OPERATORS
        reverse_iterator operator+(const difference_type& off) const { return reverse_iterator(array_iterator::_pos - off); }
        reverse_iterator operator-(const difference_type& off) const { return reverse_iterator(array_iterator::_pos + off); }

        reverse_iterator& operator+=(const difference_type& off) { array_iterator::_pos -= off; return *this; }
        reverse_iterator& operator-=(const difference_type& off) { array_iterator::_pos += off; return *this; }

        difference_type operator-(const reverse_iterator& rhs) const { return -(array_iterator::_pos - rhs._pos); }

        reference operator*()  const { return *array_iterator::_pos; }
        pointer   operator->() const { return  array_iterator::_pos; }

        iterator base() const { return iterator(array_iterator::_pos); }  //BUG HERE!!!
    };

public: //public to allow aggregate initialization and no need for constructors!!
    value_type _data[Size == 0 ? 1 : Size];

public:
    //ACCESS FUNCTIONS
    reference front() { return _data[0]; }
    reference back()  { return _data[Size - 1]; }

    const_reference front() const { return _data[0]; }
    const_reference back()  const { return _data[Size - 1]; }

    reference operator[](const size_type& index)       
    {   //bounds checking regardless of C++ standard
        if (index < 0 || index >= Size)
            throw std::out_of_range("Index out of bounds!");

        return _data[index]; 
    }

    const_reference operator[](const size_type& index) const 
    {
        if (index < 0 || index >= Size)
            throw std::out_of_range("Index out of bounds!");

        return _data[index]; 
    }

    reference       at(const size_type& index)       { return operator[](index); }
    const_reference at(const size_type& index) const { return operator[](index); }

    template<std::size_t Index> //get<> to be preferred over [] or .at() because it offers
    reference get()                 //compile-time bounds checking
    {
        static_assert(Index >= 0 && Index < Size, "blew::array::get<>() Invalid index!");
        return _data[Index];
    }

    template<std::size_t Index>
    const_reference get() const
    {
        static_assert(Index >= 0 && Index < Size, "blew::array::get<>() Invalid index!");
        return _data[Index];
    }

    pointer data()             noexcept { return _data; }
    const_pointer data() const noexcept { return _data; }

    //CAPACITY FUNCTIONS
    constexpr size_type size()     const noexcept { return Size; }
    constexpr size_type max_size() const noexcept { return Size; }
    constexpr bool      empty()    const noexcept { return !Size; }

    //ITERATORS
    iterator begin() noexcept { return iterator(_data); }
    iterator end()   noexcept { return iterator(_data + Size); }

    const_iterator begin() const noexcept { return const_iterator(const_cast<pointer>(_data)); }
    const_iterator end()   const noexcept { return const_iterator(const_cast<pointer>(_data + Size)); }

    const_iterator cbegin() const noexcept { return const_iterator(const_cast<pointer>(_data)); }
    const_iterator cend()   const noexcept { return const_iterator(const_cast<pointer>(_data + Size)); }

    //REVERSE ITERATORS
    reverse_iterator rbegin() noexcept { return reverse_iterator(_data + Size - 1); }
    reverse_iterator rend()   noexcept { return reverse_iterator(_data - 1); }

    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(const_cast<pointer>(_data + Size - 1)); }
    const_reverse_iterator rend()   const noexcept { return const_reverse_iterator(const_cast<pointer>(_data - 1)); }

    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(const_cast<pointer>(_data + Size - 1)); }
    const_reverse_iterator crend()   const noexcept { return const_reverse_iterator(const_cast<pointer>(_data - 1)); }

    //OTHER FUNCTIONS AND ALGORITHMS
    void swap(array& rhs) noexcept 
    {   //std::swap calls std::swap_ranges
        std::swap(*this, rhs); 
    }

    //fill
    void fill(const value_type& val)
    {
        for (size_type i = 0; i < Size; ++i)
            _data[i] = val;
    }

    //assign
    void assign(const value_type& val)
    {
        for (size_type i = 0; i < Size; ++i)
            _data[i] = val;
    }

    template<class InputIt,
    class = std::enable_if_t<
        std::is_convertible<value_type, typename std::iterator_traits<InputIt>::value_type>::value
    >>
    void assign(InputIt first, InputIt last)
    {
        size_type i = 0;
        for (; first != last; ++first)
            _data[i++] = *first;
    }

    //replace
    void replace(const value_type& val, const value_type& other_val)
    {
        for (size_type i = 0; i < Size; ++i)
        {
            if (_data[i] == val)
                _data[i] = other_val;
        }
    }

    template<class Predicate>
    void replace_if(Predicate predicate, const value_type& other_val)
    {
        for (size_type i = 0; i < Size; ++i)
        {
            if (predicate(_data[i]))
                _data[i] = other_val;
        }
    }

    template<class Predicate>
    void replace_if_not(Predicate predicate, const value_type& other_val)
    {
        for (size_type i = 0; i < Size; ++i)
        {
            if (!predicate(_data[i]))
                _data[i] = other_val;
        }
    }

    //count
    size_type count(const value_type& val)
    {
        size_type counter = 0;
        for (size_type i = 0; i < Size; ++i)
        {
            if (_data[i] == val)
                ++counter;
        }
        return counter;
    }

    template<class Predicate>
    size_type count_if(Predicate predicate)
    {
        size_type counter = 0;
        for (size_type i = 0; i < Size; ++i)
        {
            if (predicate(_data[i]))
                ++counter;
        }
        return counter;
    }

    template<class Predicate>
    size_type count_if_not(Predicate predicate)
    {
        size_type counter = 0;
        for (size_type i = 0; i < Size; ++i)
        {
            if (!predicate(_data[i]))
                ++counter;
        }
        return counter;
    }

    template<class Predicate = std::less<>>
    void sort(Predicate predicate)
    {
        std::sort(_data, _data + Size, predicate);
    }

    //FRIEND FUNCTIONS
    //RELATIONAL OPERATORS ON blew::array<T, N>
    friend bool operator==(const array& lhs, const array& rhs)
    {
        return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
    }

    friend bool operator!=(const array& lhs, const array& rhs)
    {
        return !std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
    }

    friend bool operator<(const array& lhs, const array& rhs)
    {
        return std::lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
    }

    friend bool operator>(const array& lhs, const array& rhs)
    {
        return std::lexicographical_compare(lhs.cbegin(), lhs.cend(),
                                            rhs.cbegin(), rhs.cend(), std::greater<>());
    }

    friend bool operator<=(const array& lhs, const array& rhs)
    {
        return operator==(lhs, rhs) || operator<(lhs, rhs);
    }

    friend bool operator>=(const array& lhs, const array& rhs)
    {
        return operator==(lhs, rhs) || operator>(lhs, rhs);
    }
};  


//NON-MEMBER FUNCTIONS
template<std::size_t Index, class ArrType, std::size_t Size> constexpr
ArrType& get(array<ArrType, Size>& arr) noexcept
{
    return arr.get<Index>();
}

template<std::size_t Index, class ArrType, std::size_t Size> constexpr
const ArrType& get(const array<ArrType, Size>& arr) noexcept
{
    return arr.get<Index>();
}
\$\endgroup\$
1
7
\$\begingroup\$

Bugs:

  1. Your iterators default-constructor is bad: You need to set the member-pointer to nullptr!

  2. Your iterators are missing the index-operator.

Iterators:

  1. You should read about SCARY iterators. The standard-library uses them for versatility and avoidance of duplicate code: What are SCARY iterators?

    In a nutshell, your iterators should only be dependent on the type-argument, not on the length-argument.

  2. There is no reason to write your own reverse-iterators.
    Just use std::reverse_iterator.

  3. There's also no reason to have a separate const_iterator-template once you use SCARY iterators: Just use a normal iterator with a constant value-type.

    If you want to enable assignment from non-constant to constant iterators, add a free-function user-defined conversion.


  1. Your template-arguments have curious names. T and N would be customary.

  2. "bounds checking regardless of C++ standard": Thanks for not making it noexcept, and thus breaking everyones expectations.
    Also, what do you expect the calling code to do when it gets an impossible exception?
    Just std::terminate() directly on detecting such internal corruption.

  3. at now should have bounds-checking and throw on out-of-bound-access. As it's more complicated than a simple field-access, you should implement the non-const version in terms of the const version, using a const_cast. Not the other way around, that would violate the standard, strictly speaking.

  4. front and back should just call std::terminate if N == 0, as calling them is a bug.

  5. I suggest you prefer SFINAE on the return-type instead of using an additional template-argument. That way, it isn't part of the symbol-name.

  6. You are missing many opportunities for marking things noexcept and/or constexpr.

  7. I wouldn't add so many algorithms as member-functions, as the free function algorithms in the standard library are perfectly adequate.

  8. If a type is cheap to copy, prefer passing it by value.

\$\endgroup\$
2
  • \$\begingroup\$ I could not find much good information about SCARY iterators. But as far as I could understand, I just have a single iterator class and then: using iterator = scary_iterator<T>; and using const_iterator = scary_iterator<const T>;. I managed to get that far. But then how would I make const_iterator constructible from iterator? \$\endgroup\$ – DeiDei Dec 6 '15 at 21:59
  • \$\begingroup\$ Well, first of all, that isn't in the iterator-requirements, so not strictly neccessary. Aside from that, just add a user-defined conversion: template<class T> constexpr operator iterator<const T>(iterator<T> x) noexcept { return iterator<const T>(x.operator->()); } \$\endgroup\$ – Deduplicator Dec 6 '15 at 22:05

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.