Basic ArrayList

Section 23.9 Basic ArrayList

At its core, an array list needs to manage an array of elements, like the container classes we previously studied in Section 22.10. This involves keeping track of a dynamic array, its size, and its capacity. We want our ArrayList class to be able to store any type of element, so we will make it a templated class. The basic interface and member variables will look like this:

🔗

Listing 23.9.1.

🔗

template <typename T>
class ArrayList {
private:
    T* m_arr;            // pointer to the array of type T
    int m_capacity;      // maximum number of elements
    int m_size;          // current number of elements

public:
    // Construct an empty ArrayList
    ArrayList();

    // Rule of Three
    // Copy another ArrayList of type T
    ArrayList(const ArrayList<T>& otherList);
    // Assign from another ArrayList of type T
    ArrayList<T>& operator=(const ArrayList<T>& other);
    // Destructor to free memory
    ~ArrayList();

    // Insert/remove item at end of list
    void insertEnd(const T& newItem);
    void removeEnd();

    // Access item at given location
    T get(int location) const;
    // Modify item at given location
    void set(int location, const T& newValue);

    // Ask how many items are in the list
    int size() const;

    // more to come...
};

We will examine definitions for those functions soon. But given that interface, we might use the ArrayList with this code:

🔗

Listing 23.9.2.

🔗

A memory diagram of main might looks like this:

🔗

The intList object contains a pointer to an array. That array contains [10, 20, 30, ???, ???] — Figure 23.9.3. `intList` has a pointer to an array with space for 5 integers. Currently only 3 are used. ??? indicates uninitialized/unused space.
🔗

Notice that we have two variables related to the size of the ArrayList. m_capacity keeps track of how much space is allocated for the array (the physical capacity). It is the maximum number of items we currently can store. m_size keeps track of how many elements of that array are in use (the logical size). In this case, only 3 of the 5 elements in


    m_arr

are being used.

🔗

Insight 23.9.1.

The ArrayList will usually not be using all of the memory it has allocated. Anytime we want to know how many elements are in the ArrayList (how many values in the array we consider to be important) we should check the m_size variable.

🔗

Recall that when we dynamically allocate an array, we have to specify how many elements we want to allocate. So the constructor needs to pick some initial capacity for the array and allocate that much storage on the heap:

🔗

template<typename T>
ArrayList<T>::ArrayList() {
    m_size = 0;
    m_capacity = 5;  //default to space for 5 items
    m_arr = new T[m_capacity]; // Allocate storage on heap
}

Note 23.9.2.

Syntax tip: ArrayList<T>::ArrayList() is the constructor for an ArrayList of type T. The ArrayList class is templated (ArrayList<T>::), but the function name (ArrayList()) is not.

🔗

That constructor allocates an array big enough to hold 5 values. We do nothing to initialize the memory, so the contents are indeterminate (i.e., they could be anything). But we do not consider those unused locations to be part of the ArrayList. Since the m_size is 0, we think of the ArrayList as being empty.

🔗

The intList variable contains an m_size of 0 and m_capacity of 5. It also has a pointer to an array named m_arr. That array contains [???, ???, ??? ???, ???]. — Figure 23.9.4. `intList` after being constructed, before anything is added to it.
🔗

Because the class manages dynamic memory, it needs the rule of three functions: a copy constructor, copy assignment operator, and destructor. Other than being templated, they all follow the same pattern we saw in Section 22.14. Their implementations are shown in the final version of the ArrayList code. If you want to examine them, see Listing 23.16.1.

🔗

Note 23.9.3.

We are intentionally making something simpler than the std::vector. To make our ArrayList more like vector, we might:

Add a constructor that takes an initial capacity as a parameter so users can create an ArrayList with a specific size from the beginning.

🔗
Use size_t instead of int for size and index variables to better represent their non-negative nature.

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next