3
\$\begingroup\$

I present my implementation of an HeapArray and StackArray.

Similar to the implementation of my ArrayView which justs open a window into sequence here a generic implementation of an actual sequence. I have to admit both classes(ArrayView and Stack/HeapArray) look very similar but they are supposed do to a very similar job, so i think that was not avoidable.

As always my aim was to avoid any runtime operation as far as possible, so that the compiler can resolve most of the code at compile-time, here in this particular case it is not as easy to follow this policy which lies in the nature of runtime allocation for the HeapArray implemenation where the StackArraycan be resolved mostly at compiletime similar to std::array.

Both classes have the same interface the only real difference is the way the array is allocated. The StackArray allocates the requested array at compile-time as normal c-like array in the form of type Field[Size] while HeapArray handles the the array dynamically via the special overload oif std::unique_ptr<type[]>. I am not sure if that is good or bad use of this specialization of std::unique_ptr but i like the idea quite a lot not to use new/delete myself in a direct manner. I could imagine this could be point of critic but maybe not.

As usual any criticism are welcome and is much appreciated.

You will find an code example at CompilerExplorer

The HeapArray:

template<typename T,std::size_t SIZE>
class HeapArray {

private:
    std::unique_ptr<T[]>            mField;

public:
    using Self = HeapArray<T, SIZE>;
    using value_type = T;
    using pointer = value_type*;
    using reference = value_type&;
    using const_reference = value_type const&;
    using iterator = value_type*;
    using const_iterator = value_type const*;

    template<typename ...Targs>
    constexpr HeapArray(Targs... args) 
    : mField{std::make_unique<value_type[]>(sizeof...(Targs))}
        //: mField{std::make_unique<value_type[]>(sizeof(value_type)*sizeof...(Targs))}
        {   
            //If you know a better way of initialize this array please let me know
            auto list = {args...};
            auto iter = std::begin(list);
            for(auto i = 0ull; i < SIZE;i++,std::next(iter))
            {
                mField[i] = *iter;
            }

    }

    reference operator[](std::size_t index) {
        return mField[index];
    };
    const_reference operator[](std::size_t index) const {
        return mField[index];
    };

    reference at(std::size_t index) {
        assert(index > SIZE);
        return mField[index];
    };
    const_reference at(std::size_t index) const {
        assert(index >SIZE);
        return mField[index];
    };

    template<std::size_t Index>
    constexpr value_type at() const {
        static_assert(Index > SIZE, "Index out of bound");
        return mField[Index];
    }

    constexpr pointer data() const { return mField; }

    constexpr bool operator==(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] != rhs.at(i)) return false;
        return true;
    };
    constexpr bool operator<(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] > rhs[i]) return false;
        return true;
    };
    constexpr bool operator>(const Self& rhs)const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] < rhs[i]) return false;
        return true;
    };
    constexpr bool operator<=(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] >= rhs[i]) return false;
        return true;
    };
    constexpr bool operator>=(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] <= rhs[i]) return false;
        return true;
    };

    constexpr iterator begin()  noexcept { return (mField); }
    constexpr iterator end()  noexcept { return mField + SIZE; }

    constexpr const_iterator begin() const noexcept { return (mField); }
    constexpr const_iterator end() const noexcept { return mField + SIZE; }

    constexpr const_iterator cbegin() const noexcept { return { mField }; }
    constexpr const_iterator cend() const noexcept { return mField + SIZE; }

    constexpr reference front() noexcept { return *mField; }
    constexpr reference back() noexcept { return *(mField + SIZE - 1); }
    constexpr const_reference cfront() const noexcept { return *mField; }
    constexpr const_reference cback() const noexcept { return *(mField + SIZE - 1); }


    constexpr const_iterator find_first_of(value_type data) const noexcept{
        for (auto i = 0; i < SIZE; i++)
            if (mField[i] == data)
                return &mField[i];
        return nullptr;
    }

    /*template<typename predicate>
    auto find_all(predicate Functor) const noexcept{    
        static_assert(!std::is_function< decltype(Functor)>::value , "find_all() of 'HeapArray' expects as predicate a function!" );
        GenericList<T> res;
        for (auto i = 0u; i < SIZE; i++)
            if (Functor(mField[i]))
                res.addTail(mField[i]);
        return res;
    }*/

    constexpr void fill(const_reference Value)  noexcept{
        for (auto& item : *this)
            item = Value;
    }

    template<typename predicate>
    constexpr void apply(predicate Functor) noexcept{
        static_assert(!std::is_function< decltype(Functor)>::value, "apply() of 'HeapArray' expects as predicate a function!");
        for (auto& item : *this)
            Functor(item);
    }


};

