8
\$\begingroup\$

I'm creating my own implementation of the STL, compliant with the C++17 standard. The only purposeful differences are that the namespace is hsl (homebrew standard library) to prevent name conflicts, and the headers end in .hpp, so that syntax highlighting will work in my editor. I started with hsl::array because it seemed simplest. I'm mostly happy with it, though I have a few questions:

Is there a way to make the underlying C-style array private? It's my understanding that that would break aggregate initialization, but it seems awfully inelegant just to leave a comment saying "don't use this!"

Should I replace all the Ts and Ns with the appropriate member types? That seems overly verbose to me, especially down below where I implement the member functions, and I would need to type typename array<T, N>::value_type instead of just T.

Is it good practice to place the template implementations in a separate .cpp file, and then include it at the bottom of the header?

And the obvious question: is there any place where I'm violating the standard?

#pragma once

#include "cstddef.hpp"
#include "algorithm.hpp"
#include "iterator.hpp"     // hsl::begin, hsl::end defined here
#include "stdexcept.hpp"
#include "tuple.hpp"
#include "type_traits.hpp"
#include "utility.hpp"

namespace hsl
{

template<typename T, size_t N>
class array
{
public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = T*;
    using const_iterator = const T*;
    using reverse_iterator = hsl::reverse_iterator<T*>;
    using const_reverse_iterator = hsl::reverse_iterator<const T*>;
    using size_type = size_t;
    using difference_type = ptrdiff_t;


    // Must be public for aggregate initialization to work.
    // Don't access it directly; use data() method, instead.
    T arr[N];


    // Iterators
    constexpr T* begin() noexcept;
    constexpr const T* begin() const noexcept;

    constexpr T* end() noexcept;
    constexpr const T* end() const noexcept;

    constexpr const T* cbegin() const noexcept;
    constexpr const T* cend() const noexcept;

    constexpr hsl::reverse_iterator<T*> rbegin() noexcept;
    constexpr hsl::reverse_iterator<const T*> rbegin() const noexcept;

    constexpr hsl::reverse_iterator<T*> rend() noexcept;
    constexpr hsl::reverse_iterator<const T*> rend() const noexcept;

    constexpr hsl::reverse_iterator<const T*> crbegin() const noexcept;
    constexpr hsl::reverse_iterator<const T*> crend() const noexcept;


    // Capacity
    constexpr size_t size() const noexcept;
    constexpr size_t max_size() const noexcept;
    constexpr bool empty() const noexcept;


    // Element access
    constexpr T& operator[] (size_t n);
    constexpr const T& operator[] (size_t n) const;

    constexpr T& at(size_t n);
    constexpr const T& at(size_t n) const;

    constexpr T& front();
    constexpr const T& front() const;

    constexpr T& back();
    constexpr const T& back() const;

    constexpr T* data() noexcept;
    constexpr const T* data() const noexcept;


