TransWikia.com

C++ Arraylist Implementation

Code Review Asked by SirTrashyton on January 2, 2022

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.

2 Answers

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)

Answered by sɪʒɪhɪŋ βɪstɦa kxɐll on January 2, 2022

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
}

Answered by Oscar on January 2, 2022

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP