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
- My ArrayList class guarantees Strong Exception Safety, using the copy and swap idiom
- The container still works if T passed in is not default constructible
- Correctness of the implementation of the Rule of Five
- 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)
{
}
1 Answer 1
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.