    // Modifiers
    void fill(const T& val);
    void swap(array<T, N>& other) noexcept(is_nothrow_swappable<T>::value);
};


// Tuple helper class specializations

template<size_t I, typename T, size_t N>
struct tuple_element<I, array<T, N> >
{
    using type = T;
};

template<typename T, size_t N>
struct tuple_size<array<T, N> > : public integral_constant<size_t, N> {};


// Relational operators

template<typename T, size_t N>
bool operator== (const array<T, N>& lhs, const array<T, N>& rhs);

template<typename T, size_t N>
bool operator< (const array<T, N>& lhs, const array<T, N>& rhs);

template<typename T, size_t N>
bool operator!= (const array<T, N>& lhs, const array<T, N>& rhs);

template<typename T, size_t N>
bool operator<= (const array<T, N>& lhs, const array<T, N>& rhs);

template<typename T, size_t N>
bool operator> (const array<T, N>& lhs, const array<T, N>& rhs);

template<typename T, size_t N>
bool operator>= (const array<T, N>& lhs, const array<T, N>& rhs);


// Tuple-style get

template<size_t I, typename T, size_t N>
constexpr T& get(array<T, N>& arr) noexcept;

template<size_t I, typename T, size_t N>
constexpr T& get(array<T, N>&& arr) noexcept;

template<size_t I, typename T, size_t N>
constexpr const T& get(const array<T, N>& arr) noexcept;


// Template member function implementations

// Iterators

template<typename T, size_t N>
constexpr T* array<T, N>::begin() noexcept { return arr; }

template<typename T, size_t N>
constexpr const T* array<T, N>::begin() const noexcept { return arr; }

template<typename T, size_t N>
constexpr T* array<T, N>::end() noexcept { return arr+N; }

template<typename T, size_t N>
constexpr const T* array<T, N>::end() const noexcept { return arr+N; }

template<typename T, size_t N>
constexpr const T* array<T, N>::cbegin() const noexcept { return arr; }

template<typename T, size_t N>
constexpr const T* array<T, N>::cend() const noexcept { return arr+N; }

template<typename T, size_t N>
constexpr reverse_iterator<T*> array<T, N>::rbegin() noexcept { return hsl::reverse_iterator<T*>(end()); }

template<typename T, size_t N>
constexpr reverse_iterator<const T*> array<T, N>::rbegin() const noexcept
{
    return hsl::reverse_iterator<const T*>(end());
}

template<typename T, size_t N>
constexpr reverse_iterator<T*> array<T, N>::rend() noexcept { return hsl::reverse_iterator<T*>(begin()); }

template<typename T, size_t N>
constexpr reverse_iterator<const T*> array<T, N>::rend() const noexcept
{
    return hsl::reverse_iterator<const T*>(begin());
}

template<typename T, size_t N>
constexpr reverse_iterator<const T*> array<T, N>::crbegin() const noexcept
{
    return hsl::reverse_iterator<const T*>(cend());
}

template<typename T, size_t N>
constexpr reverse_iterator<const T*> array<T, N>::crend() const noexcept
{
    return hsl::reverse_iterator<const T*>(cbegin());
}


// Capacity

template<typename T, size_t N>
constexpr size_t array<T, N>::size() const noexcept { return N; }

template<typename T, size_t N>
constexpr size_t array<T, N>::max_size() const noexcept { return N; }

template<typename T, size_t N>
constexpr bool array<T, N>::empty() const noexcept { return !N; }


// Element access

template<typename T, size_t N>
constexpr T& array<T, N>::operator[] (size_t n) { return arr[n]; }

template<typename T, size_t N>
constexpr const T& array<T, N>::operator[] (size_t n) const { return arr[n]; }

template<typename T, size_t N>
constexpr T& array<T, N>::at(size_t n)
{
    if (n >= N) throw out_of_range("hsl::array::at");
    return arr[n];
}

template<typename T, size_t N>
constexpr const T& array<T, N>::at(size_t n) const
{
    if (n >= N) throw out_of_range("hsl::array::at");
    return arr[n];
}

template<typename T, size_t N>
constexpr T& array<T, N>::front() { return arr[0]; }

template<typename T, size_t N>
constexpr const T& array<T, N>::front() const { return arr[0]; }

template<typename T, size_t N>
constexpr T& array<T, N>::back() { return arr[N-1]; }

template<typename T, size_t N>
constexpr const T& array<T, N>::back() const { return arr[N-1]; }

template<typename T, size_t N>
constexpr T* array<T, N>::data() noexcept { return arr; }

template<typename T, size_t N>
constexpr const T* array<T, N>::data() const noexcept { return arr; }


// Modifiers

template<typename T, size_t N>
void array<T, N>::fill (const T& val) { for (auto& x : arr) x = val; }

template<typename T, size_t N>
void array<T, N>::swap(array<T, N>& other) noexcept(is_nothrow_swappable<T>::value)
{
    for (auto it1 = begin(), it2 = other.begin(); it1 != end(); ++it1, ++it2)
    {
        hsl::swap(*it1, *it2);
    }
}


// Template non-member function implementations

// Relational operators

template<typename T, size_t N>
bool operator== (const array<T, N>& lhs, const array<T, N>& rhs)
{
    return equal(lhs.begin(), lhs.end(), rhs.begin());
}

template<typename T, size_t N>
bool operator< (const array<T, N>& lhs, const array<T, N>& rhs)
{
    return lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template<typename T, size_t N>
bool operator!= (const array<T, N>& lhs, const array<T, N>& rhs) { return !(lhs == rhs); }

template<typename T, size_t N>
bool operator<= (const array<T, N>& lhs, const array<T, N>& rhs) { return !(rhs < lhs); }

template<typename T, size_t N>
bool operator> (const array<T, N>& lhs, const array<T, N>& rhs) { return rhs < lhs; }

template<typename T, size_t N>
bool operator>= (const array<T, N>& lhs, const array<T, N>& rhs) { return !(lhs < rhs); }


// Tuple-style get

template<size_t I, typename T, size_t N>
constexpr T& get(array<T, N>& arr) noexcept
{
    static_assert(I < N, "I must be less than N");
    return arr[I];
}

template<size_t I, typename T, size_t N>
constexpr T& get(array<T, N>&& arr) noexcept
{
    static_assert(I < N, "I must be less than N");
    return arr[I];
}

template<size_t I, typename T, size_t N>
constexpr const T& get(const array<T, N>& arr) noexcept
{
    static_assert(I < N, "I must be less than N");
    return arr[I];
}

}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. I suggest you to edit your post, as it currently sounds like your array reimplementation might not work. Avoid words like "try" in your description and add a little bit more context, e.g. do you want to match std::array's interface exactly, where there any special design decisions and so on. \$\endgroup\$ – Zeta Nov 10 '18 at 8:12
  • \$\begingroup\$ Including a CPP file from an header file is not a good practice as it is not what people expect. \$\endgroup\$ – Phil1970 Nov 10 '18 at 23:53
  • \$\begingroup\$ Reinventing the wheel is not a good idea. By the time, you got it working it will be obsolete! And it might cause more problem that it solve. If you have a problem with your editor, then change your editor before duplicating the library! \$\endgroup\$ – Phil1970 Nov 10 '18 at 23:56
6
\$\begingroup\$

Regarding the standard compliance:

