5
\$\begingroup\$

I am a new C++ developer who, coming from Java, am having issues in understanding some of C++'s key memory management features. Below is my attempt at an ArrayList implementation and I would really love criticism and ways to improve.

Problems I noticed: Can not create an ArrayList object

Questions: In expandArray(), is delete[] required since the data is set in the next line? In my functions such as add(T &d) I figured the parameter should be a reference. Is this necessary? Would the program still work with the variable as a reference? There is no null value in C++ (besides with pointers), so in my function get(int index) I just use return; for a value it could not find.

ArrayList.h:

#pragma once
template <class T> class ArrayList {

public:
    // Constructor to initialize the list.
    ArrayList();

    // Destructor to clean up the list.
    ~ArrayList();

    // Finds a specifies element of the array list based on the index. Returns null if nothing.
    T get(int index);

    //Finds the index of the given element.
    int indexOf(T &d);

    // Inserts an element at the end of the list.
    void add(T &d);

    // Inserts an element at a specified position in the array list.
    void add(T &d, int position );

    // Deletes the element at the given index.
    //TRUE if successful
    bool remove(int index);

    //TRUE if this array contains the given data
    bool contains(T &d);

    // Empties/clears out the array list structure.
    void clear( );

    // Tests to see if the array list structure is empty.
    bool isEmpty( );

    // Returns the size of the array.
    inline int listSize() { return size; }

private:

    int arraySize;// Size of the array.
    int size; // Number of elements in the array.
    T *data = nullptr;// Pointer to the array.

    // Checks if the array is full of elements.
    bool needsExpansion();

    //makes space in the array by doubling the arraySize
    void expandArray();

    //returns TRUE if the given index is in range (0 -> size)
    bool isValidIndex(int index);
};

ArrayList.cpp:

#include "ArrayList.h"

using namespace std;

//constructor
//set array size, size and data
template<class T>
ArrayList<T>::ArrayList() {
    arraySize = 2;
    size = 0;
    data = new T[arraySize];
}

//deconstructor
//cleanup objects
template <class T> ArrayList<T> :: ~ArrayList() {
//    delete arraySize;
//    delete size;
    delete []data;
};

//takes in and index and returns the object associated with it
//return NULL or nothing if index is outta range
template <class T> T ArrayList<T> :: get(int index) {
    if (!isValidIndex(index)) return 0;
    return data[index];
}

//returns the index of the given obj
//or -1 if not found
template <class T> int ArrayList<T> :: indexOf(T &d) {
    for (int i = 0; i < size; i++) {
        if (data[i] == *d) return i;
    }
    return -1;
}

//adds the given data to the end of the list
//expands the list if neccisary
template <class T> void ArrayList<T> :: add(T &d) {
    if (needsExpansion()) expandArray();
    data[size++] = d;
}

//adds the given data to the given index
//expands the list if necessary
template <class T> void ArrayList<T> :: add(T &d, int index) {
    if (needsExpansion()) expandArray();
    //accept index at size
    if (!(index >= 0 && index <= size)) return;
    //move all obj's at >= index up 1
    for (int i = size() - 1; i >= 0; i--) {
        if (i >= index) {
            data[i + 1] = data[i];
        }
    }
    data[index] = d;
    size++;
}

//removes the element at the given index
template <class T> bool ArrayList<T> :: remove(int index) {
    if (!isValidIndex(index)) return false;
    //shift elements down
    for (int i = index + 1; i < size(); i++) {
        data[i - 1] = data[i];
    }
    //remove last element
    data[size--] = nullptr;
    return true;
}

//TRUE if the element exists in the array
//FALSE otherwise.
template <class T> bool ArrayList<T> ::contains(T &d) {
    return indexOf(d) >= 0;
}

//clears out the data that this arraylist holds
template <class T> void ArrayList<T> :: clear() {
    size = 0;
    arraySize = 2;
    delete []data;
    *data = new T[arraySize];
}

//TRUE if this array list has no elements.
template <class T> bool ArrayList<T> :: isEmpty() {
    return size == 0;
}

//TRUE if this array needs to be expanded.
//needs expansion if it is full.
template<class T> bool ArrayList<T> :: needsExpansion() {
    return size >= arraySize;
}

//expands the array by twice the given size
template<class T> void ArrayList<T> :: expandArray() {
    arraySize *= 2;
    T *newData = new T[arraySize];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    delete []data;
    data = newData;
}

//check if the index is valid
template<class T>
bool ArrayList<T>::isValidIndex(int index) {
    return index >= 0 && index < size;
}

