6
\$\begingroup\$

I present my implementation of an "ArrayView".

I am totally aware the standard nowadays provides such facilities, but for the purpose of learning generic template coding (or is template meta programming anyway) I tried to implement my very own version.

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 is the code:

namespace jsl::core::types
{
    template<typename Type>
    class ArrayView
    {
     public:

    using Self = ArrayView<Type>;
    using value_type = Type;
    using reference = value_type&;
    using pointer = value_type*;
    using pointerconst = value_type const*;

The first portion of my class is simply here to help to make the code more readable, at least for me.

Now the interesting part starts:

    constexpr ArrayView() noexcept : mSize{ 0 }, mBegin{ nullptr } {}

    template<typename ContainerType>
    constexpr ArrayView(const ContainerType& ar) noexcept
        : mBegin{ ar.begin() }, mSize{ ar.size() } {
    static_assert(std::is_member_function_pointer<decltype(&ContainerType::begin)>::value
            && std::is_member_function_pointer<decltype(&ContainerType::end)>::value, "ArrayView: Not a containertype");
    }

    template<typename T, std::size_t N>
    constexpr ArrayView(T(&seq)[N]) noexcept : mSize{ N }, mBegin{ seq } {
    }

    constexpr ArrayView(Type* raw_ptr, std::size_t SizeInBytes) noexcept : mSize{ SizeInBytes }, mBegin{ raw_ptr } {}

It has four constructors in total; the first one is very self-explanatory, I hope. The second one might need some clarification: it expects a container type which follows the C++ standard.

To assure the user, mostly me, that this is really the case, I do a static assert. If it is not an container type, I emit a customized error message; that is the reason for the static assert to be kept in code, otherwise there would no need because the compiler would anyway complain that the type I put in has no begin or end function like I require it to have.

The third one is syntactically interesting. I ensure that my ArrayView can handle 'raw' arrays given to it. And, last but not least, the fourth constructor is there to allow the user to initialize the required fields for an ArrayView by hand.

    constexpr pointer begin() const noexcept { return { const_cast<pointer>(&mBegin[0]) }; }
    constexpr pointer end() const noexcept { return { const_cast<pointer>(mBegin + size()) };; }        

For reasons I do not yet fully understand nor follow, without the const_cast I cannot use this function if it marked as const. It regards the value given by &mBegin[0] as const, which requires me to remove the const qualifier. That is something which needs some sort of explanation which I cannot provide, sorry. Otherwise, I think these member functions are quite self-explanatory.

    constexpr pointerconst cbegin()  noexcept { return mBegin; }
    constexpr pointerconst cend()  noexcept { return mBegin + size(); }

    constexpr pointer front() noexcept { return mBegin; }
    constexpr pointer back() noexcept { return mBegin + size() - 1; }

    constexpr pointerconst cfront()  noexcept { return mBegin; }
    constexpr pointerconst cback()  noexcept { return mBegin + size() - 1; }

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

The index operator is very raw at the moment. I wish I could do static_assert, but for that I would need it to be an template function so my index would be a compile time constant, so for now it is just this:

    constexpr value_type operator[](std::size_t index) const {
        //assert(index > mSize)
            return mBegin[index];

    };

The find function takes any arbitrary sequence which looks like a 'raw' array and tries to find that exact sequence within the view; it returns a view of the matched sequence:

    template<typename Ar, std::size_t N>
    constexpr ArrayView<Type> find(Ar(&sequence)[N]) const noexcept {
        for (auto i = 0u; i <= (size() - N); i++) {
            bool foundView = true;

            for (auto j = 0u; j < N; j++) {
                if (sequence[j] != mBegin[i + j]) {
                    foundView = false;
                    break;
                }

                // Sub view found - return new array view 
                if (foundView) {
                    return { mBegin + i,N };
                }
            }
        }

        return {};
    }