  1. empty should better be [[nodiscard]]
  2. You are missing the deduction guide:

    template<class T, class... U> array(T, U...) -> array<T, 1 + sizeof...(U)>
    

    which also must result in an error if (is_same_v<T, U> && ...) is false (e.g. via enable_if relying on there being no other deducible constructor).

  3. tuple_element<I, array<T, N>>::type must result in an error if I >= N (e.g. using static_assert).

  4. constexpr T& get(array<T, N>&& arr) noexcept should return a T&& (e.g. with std::move)
  5. There should be an overload constexpr const T&& get(const array<T, N>&& arr) noexcept.
  6. The specialization for std::swap is missing.
  7. You must handle the case N==0 correctly. Zero length arrays are not standard C++. Also for N==0, begin() and end() must return a unique value and the exception specification of swap must be non-throwing no matter the element type.

Regarding the public data member: At least both libstdc++ and libc++ also use a public data member. There probably is no other way of doing it. They declare them with implementation-reserved identifiers like __elemens_. In any case programs are not allowed to use these additional members.

\$\endgroup\$
4
\$\begingroup\$

You said that you want your version compliant with the one from C++17. But with a backward compatibility (C++11, C++14) or do you only aim C++17 and above? (just to be sure)

  • It would be better if you written full include guards instead the non-standard #pragma directive (more info)

  • Maybe try to mimic std::iterator_traits for iterator and const_iterator

  • Does size_t and ptrdiff_t the ones from std:: or do you redefined them? maybe try to full-qualify them.

  • In C++17, I think deduction guides are the solution for your first question about construction from a variadic parameter pack.

  • Use your type aliases:

    • Return type would be iterator and const_iterator instead of T* and const T*
    • Same for reference and const_reference instead of T& and const T&
    • Same size_type instead of size_t
    • Same pointer and const_pointer instead of T* and const T*
  • empty() can be made [[nodiscard]]
  • In operator[] and at() the param type size_t would be replaced by size_type
\$\endgroup\$
  • \$\begingroup\$ Iterator traits are already defined for pointers - it's not only unnecessary, but not allowed, to reimplement std::iterator_traits for these. \$\endgroup\$ – Toby Speight Nov 12 '18 at 12:23
  • \$\begingroup\$ For #pragma once, I think I would rather use it, even if it isn't standard. It's widely supported, briefer than an include guard, and even in the question you link to, the majority position seems to support it, even if there isn't quite a consensus. \$\endgroup\$ – Bob Carter Nov 12 '18 at 21:15
  • \$\begingroup\$ Also, I did implement iterator_traits for pointers in iterator.hpp. \$\endgroup\$ – Bob Carter Nov 12 '18 at 21:22
  • \$\begingroup\$ @BobCarter that was my opinion, but not only \$\endgroup\$ – Calak Nov 12 '18 at 21:27
  • \$\begingroup\$ For iteraror, you implements it but don't use it as return type. Don't ask for a review if you are looking for excuses for each item discussed. I gave my opinion, that you apply my advice or not, concerns only you. \$\endgroup\$ – Calak Nov 12 '18 at 21:32

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.