7
\$\begingroup\$

As part of my learning C++, I have created an ArrayList class. It shares some of its interface with the Java ArrayList, but it by no means implements anywhere close to the full set of functions an ArrayList or vector supports.

Here is my ArrayList.h:

#ifndef ARRAYLIST_ARRAYLIST_H
#define ARRAYLIST_ARRAYLIST_H

#include <initializer_list>

template<typename T>
class ArrayList{
public:
    //lifecycle
    ArrayList() : m_array(new T[0]) {}
    ArrayList(std::initializer_list<T> it);
    ~ArrayList() { delete [] m_array; }

    //copy control
    ArrayList(const ArrayList<T> &arraylist) { *this = arraylist; }
    ArrayList(const ArrayList<T> &&arraylist) { *this = arraylist; }
    ArrayList& operator=(const ArrayList<T> &arrayList);
    ArrayList& operator=(ArrayList<T> &&arrayList);

    //element access
    T& operator[](unsigned i) { return m_array[i]; }
    void add(const T &t) { resizeIfFull(); m_array[m_frontendLength++] = t; }
    void add(const T &&t) { resizeIfFull(); m_array[m_frontendLength++] = std::move(t); }

    //utilities
    unsigned length() { return m_frontendLength; }

private:
    T *m_array = nullptr;
    unsigned m_backendLength, m_frontendLength;

    void resizeIfFull();
};

#include "ArrayList.tpp"

#endif //ARRAYLIST_ARRAYLIST_H

Here is my ArrayList.tpp:

#ifndef ARRAYLIST_TPP
#define ARRAYLIST_TPP

#include "ArrayList.h"

#include <utility>

template<typename T>
ArrayList<T>::ArrayList(std::initializer_list<T> ls){
    m_array = new T[ls.size()];

    m_backendLength = ls.size();
    m_frontendLength = ls.size();

    unsigned i = 0;
    for(auto it=ls.begin();it!=ls.end();++it){
        m_array[i++] = *it;
    }
}

template<typename T>
ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T> &arrayList){
  m_backendLength = arrayList.m_backendLength;
  m_frontendLength = arrayList.m_frontendLength;

  delete [] m_array;

  m_array = new T[m_backendLength];

  for(unsigned i=0;i<m_frontendLength;++i){
    m_array[i] = arrayList.m_array[i];
  }

  return *this;
}

template<typename T>
ArrayList<T>& ArrayList<T>::operator=(ArrayList<T> &&arrayList){
    m_backendLength = arrayList.m_backendLength;
    m_frontendLength = arrayList.m_frontendLength;  
    m_array = arrayList.m_array;
    arrayList.m_array = nullptr;
}

template<typename T>
void ArrayList<T>::resizeIfFull(){
  if(m_backendLength == m_frontendLength){
    m_backendLength *= 2;
    T *newArray = new T[m_backendLength];

    for(unsigned i=0;i<m_frontendLength;++i){
      newArray[i] = std::move(m_array[i]);
    }

    delete [] m_array;
    m_array = newArray;
  }
}

#endif

I am hoping to get some information on things I did badly, and things I did well. I am particularly interested in: compliance with C++ convention, writing good code with regard to organization (ie. OOP, SOLID, etc.), and efficiency. I know Java much better, and I would like to know if I am bringing Java stuff in here that doesn't belong in C++.

\$\endgroup\$
10
\$\begingroup\$

Memory Allocation

This is a house built on sand, so to speak. Quite a bit of the house itself looks perfectly fine, but the foundation is completely rotten, so everything else is liable to fall over without notice.

The specific problem is using new [] to allocate storage. The problem with this is that it actually creates objects in the memory you allocate. If you're storing objects that are expensive to construct, this can impose unnecessary overhead. If you're storing objects that can't be default constructed...well, you're not storing those, because it just won't work.

The right (at least IMO) way to do this is to use the same strategy as vector does (at least by default). You allocate raw memory using operator new, and then construct objects in that raw memory using placement new. This means the unused part of the memory really is unused--i.e., it's just raw memory that doesn't contain any actual objects.

Naming

frontEndLength and backEndLength don't seem particularly descriptive, at least to me. Apparently they really mean something like "amount allocated" and "amount in use". If so, I'd change the names to reflect that more directly.

Exception Safety

Your assignment operator is written a lot like most of us typically wrote them in the '90s or so, before (for one example) Exceptional C++ was published. It has a number of problems. For example, if it ends up doing a self assignment:

ArrayList a;

// code that puts something into `a` goes here

a = a;

The self-assignment will often be somewhat indirect, such as passing the same collection as both the source and the destination of some function. Regardless of how it happens, it leads to a serious problem. It obviously shouldn't really do anything--but with your code, it destroys a. Nearly the first thing your operator= does is delete [] m_array;, so if the source and the destination are the same, you've just destroyed your source, and after that, everything breaks badly.

Quite a few people noticed this problem, so at one time it was pretty typical to see code that did something like this:

T &operator=(T const &r) { 
    if (this == &r) // if source and dest are the same, do nothing
        return;
    // rest of the assignment goes here.
}

This fixes that particular problem, but leaves a more pernicious one. You'd typically like your assignment to either succeed entirely or fail entirely--but as it stands now, it might half-succeed, so you've lost the old contents, but gotten only part of the new contents. Worse, you aren't sure where in the copying process it was when the exception was thrown, so you don't have any way of knowing how much of the content is really valid.