    template<typename ContainerType>
    constexpr ArrayView<Type> find(ContainerType& sequence)const noexcept {

        static_assert(std::is_member_function_pointer<decltype(&ContainerType::begin)>::value
            && std::is_member_function_pointer<decltype(&ContainerType::end)>::value
            && std::is_member_function_pointer<decltype(&ContainerType::operator [])>::value,
            "ArrayView: Not a containertype-> Sequence Type");


        for (auto i = 0u; i <= (size() - sequence.size()); i++) {
            bool foundView = true;

            for (auto j = 0u; j < sequence.size(); j++) {
                if (sequence[j] != mBegin[i + j]) {
                    foundView = false;
                    break;
                }

                /* Sub view found - return new array view */
                if (foundView) {
                    return { mBegin + i, sequence.size() };
                }
            }
        }

        return {};
    }


    private:

        Type*   mBegin;
        std::size_t mSize;

}; 

Any criticism is welcome :D

//EDIT: did some of the suggestion and put them into code Thanks a lot for your time

Here is the link to an very simple demo but with the complete listing of the code: CompilerExplorer

\$\endgroup\$
  • 1
    \$\begingroup\$ It usually bad to use any cast (as you are telling the compiler you know better than it and to ignore an error). BUT never ever use const_cast to remove const-ness. This is probably the most dangerous cast. A company will never let code that casts away constness into the code base (rejected at code review or by automated tool). It is just to easy to generate undefined behavior at runtime. \$\endgroup\$ – Martin York Oct 2 '17 at 17:58
  • 1
    \$\begingroup\$ Well you learn a new thing everyday. namespace jsl::core::types have not seen that before but it compiles in C++17 but not before. \$\endgroup\$ – Martin York Oct 2 '17 at 18:01
  • \$\begingroup\$ @LokiAstari I know const_cast or any cast are very bad and should be avoided(several sources including stackoverflow and co). But if for instant const_cast is really this bad why is it in the language, which use case exist where this kind of cast is required? just used here get the code compiled... like i wrote i could not explain why it was necessary at that point \$\endgroup\$ – ExOfDe Oct 2 '17 at 18:38
  • 1
    \$\begingroup\$ Sometimes adding const is useful. For that you need a const cast. Not all the features of a language need to be useful to the average programmer. But sometimes I may need that scalpel to do something that I would never let any of the junior developers in the company do. Though I have yet to find a use for casting away const and have only every used goto twice in 30 years. Just because they are there does not mean you should use them. \$\endgroup\$ – Martin York Oct 2 '17 at 19:06
  • \$\begingroup\$ @LokiAstari: Funny; just today, I had to cast away const. Why? Because I was writing an implementation of vector::erase, which takes const_iterators. And it's easier to cast away that const T* to a T* than it is to do the math to compute the non-const T* equivalent directly. You need a non-const T*, because you're going to be modifying the object: potentially copying/moving over top of it. \$\endgroup\$ – Nicol Bolas Nov 2 '17 at 6:58
6
\$\begingroup\$

Constructors

The second constructor:

template<typename ContainerType>
constexpr ArrayView(const ContainerType& ar) noexcept
    : mBegin{ ar.begin() }
    , mSize{ ar.size() }
{

    static_assert(
           std::is_member_function_pointer<decltype(&ContainerType::begin)>::value
        && std::is_member_function_pointer<decltype(&ContainerType::end)>::value, "ArrayView: Not a containertype");
}

Had to refactor to read.
But the static assert is checking that begin and end exist and are members. But if begin() is not a member of ar then you will get a compiler error above. So I think the static assert is a waste.

Also in C++14 we added std::begin(), std::end() and in C++17 we added std::size() for exactly this situation. If the parameter supports the method it will work but it also works for C-Arrays.

So I would replace with:

template<typename ContainerType>
constexpr ArrayView(const ContainerType& ar) noexcept
    : mBegin{ std::begin(ar) }
    , mSize{  std::size(ar)  }
{}

If you do it this way then you don't need you third constructor.

template<typename T, std::size_t N>
constexpr ArrayView(T(&seq)[N]) noexcept
    : mSize{ N }
    , mBegin{ seq } 
{}

Which brings me to your formatting. Your code is really hard to read. Use the same rules for parameters that you would for normal variables. There is no extra points for minimizing vertical size.

Your fourth constructor is good. But to be complete you may want to add a fifth to handle the nullptr (as it is not a pointer type, just convertable to a pointer type). But