The StackArray:

template<typename T, std::size_t SIZE>
class StackArray {

private:
    T           mField[SIZE];


public:
    using Self = StackArray<T, SIZE>;
    using value_type = T;
    using pointer = value_type*;

    using reference = value_type&;
    using const_reference = value_type const&;

    using iterator = value_type*;
    using const_iterator = value_type const*;

    template<typename ...Targs>
    constexpr StackArray(Targs... args) : mField{ std::forward<value_type>(args)... } {}

    reference operator[](std::size_t index) {
        return mField[index];
    };
    const_reference operator[](std::size_t index) const {
        return mField[index];
    };

    reference at(std::size_t index) {
        assert(index > SIZE);
        return mField[index];
    };
    const_reference at(std::size_t index) const {
        assert(index > size());
        return mField[index];
    };

    template<std::size_t Index>
    constexpr value_type at() const {
        static_assert(Index > SIZE, "Index out of bound");
        return mField[Index];
    }

    constexpr bool operator==(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] != rhs.at(i)) return false;
        return true;
    };
    constexpr bool operator<(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] > rhs[i]) return false;
        return true;
    };
    constexpr bool operator>(const Self& rhs)const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] < rhs[i]) return false;
        return true;
    };
    constexpr bool operator<=(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] >= rhs[i]) return false;
        return true;
    };
    constexpr bool operator>=(const Self& rhs) const noexcept {
        for (int i = 0; i < SIZE; i++)
            if (mField[i] <= rhs[i]) return false;
        return true;
    };




    constexpr pointer data() const { return mField; }


    constexpr iterator begin()  noexcept { return (mField); }
    constexpr iterator end()  noexcept { return mField + SIZE; }

    constexpr const_iterator begin() const noexcept { return (mField); }
    constexpr const_iterator end() const noexcept { return mField + SIZE; }

    constexpr const_iterator cbegin() const noexcept { return { mField }; }
    constexpr const_iterator cend() const noexcept { return mField + SIZE; }

    constexpr reference front() noexcept { return *mField; }
    constexpr reference back() noexcept { return *(mField + SIZE - 1); }
    constexpr const_reference cfront() const noexcept { return *mField; }
    constexpr const_reference cback() const noexcept { return *(mField + SIZE - 1); }


    constexpr  std::size_t size() const  noexcept { return SIZE; }
    constexpr  std::size_t length() const noexcept { return SIZE; }

    constexpr const_iterator find_first_of(value_type data) const noexcept {
        for (auto i = 0; i < size(); i++)
            if (mField[i] == data)
                return &mField[i];
        return nullptr;
    }

    /*template<typename predicate>
    constexpr auto find_all(predicate Functor) noexcept {
        static_assert(!std::is_function< decltype(Functor)>::value, "find_all() of 'StackArray' expects as predicate a function!");
        GenericList<T> res;
        for (auto i = 0u; i < size(); i++)
            if (Functor(mField[i]))
                res.addTail(mField[i]);
        return res;
    }*/

    constexpr void fill(const_reference Value) noexcept {
        for (auto& item : *this)
            item = Value;
    }

    template<typename predicate>
    constexpr void apply(predicate Functor) noexcept {
        static_assert(!std::is_function< decltype(Functor)>::value, "apply() of 'StackArray' expects as predicate a function!");
        for (auto& item : *this)
             Functor(item);
    }


};
\$\endgroup\$
5
\$\begingroup\$