One simple way of dealing with all of these is called the copy and swap idiom. It consists of creating a temporary copy of the source. Then when that's completed, you swap the destination with the temporary.

template<typename T>
ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T> &arrayList){

    ArrayList<T> temp(arrayList);
    std::swap(*this, temp);
    return *this;    
}

You can also shorten this a tiny bit by using the parameter as the temporary object:

template<typename T>
ArrayList<T>& ArrayList<T>::operator=(ArrayList<T> arrayList){

    std::swap(*this, arrayList);
    return *this;    
}

Either way, if an exception is thrown during the copying process, the temporary is never created, and the swap never happens. The original stays exactly as it was. We normally expect (and typically enforce) that the swap can't throw any exceptions (pretty trivial in this case, because all it's doing is copying pointers and ints around).

Once that's done, the temporary gets destroyed, releasing the memory that was previously used by the destination object.

Of course, there are other ways to write an exception-safe assignment operator--this is just one that's simple, well-known and idiomatic.

Expansion factor

Right now, when you run out of space, you multiply the size by two. That's a fairly reasonable approach, but there's a theoretical argument to be made in favor of making the expansion factor less than or equal to the golden mean. I wrote a little more about it in an earlier reply.

\$\endgroup\$
10
\$\begingroup\$

Important stuff:

  • compiler error

    add() uses std::move() which is not defined yet. std::move() is in a header <utility>, which is not included yet. So, it is not good idea to write some of the implementation in the header and some of it in separate implementation file.

  • const rvalue reference (type of form const T&&).

    Moving from an object essentially means moving modifies it. So making it const will disable it.

  • Exception safety guarantee

    There are three exception safety guarantees. I won't go into much detail, but people expect strong exception guarantee in copy constructors (e.g. if function throws, the program gets to the state before the function fall. Exception still has to be caught). It is possible to do so using copy and swap idiom.

  • Unexpected behavior:

    Copy and move constructors will copy/move assign elements instead of constructing them. It is an outcome of using new.

    Also, move constructors and move operator= are expected to be noexcept.

Improvements:

  • Not for all T:

    new T[size]; allocates memory and default constructs size count of objects. By far not every object is default constructible. Uninitialized storage should be used paired with "placement new".

  • small usage of standard library:

    std::copy() could be used to copy one range into another. There is also std::move() version of it. It can still be used without implementing iterators, since pointers to contiguously allocated elements are "RandomAccessIterator"s, and "ContiguousIterator" in C++17.

    std::size type is usually used as size type in containers.

    length() disables std::size() function, which can be uniformly used on standard containers. size() function should be provided instead.

Stylistical improvements:

  • Inconsistency in reference/pointer placing:

    ArrayList& operator=(const ArrayList<T> &arrayList);
    ArrayList& operator=(ArrayList<T> &&arrayList);
    
    //element access
    
    T& operator[](unsigned i) { return m_array[i]; }
    

    These lines put & close to the type. Others don't. It might be an IDE doing that; it is possible to configure it.

\$\endgroup\$
3
\$\begingroup\$

One thing other reviewers haven't mentioned:

T& operator[](unsigned i) { return m_array[i]; }

This is potentially dangerous. There is no bounds checking in place, so if you have ArrayList<int> a; whose size is 3 and a[5] gets called, you get out of bounds problems (and thus undefined behavior). You should include an alternative way to do element access with bounds checking that throws a std::out_of_range exception if the index is out of range (calling it at would be good, because it mirrors std::vector::at).

\$\endgroup\$
  • 9
    \$\begingroup\$ disagree: No bounds checking in this case is a very good thing, as it follows the idiom established by the stdlib, therefore not surprising callers by making them pay for what they didn't want to use in the first place. It doesn't matter whether they think they "really really really need" it. It's just good, non-surprising design not to do bounds-checking in operator[]. That's what .at() is for. If operator[] is to check bounds, it should only do so in debug mode if given a specific flag at compile-time, as some stdlibs offer. \$\endgroup\$ – underscore_d Jun 7 '17 at 23:04
  • 1
    \$\begingroup\$ @underscore_d Following the idiom established in the standard library is not preferable to having safe code that doesn't cause undefined behavior. As I noted, it's possible to have both with an implementation of at, but without that, no UB is better than possible UB. \$\endgroup\$ – Mego Jun 8 '17 at 2:13
  • 1
    \$\begingroup\$ My point is: Mentioning the danger and suggesting providing .at() to do bounds-checked indexing are great suggestions! But what is not great is how you bring up .at() as an afterthought, after leading with the bad suggestion of having operator[] do the check. If you had instead said 'note this can explode if given unsafe input, so use .at() if that is a risk', or 'you probably want to assert() on the index in debug mode', then I would totally agree. But as written, I just don't think this has the right order of, or emphasis on, points. \$\endgroup\$ – underscore_d Jun 8 '17 at 7:15
  • \$\begingroup\$ @underscore_d I'll rewrite my answer to improve the explanation. \$\endgroup\$ – Mego Jun 8 '17 at 8:06
2
\$\begingroup\$
  1. The move constructor should be:

    *this = std::move(arrayList);
    
  2. You need to free the array in the move assignment operator:

    delete [] m_array;
    

(here's an example on MSDN that details how to make your class moveable)

  1. You should initialize the member variables:

    unsigned m_backendLength = 0;
    

    Otherwise they may be set to something funky when you call your default constructor.

  2. Personal preference - I would change your length variable names to m_size and m_capacity.

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