It compiles after adding #pragma once.

\$\endgroup\$
6
  • \$\begingroup\$ How is this off topic? I am looking for best practices, potential performance issues with my memory allocation and general feedback on my code structure. Is it because it does not compile completely? \$\endgroup\$ Commented Jun 27, 2019 at 12:56
  • 4
    \$\begingroup\$ The code should work as expected to the most of your knowledge. There are more details in the page I linked. \$\endgroup\$ Commented Jun 27, 2019 at 12:57
  • 2
    \$\begingroup\$ It not only must compile, it must work as expected. Please see the help center as @Incomputable suggested. \$\endgroup\$ Commented Jun 27, 2019 at 13:29
  • \$\begingroup\$ Is there a reason you are not using vector<TYPE> or array<TYPE, SIZE>? \$\endgroup\$ Commented Jun 27, 2019 at 13:31
  • \$\begingroup\$ After adding the tag #pragma once, it compiles. And it works in storing items and retrieving items, so yes, my post applies. Thank you for helping me understand the rules. \$\endgroup\$ Commented Jun 27, 2019 at 14:11

2 Answers 2

Reset to default
3
\$\begingroup\$

Some small structure feedback:

1. The template keyword should be above the function definition

Templated functions is usually written like you have written your constructor with the template keyword ontop of the function definition. Like this:

template<class T> 
T ArrayList<T>::get(int index)
{
      //Implementation here
}

It is easier to understand at a glance this way.

2. Don't use using namespace std;

It's bad practice, and the earlier you stop using it the easier it is.

If you don't know what it does, it removes the need to write std:: before functions in the standard namespace. Example: cout << instead of std::cout <<.

It might seem handy in the beginning but it will possibly cause problems in the future so it's better to just get used to it.

3. Templated classes should be implemented in the header

.cpp files should not be used when dealing with templates. See this for more information.

If you want to separate the definition from the implementation you can use a .inl file. Like this:

ArrayList.h:

#pragma once

template <class T> 
class ArrayList 
{
public:
     ArrayList();

     // Rest of your functions here.
};

//Notice this:
#include "ArrayList.inl"

ArrayList.inl:

//Notice: No #include here

template<class T>
ArrayList<T>::ArrayList()
{
      //Implementation here
}
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the advice, I did not know that splitting my function declaration's between .cpp files would cause issues. Am I using the correct parameters and dereferencing with my get function (and other functions)? \$\endgroup\$ Commented Jun 28, 2019 at 8:32
  • \$\begingroup\$ I'd say that point 1 is really a style choice. I see you have a justification for it, but you do make it sound like an absolute rule (which it isn't). Points 2 and 3 are good observations. \$\endgroup\$ Commented Jun 28, 2019 at 9:50
  • \$\begingroup\$ @SirTrashyton You can only split the declaration and definition of a nontemplate function. You cannot do that for a template because of the way C++ templates work under the hood. \$\endgroup\$ Commented Jul 4, 2019 at 1:08
2
\$\begingroup\$

Do not use 0 or NULL to represent the null pointer

Instead use nullptr which is type safe. Why?

Well, there's quite the problem when you return the type T because objects in C++ (not confuse with pointers) have't on its range of possible values the nullptr value. It forces you to decide if there is a default value which in the case of objects is fine because you may define a non-argument constructor and say "that's my default object" but when dealing with primitive types is where the problem appears.

You may consider declaring your array as:

private:
    int arraySize;// Size of the array.
    int size; // Number of elements in the array.
    T **array;// Pointer to the array. (initialize in constructors)

but it leads to another problem, you could say why don't I return pointers but if you wrongly delete some of the pointers that have been retrieved from the ArrayList you are likely to cause a segfault or UB in the future. Why? because the address of the returned type is being shared and so when you delete but not set the pointer in the ArrayList to nullptr (which is a good practice instead of using NULL) at the moment to compare it with nullptr which is the default value it will be false and if you are trying to access said pointer then segfault.

How could I solve such trouble? You may create a new pointer passing the data of the accessed type and that would unlink the pointer in ArrayList from the pointer you are receiving when calling operator[] in example.

//takes in and index and returns the object associated with it
//return NULL or nothing if index is outta range
template <class T>
T *ArrayList<T>::get(int index) {
    if (!isValidIndex(index)) return nullptr;
    T *with_new_address = new T; // if T is an object must have a default constructor
    *with_new_address = *(data[index]); // data[index] now returns a *T type
    return with_new_address;
}

I hope it helped you. Even at this time (1 year latter)

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.