Personally I would implement those as this:

template <typename T, std::size_t size>
using stack_array = std::array<T, size>;

template <typename T, std::size_t size>
struct heap_array
{
    //some delegates
    //get the size from template parameter
}

My main concern is that code has very low expression effectiveness. In other words, a lot of code that can be compressed without losing effectiveness. More code means more stuff to maintain, which means more headache.

It is good to know template metaprogramming. But one also needs to know how to apply it effectively. Just try to find a problem for which templates would be fit. SFINAE, range based algorithms, lexical cast (personally I wouldn't want to deal with the latter).

Unfortunately many people are scared of templates. In my opinion, the most productive thing to do right now is to teach templates to people you know. That way, they'll get more adoption, and as a result the stuff you do won't be a waste. This is what I do.

Darkness

Your stack array does not deal with alignment. It is gonna be a problem in certain cases, when people do some undefined/unspecified stuff. I'm not sure if new deals with this.

Culprits:

The code does not do forwarding. Usually that's what should be done, in a generic case.

constexpr HeapArray(Targs&& ... args) 

And then

auto list = {std::forward<Targs>(args)...};

Also your heap array does not provide allocator or some other customizable allocation mechanisms. This would be a much better template metaprogramming exercise.


Redesign:

It is better to abstract away storage and operations performed on them:

template <typename Storage>
class array_ops
{
    Storage store;
public:
    using Storage::Storage; //I believe this is what used to grab constructor of parent

    // operations ...
    // and type aliases
}

And then this is what Storage should adhere to

  • Always define data(), which will return pointer to data

  • constexpr std::size_t size(), so that the ops could be constexpr too.

Then, HeapArray's storage will turn into:

template <typename T, std::size_t size>
class array_on_heap
{
    std::unique_ptr<T[]> array; //note that this relies on absence of using namespace std
public:
    //the same constructor

    T* data()
    {
        return array.get();
    }
}

I'll omit array on stack, since it is std::array. If you want you can reimplement it.

Then, to make it more user friendly, you can alias frequent used types:

template <typename T, std::size_t size>
using heap_array = array_ops<array_on_heap<T, size>>;

//ditto for stack_array
\$\endgroup\$
  • 1
    \$\begingroup\$ I'll post policy based design later. Roommates are sleeping, and I'm using mechanical keyboard. \$\endgroup\$ – Incomputable Oct 3 '17 at 19:02
  • \$\begingroup\$ Thanks a lot for your input. I think i agree about the low expression effectivness of the code. But then right now it is only very simple exercise to get into the feeling to tmp and slowly but steady attack those points e.g. you pointed out and more. My plan is over time to improve these classes and their algorithms which come later and add more and more tmp technics . But for this the base must be right and ok, at least thats what i think/belive. \$\endgroup\$ – ExOfDe Oct 3 '17 at 19:04
  • \$\begingroup\$ @ExOfDe, I believe the simplest exercise right now is range destruct. Given range [first, last), run destructor for each. Do note that there are optimizations. This is when Loki demonstrated me the first template metaprogramming. If my programming style looks similar to other's, it is not an accident. The people here taught me most of what I know. \$\endgroup\$ – Incomputable Oct 3 '17 at 22:06
  • \$\begingroup\$ @ExOfDe, I've added new design. \$\endgroup\$ – Incomputable Oct 4 '17 at 8:14
  • \$\begingroup\$ I never thought about decoupling the behaviour from the way it's stored in memory in this case. super interesting way and i will definitely try it out next weekend to rewrite my version additionally. especially the way how you use the aliasing i find fascinating. just hypothetically with that extra layer of indirection given by the alias, as long as i do not break the interface i could now change the underlying class how ever i want... thanks a lot for your time looking over my code \$\endgroup\$ – ExOfDe Oct 4 '17 at 9: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.