 ArrayPtr<T>  a(nullptr, 0); // will not compile at the moment.

If you were talking about normal code I would not consider it that necessary, but you mentioned template meta programming in your prolog. In heavy templated code the pointer object may be swapped out for the literal nullptr and in this case, so I would still want the above to compile.

constexpr ArrayView(std::nullptr_t) noexcept
    : mBegin{ nullptr }
    , mSize{ 0 }
{}

Iterators

A naming thing. Iterators should not have a type pointer. Pointer may be a type of iterator but it is not an iterators type.

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

Given this I would expect the following iterators:

iterator       begin();
iterator       end();
const_iterator begin()  const;   // Missing these two in the middle.
const_iterator end()    const;   // 
const_iterator cbegin() const;
const_iterator cend()   const;

Front/Back

The methods front() and back() should return references to elements (not pointers or iterators). This will make your type consistent with other container types (and thus interchangeable).

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

reference front();
reference back();
const_reference front()  const;
const_reference back()   const;
const_reference cfront() const;
const_reference cback()  const;

Indexed Access

constexpr value_type operator[](std::size_t index) const {
    //assert(index > mSize)
        return mBegin[index];

};

The operator[]() should return a reference to the object (so it can be updated in place). As such it is not normally const. Also this method is usually unchecked if you want a checked version you should add the method at().

reference operator[](std::size_t index) {
        return mBegin[index];
};
const_reference operator[](std::size_t index) const {
        return mBegin[index];
};
reference at(std::size_t index) {
        // Add validation code here
        return mBegin[index];
};
const_reference at(std::size_t index) const {
        // Add validation code here
        return mBegin[index];
};
\$\endgroup\$
  • \$\begingroup\$ You wrote my static_assert within the ctors is a waste. I agree because i wrote that in the post as well, would be crazy to disagree. The only reason was to receive a personalized error message. Thats the reason why i kept in code. ||std::begin() and std::end() i haven't really used them and that std::size now exist i wasn't aware. so i kind of overlooked that possibility. And I must agree if saves writing ctor, that is kind of nice especially with this really weird syntax for arrays. || About the naming. I have to say makes sense what you say. I will change it. Thank you alot for your review. \$\endgroup\$ – ExOfDe Oct 3 '17 at 7:56
2
\$\begingroup\$

The first thing is that you must never compile with -fpermissive. Use -Wall -Wextra -Wconversion -Wpedantic instead. It will give you a lot of helpful hints.

As for constexpr pointer end() const noexcept { return { const_cast<pointer>(mBegin + size()) };; } place, it does not compile properly because you are calling not const-qualified size method. It can be simplified to

constexpr std::size_t size() const noexcept { return mSize; } // this one does not much to version in online compiler
constexpr pointer begin() const noexcept { return mBegin; }
constexpr pointer end() const noexcept { return mBegin + size(); } 

find functions seems to reinvent std::search.

Also if sequence is not an array, vector or some other container with continuous items storage your view will be invalid. So existing checks are not sufficient.

\$\endgroup\$
  • \$\begingroup\$ you are right about the const qualifier.... i have forgotten to update the link, if you read the post or quick the edit history i already corrected. my biggest apology about that and thank you a lot for your time analyzing my code about your last point i haven't thought about it. i will try to fix it \$\endgroup\$ – ExOfDe Oct 2 '17 at 16:57
  • \$\begingroup\$ updated your suggestions on the example and put the most recent link into the post \$\endgroup\$ – ExOfDe Oct 2 '17 at 17:07
  • \$\begingroup\$ again to the last point Adding && std::is_member_function_pointer<decltype(&ContainerType::operator [])>::value should do the job because this operator i do utilize and if not misoverloaded should mean the underlying class is a sequence isn't it \$\endgroup\$ – ExOfDe Oct 2 '17 at 17:15
  • \$\begingroup\$ @ExOfDe std::map has begin, end and operator[], but won't work as sequence. I guess it would be better to check for data(). \$\endgroup\$ – VTT Oct 2 '17 at 17:18
  • \$\begingroup\$ your are right, here an link of the container-library-overview for other people who will read this post \$\endgroup\$ – ExOfDe Oct 2 '17 at 17:29

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.