7
\$\begingroup\$

In some (lower-level) parts of my codebase I often have the need to allocate resizable array storage for certain objects, that usually are not default-constructible.

I created a simple class using std::aligned_storage and I was wondering if it's safe and if it can be improved.

The user of the class has to keep track of the current capacity.

template<typename T> class ResizableArray
{
    private:
        using TStorage = std::aligned_storage_t<sizeof(T), alignof(T)>;
        TStorage* data{nullptr};

    public:
        ~ResizableArray() { delete[] data; }

        void resize(std::size_t mSizeOld, std::size_t mSizeNew)
        {
            auto newData(new TStorage[mSizeNew]);
            for(auto i(0u); i < mSizeOld; ++i) newData[i] = std::move(data[i]);

            delete[] data;
            data = newData;
        }

    auto& operator[](std::size_t mIdx) noexcept 
    { return reinterpret_cast<T&>(data[mIdx]); }

    const auto& operator[](std::size_t mIdx) const noexcept 
    { return reinterpret_cast<const T&>(data[mIdx]); }
};

Example usage:

int main()
{
    ResizableArray<Thing> a;

    // Resize array capacity from 0 to 10
    a.resize(0, 10);

    for(auto i(0u); i < 10; ++i)
        new (&a[i]) Thing{/* something */};

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Why not using std::vector::reserve() and std::vector::emplace_back()? vector<T> does require T to be default-constructible. \$\endgroup\$ – user52292 Oct 18 '14 at 17:24
  • \$\begingroup\$ std::vector<T> only requires T to be default constructable if you features of vector that use the default constructor. If you don't use those features then this requirement is not required because of SFINAE. So the only thing stopping you using a vector is re-size. Rather than use re-size just reserve and emplace back your elements that you want. \$\endgroup\$ – Martin York Oct 19 '14 at 16:35
  • \$\begingroup\$ Forgot the rule of three. Forgot to make resize provide the strong exception guarantee. \$\endgroup\$ – Martin York Oct 19 '14 at 16:37
5
\$\begingroup\$

I see a couple of problems:

  • If you ever shrink the array, the loop for copying the elements will overrun the bounds of newdata because the index runs from 0 to mSizeOld.

  • You don't store the size of the array in the class, so code like this will lose data:

    ResizeableArray<Thing> a;
    a.resize(0, 10);
    // Populate the array
    a.resize(0, 11);
    // Now a is empty again because resize() uses the first argument.
    

    This might be intentional — to allow you to start over with a fresh set of data &mdash but if so, resize() should be commented to say that.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the review. The array is meant to never be shrunk - I will probably rename it to GrowableArray or something similar. I added an assertion to make sure mSizeOld <= mSizeNew. Not storing the size of the array is intentional (as not calling the items' destructors is) - I will make sure to document that properly. \$\endgroup\$ – Vittorio Romeo Oct 18 '14 at 15:31
  • 1
    \$\begingroup\$ @VittorioRomeo If you are renaming it to GrowableArray, rename the method from resize to add. Instead of 2 parameters, you accept the number of items to add. And prepare a method to get the length of your 'array'. \$\endgroup\$ – Ismael Miguel Oct 19 '14 at 1:19
5
\$\begingroup\$

Ciao Vittorio,

You're looking for safety and improvements, thus I'll give a brief overview of the code and then focus on them.

Overview

  1. You're abusing auto: in a lot of places, you don't really need it such as in for loops.
  2. I can't see any library #include but you'll need at least <memory> and <cstdint>.
  3. Your code will not compile for non DefaultConstructible classes.
  4. There is no way to get the number of elements.
  5. Following #4, it's hard to extract a range from it and/or iterate over it.

Safety

The resize function has some faults:

  1. There is no check against mSizeOld and mSizeNew, therefore mSizeOld can easily be > mSizeNew. mSizeOld should be a member of the class.
  2. If mSizeNew == mSizeOld, elements will be however copied/moved.

Improvement

  1. You could make resize a variadic template in order to create elements with such arguments.
  2. Check for mSizeOld and mSizeNew and throw out_of_range/ if you find something wrong.
\$\endgroup\$
4
\$\begingroup\$

It seems to me that it would be beneficial to store the length of the array as well. It is such a tiny increase in the size of the structure that I really don't see why wouldn't you do it.

If you do keep track of the size, then you could do debug bounds checking inside operator [], which I consider very important.

As it was mentioned, there is a bug in the for loop of resize(), as the new array is allocated with mSizeNew entries and the loop will visit 0 to mSizeOld-1 entries. There is nothing preventing mSizeOld from being greater than mSizeNew.

You could also use a unique_ptr to manage the memory so that you don't have to bother writing an explicit destructor.

Apart from that, good code.

\$\endgroup\$
  • 1
    \$\begingroup\$ (Copy-paste from the above answer) Thanks for the review. The array is meant to never be shrunk - I will probably rename it to GrowableArray or something similar. I added an assertion to make sure mSizeOld <= mSizeNew. Not storing the size of the array is intentional (as not calling the items' destructors is) - I will make sure to document that properly. \$\endgroup\$ – Vittorio Romeo Oct 18 '14 at 15:31
3
\$\begingroup\$

Summary:

  1. rule of three                                   Potentially broken if misused.
  2. Strong Exception Guarantee:        Potentially broken depend on T.

  3. Naming convention:                      Maintenance

  4. Excessive auto keyword:              Maintenance.

Did not implement the rule of three (five)

int func()
{
    ResizableArray<int>   a;
    ResizableArray<int>   b;

    a = b;   // leak `a` original content.
}  // Double delete on pointer.

Did not provide Strong Exception Guarantee

// in resize

        delete[] data;    // If any element throws.
                          // You have lost all your data
                          // and this element is not in a consistent state.

        data = newData;   // and this assignment will never happen.

// Always do it like this:

        swap(data, newData);  // New data is now in the object.
                              // the old data is in `newData`
                              // We have finished updating the state of `this`
                              // So we can now do dangerious things and not
                              // worry too much.

        delete [] newData;    // Even if there is an exception
                              // This object is in a consistent state.

Naming convention.

Personally I am not into abstract naming conventions (as it usually means you have failed in giving your variables (including members) names that make the code obvious to read). But when I do use them I try to use accepted standards:

void resize(std::size_t mSizeOld, std::size_t mSizeNew)

Usually a prefix m or m_ means member variable. These are obviously not members.

Excessive use of the auto keyword

Auto is very useful of makeing the compiler do work. And I agree that there are a lot of cases where it should be used.

BUT I also believe that excessive use can make the code confusing and when it removes information from the person reading the code that is not good. In this case:

auto& operator[](std::size_t mIdx) noexcept 
{ return reinterpret_cast<T&>(data[mIdx]); }

const auto& operator[](std::size_t mIdx) const noexcept 
{ return reinterpret_cast<const T&>(data[mIdx]); }

I think that auto hurts the reader of the code. This is an external interface. If I am going to use your class I don't really want to know the internals I want to know how to use it which means I need to know whats coming out of these functions. To actually I work this out I need to generate some compiler errors or look into your code when I just want to read the interface.

In this case I would expect:

T& operator[](std::size_t mIdx) noexcept 
{ return reinterpret_cast<T&>(data[mIdx]); }

T const& operator[](std::size_t mIdx) const noexcept 
{ return reinterpret_cast<const T&>(data[mIdx]); }
\$\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.