0
\$\begingroup\$

This question is a follow-up to the my earlier code posted here. In the original question, I created a simplified version of C++ std::vector/ArrayList. I got many good answers and I thought I would like another code review of my improvements to my original code.

What I changed

I Incorporated the reviews from @Loki, @Sean, and @Matthieu. I used some of the code from each of them. More specifically, I heavily used initializer lists now, and I changed the constructor, removed wrongly implemented remove functions, added a swap function, added noexcepts, removed duplicated/reused code where possible, and a bunch of other changes.

Goal

I still have the same goals as the last review

  1. My ArrayList class guarantees Strong Exception Safety, using the copy and swap idiom
  2. The container still works if T passed in is not default constructible
  3. Correctness of the implementation of the Rule of Five
  4. General correctness and efficiency (i.e: No memory leaks, dangling pointers ... ...)

Hopefully my new and improved code implements the above 4 points better this time around. I would still like to ask that code reviews focus on those 4 aspects, in addition to any other important style choice errors or any other problems that I missed.

#pragma once

template <typename T>
class ArrayList
{
    public:
        ArrayList(int size = 100);
        ArrayList(const ArrayList<T>& other);
        ArrayList(ArrayList&& other)                                noexcept;
        ~ArrayList();

        ArrayList<T>& operator= (const ArrayList<T>& other);
        ArrayList<T>& operator= (ArrayList&& other)                 noexcept;

        void add(T item);
        void remove(int index);
        void swap(ArrayList& other)                                 noexcept;

        friend void swap(ArrayList& A, ArrayList& B)
        {
            A.swap(B);
        }

    private:
        T* arr;
        size_t allocatedSize;
        size_t actualSize;

        void resize();
        ArrayList(const ArrayList& other, int size);
};

template <typename T>
ArrayList<T>::ArrayList(int size = 100)
    :arr(static_cast<T*>(::operator new(sizeof(T)*size)))
    ,actualSize(0)
    ,allocatedSize(size)
{

}


template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other, int size)
    :ArrayList(size)
{
    try
    {
        for(std::size_t i = 0; i<other.actualSize; i++)
            add(other.arr[i]);
    }
    catch (...)
    {
        for(std::size_t i = 0; i<other.actualSize; i++)
            other.arr[i].~T();

        ::operator delete;
        throw;
    }
}

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
    :arr(nullptr)
    ,actualSize(0)
    ,allocatedSize(0)
{
    swap(*this, other);
}

template <typename T>
ArrayList<T>::~ArrayList()
{
    for(std::size_t i = actualSize - 1; i>=0; i--)
        arr[i].~T();

    ::operator delete(arr);
}

template <typename T>
ArrayList<T>& ArrayList<T>::operator =(const ArrayList<T>& other)
{
    ArrayList tmp(other);
    swap(*this, tmp);
    return *this;
}

template <typename T>
ArrayList<T>& ArrayList<T>::operator =(ArrayList<T>&& other)
{
    swap(*this, other);
    return *this;
}

template <typename T>
void ArrayList<T>::add(T item)
{
    if(actualSize >= allocatedSize)
        resize();

    new(arr+actualSize) T(std::move(item));
    actualSize++;
}

template <typename T>
void ArrayList<T>::remove(int index)
{
    if(index<0 || index>actualSize - 1)
        throw std::runtime_error("wrong index");

    for(std::size_t i=index; i<actualSize-1; i++)
    {
        arr[i] = std::move(arr[i+1]);
    }

    actualSize--;
    arr[actualSize].~T();
}

template <typename T>
void ArrayList<T>::swap(ArrayList& other)
{
    using std::swap
        swap(allocatedSize, other.allocatedSize);
    swap(actualSize, other.actualSize);
    swap(arr, other.arr);
}

template <typename T>
void ArrayList<T>::resize()
{
    ArrayList tmp(this, allocatedSize*1.5);
    allocatedSize *= 1.5;
    swap(*this, tmp);
}

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
    :ArrayList(other, other.allocatedSize)
{
}
\$\endgroup\$
3
\$\begingroup\$

My ArrayList class guarantees Strong Exception Safety, using the copy and swap idiom

Yes.

The container still works if T passed in is not default constructible

Yes

Correctness of the implementation of the Rule of Five

Yes

General correctness and efficiency (i.e: No memory leaks, dangling pointers ... ...)

Couple of minor bugs (see below) but nothing outrages. No leaks or dangling pointers.

Fails to compile:

template <typename T>
ArrayList<T>::ArrayList(int size = 100)
                                 ^^^^^ not need in definition

        ::operator delete     ;
        throw;           ^^^^^   need to delete something


template <typename T>
ArrayList<T>& ArrayList<T>::operator =(ArrayList<T>&& other)  
                                                             ^^^^^^ missing noexcept

template <typename T>
ArrayList<T>& ArrayList<T>::operator =(const ArrayList<T>&& other)
                                                                   ^^^^^^ missing noexcept


template <typename T>
void ArrayList<T>::swap(ArrayList& other) 
                                           ^^^^^^ missing noexcept

    using std::swap
                   ^^^^ missing ;

Destruction order

catch (...)
{
    for(std::size_t i = 0; i<other.actualSize; i++)
        other.arr[i].~T();

    ::operator delete;
    throw;
}

Like the destructor. I would destroy the members in reverse order (so it behaves like the built in array).

Bug 1: Does this loop terminate

for(std::size_t i = actualSize - 1; i>=0; i--)
    arr[i].~T();

Is i ever smaller than zero? Since this is a std::size_t I expect it to be an unsigned integer that rolls around to a very large value.

There are two techniques I have seed used.

for(std::size_t i = actualSize; i > 0; i--)
    arr[i-1].~T();

Or

for(std::size_t i = 0; i < actualSize; i++)
    arr[actualSize - 1 - i].~T();

Bug 2: Failure to increase allocated size

ArrayList tmp(this, allocatedSize*1.5);

 // This is subtle.
 // But if the current allocatedSize is 0 or 1
 // then the above will not increase the allocated size.
 // So you need a minimum of 2

     ArrayList tmp(this, std::max(2, allocatedSize * 1.5));

Flaw 1: Invalid value of allocatedSize

ArrayList tmp(this, allocatedSize*1.5);
allocatedSize *= 1.5;   // This is a mistake.
                        // You have not increased the allocated size
                        // of the current object (so this could cause issues)

                        // Luckily you swap it to tmp below which goes
                        // out of scope and is thus destroyed so it is
                        // benign in this context.

                        // The current objects size and allocatedSize
                        // will change with the swap() operation below.
swap(*this, tmp);

Tidyup

I would move the copy constructor from the bottom upto where the other constructors are.

\$\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.