std::list reimplementation

Question

I've decided to rewrite the standard library list in a smaller version. This is similar to another question of mine, where my main concern is memory management. I allocate a new array each time the user wants to modify the list. I want to know if there are any memory leaks that I need to plug. I've been liberal using delete[], but I need to know I've covered all my bases.

As always, best practices and other improvements are always welcome and appreciated.

#include <iostream>
#include <initializer_list>

template<class T>
class list {

    private:

        size_t length = 0;
        T* elements = nullptr;

        /**
         * Determines if there will be an out of bound error. If so, handles
         * it nicely and displays the range of acceptable integers allowed.
         * 
         * @param position The index passed by the user.
         * 
         * @return (void).
        **/
        void checkRangeError(const int& position) const {
            if (position < 0 || position >= this->length) {
                std::cout << "error: (position) parameter needs to be in range [0, " << this->length << ")" << std::endl;
                exit(1);
            }
        }

    public:

        list() {}
        list(std::initializer_list<T> args) {
            for (auto arg : args) {
                this->append(arg);
            }
        }
        ~list() { delete[] this->elements; }

        // Capacity Functions //

        /**
         * Determines if the current list is empty.
         * 
         * @return (bool) True if empty, False otherwise.
        **/
        bool empty(void) const { return this->length != 0; }

        /**
         * Returns the current length of the list.
         * 
         * @return (size_t) Length of list.
        **/
        size_t size(void) const { return this->length; }

        // Element Access Functions //

        /**
         * Returns the element at the front of the list. Does not pop, but
         * simply returns the value.
         * 
         * @return (T) First item in the list.
        **/
        T front(void) const { return this->elements[0]; }

        /**
         * Returns the element at the end of the list. Does not pop, but
         * simply returns the value.
         * 
         * @return (T) Last item in the list.
        **/
        T back(void) const { return this->elements[this->length - 1]; }

        // Modifier Functions //

        /**
         * Adds an element to the end of the list. Grows the list size by one.
         * 
         * @param value Element to add to the list.
         * 
         * @return (void).
        **/
        void append(const T& value) {
            if (this->length == 0) {
                this->elements = new T[1];
                this->elements[this->length++] = value;
                return;
            }
            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < this->length; i++)
                this->elements[i] = previous[i];
            this->elements[this->length - 1] = value;
            delete[] previous;
        }

        /**
         * Inserts an element at the given position. Shifts every element after down one.
         * 
         * @param position Index to place value.
         * @param value Element to add to list.
         * 
         * @return (void).
        **/
        void insert(const int& position, const T& value) {
            this->checkRangeError(position);
            T* previous = new T[this->length];
            if (position == 0) {
                for (int i = 0; i < this->length; i++)
                    previous[i] = this->elements[i];
                this->elements = new T[++this->length];
                this->elements[0] = value;
                for (int i = 1; i < this->length - 1; i++)
                    this->elements[i] = previous[i];
                delete[] previous;
                return;
            }
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < position; i++)
                this->elements[i] = previous[i];
            this->elements[position] = value;
            for (int i = position; i < this->length - 1; i++)
                this->elements[i + 1] = previous[i];
            delete[] previous;
        }

        /**
         * Replaces the value at the given position with the new value.
         * 
         * @param position Index to replace value.
         * @param value New element to place in list.
         * 
         * @return (void).
        **/
        void replace(const int& position, const T& value) {
            this->checkRangeError(position);
            this->elements[position] = value;
        }

        /**
         * Erases the value at the given position, shrinking the size of the list by one.
         * 
         * @param position Index to erase value.
         * 
         * @return (void).
        **/
        void erase(const int& position) {
            this->checkRangeError(position);
            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[--this->length];
            for (int i = 0; i < position; i++)
                this->elements[i] = previous[i];
            for (int i = position; i <= this->length - 1; i++)
                this->elements[i] = previous[i + 1];
            delete[] previous;
        }

        /**
         * Shrinks the size of the list, keeping only the elements that fit into the new size.
         * The new size must be less than the current length of the list, or the function will exit.
         * 
         * @param newSize New length of the list.
         * 
         * @return (void).
        **/
        void shrink(const int& newSize) {
            if (newSize >= this->length) {
                std::cout << "error: (newSize) must be less than the current length of the list!" << std::endl;
                exit(1);
            }
            size_t len = this->length - newSize;
            for (int i = 0; i < len; i++)
                this->erase(this->length - 1);
        }

        /**
         * Swaps two elements at their given indexes.
         * 
         * @param indexOne First index to swap.
         * @param indexTwo Second index to swap.
         * 
         * @return (void).
        **/
        void swap(const int& indexOne, const int& indexTwo) {
            T temp = this->elements[indexOne];
            this->elements[indexOne] = this->elements[indexTwo];
            this->elements[indexTwo] = temp;
        }

        /**
         * Performs an in-place bubble sort on the current list.
         * 
         * @return (void).
        **/
        void sort(void) {
            for (int i = 0; i < this->length; i++)
                for (int j = 0; j < this->length - i - 1; j++)
                    if (this->elements[j] > this->elements[j + 1])
                        this->swap(j, j + 1); // Swap using index, not value.
        }

        /**
         * Clears the list of all elements and resetting the length to zero.
         * 
         * @return (void).
        **/
        void clear(void) {
            this->elements = nullptr;
            this->length = 0;
        }

        /**
         * Prints the list to the console, all on one line.
         * 
         * @return (void).
        **/
        void print(void) const {
            for (int i = 0; i < this->length; i++)
                std::cout << this->elements[i] << " ";
            std::cout << std::endl;
        }

        /**
         * Overload operator[] for list.
        **/
        T& operator[](const int& position) const {
            this->checkRangeError(position);
            return this->elements[position];
        }   

        /**
         * Overload operator== for list.
        **/
        bool operator==(list& rhs) const {
            if (this->size() != rhs.size()) return false;
            for (int i = 0; i < this->length; i++)
                if (this->elements[i] != rhs[i]) return false;
            return true;
        }   

};

And here's how I'm compiling:

run.sh

g++ program.cpp -std=c++2a -o program
./program
rm program

Answer 1

1. As mentioned, this is a re-implementation of std::vector, not std::list.

---

2. The default constructor can be set as default.

---

3. You're not following rule of 0-3-5. Consider this snippet of code:

   int main()
   {
    list<int> l1 = {1, 2, 3};
    list<int> l2 = l1;
   }
   

   As things stand, your implementation is invoking undefined behavior because both l1 and l2 point to the same region of memory. When both are destroyed, they both try to delete the same pointer, causing a double free.

---

4. Your front and back methods should return a reference to the object. Additionally, there should be two versions, a const and a non-const version, returning a const reference and a non-const reference respectively.

---

5. You don't need to use void to signify an empty parameter list. Unlike C, an empty parameter list signifies no arguments.

---

6. You don't actually need to use this to refer to member functions and data. Unlike some other languages, this is generally used only whenever one needs to explicitly use the pointer to the current object.

---

7. If you're re-implementing a STL container/function, you should keep the interface the same. That means append becomes push_back.

---

8. The way you're growing the array is very inefficient. You're essentially allocating a new array and copying elements over every time you append. This means your append method has a time complexity of O(N), where N is the number of elements in the array.

   Typical implementations allocate more memory than needed, and keep track of how much memory is allocated and how much memory is actually used. If they are both equal, only then new memory is allocated and the elements copied over.

   How much new memory to allocate? Implementations typically allocated 2 or 1.5 times the original capacity. This gives you an amortized O(1) append.

   There's some other optimizations you can do in C++. You can allocate raw memory and create an object only when required (using placement new). This avoids the objects being default constructed whenever you allocate memory (which might be expensive). You can also check if T's move constructor is noexcept (using std::is_nothrow_move_constructible) and then moving the elements over, instead of copying them.

---

9. The way that you're moving elements is also very inefficient. This is what you're doing:

   1. Allocate temp memory (will be default constructed)
   2. Copy all elements to temp memory
   3. Allocate new list memory
   4. Copy all elements in temp memory to new list memory
   5. Delete temp memory

   whereas, a more efficient way would be

   1. Allocate temp memory (whose size is old memory * 2)
   2. Copy all elements to temp memory
   3. Swap temp memory and list memory pointers
   4. Delete temp memory

---

10. Your class is not exception safe. Any of the calls to new can return std::bad_alloc.

---

11. Instead of exiting the entire program when something goes wrong, throw an exception, or use some other kind of mechanism, to notify the caller and let the caller handle it.

---

12. Instead of providing a print function, a more idiomatic way in C++ to print an object is to overload the operator<< method.

---

13. Instead of providing a sort function, you should provide iterators (which are simply T* in this case) in the form of begin() and end() functions, so that one can use std::sort.

---

14. Use std::size_t instead of int to represent indices or size. Also, you don't need to pass trivial types such as int using const reference; pass them by value instead. They are small enough to fit in registers.

Answer 2

The front, back, and swap methods don't check for an empty list.

You leak a lot of memory. Most/all of the places where you have this->elements = new you haven't freed the previous memory stored in this->elements, resulting in a leak. clear does not free memory.

append reads one past the end of the memory block stored in previous because the loop that copies the previous elements into the new memory block uses the new size, not the old one.

insert at position 0 does not shift the existing elements. You lose the old element 0, and have a default constructed last element.

shrink can be rewritten to be faster by just allocating the new block and copying the elements that won't be lost.

operator[] should have const and non-const versions. Your current version is a const function that returns a non-const reference to your internal data.

Your list can only store default constructable objects.

Answer 3

As has already been mentioned, this is something like std::vector, but nothing like std::list.

You should at least learn what containers exist and what their characteristics are before you start reimplementing them.

my main concern is memory management

My main concern about this code is also memory management. It's not a simple topic and it requires more care than you're giving it here.

void checkRangeError(const int& position) const {

You can just pass value types by value, unless you have some persuasive reason not to. Passing an int by const reference isn't optimizing anything, it just makes the code noisier. Conversely, in

T front(void) const

you (as the library writer) don't know up-front what type T is, so you can't possibly say whether it's expensive to copy. This should return a const ref (and there should really be a non-const overloads of this & the other accessors too).

Similarly,

T& operator[](const int& position) const

should probably return a const ref (so you can't mutate the contents of a const container) and also have a non-const overload.

T* previous = new T[this->length];

why is the new array called previous? Surely this should be the next version of the array?

Note that you're going to default construct all N elements and then copy-assign all N elements again. This is wasteful (you're initializing everything twice) and places an unnecessary constraint on T (it has to be default constructible).

this->elements = new T[++this->length];

You haven't released the old copy yet, so that's a memory leak. And you've also missed one of the key things about pointer indirection: you don't need to copy everything out of the way just to copy it back later, like swapping two values.

You can just write

T* new_elements = allocate_and_move(elements, length);
delete [] elements;
elements = new_elements;

with a little effort, you can placement-move-construct the old elements into their new location instead of initializing them twice. At the very least you don't have to copy them back again, and it doesn't leak memory.

I've been liberal using delete[], but I need to know I've covered all my bases.

Don't be liberal using delete - double-freeing memory is just as bad as leaking it. Try to avoid manual memory management in the first place, especially if you're having a hard time understanding what state things are in. So we could improve the three lines above to:

std::unique_ptr<T[]> new_elements = allocate_and_move(elements, length);
elements.swap(new_elements);

(obviously you still need to write allocate_and_move, and I do encourage you to learn how to move your elements instead of copying them).

---

Finally, consider the performance of this container. It's terrible.

std::list has O(1) insert because the time to insert a single element in a linked list doesn't depend on the size of the list.

std::vector has amortized O(1) insert because although growing the array is expensive (linear although with a lower coefficient than your code), it avoids growing the array on every insert.

Your container has O(N) insert (with a really high coefficient due to default-initializing every element before copying it twice).

Answer 4

T back(void) const
Don't use (void) for empty parameter lists. Stroustrup calls this "an abomination". C needed that when (optional) signatures were added; C++ never did.

 if (this->length == 0) {
 this->elements = new T[1];
 this->elements[this->length++] = value;

Don't use this-> for every member access! Just use the member name.

length == 0 is better expressed as empty().

---

How is this an implementation similar to std::list? It looks more like vector.

---

        /**
         * Performs an in-place bubble sort on the current list.
         * 
         * @return (void).
        **/
        void sort(void) {

Why is this necessary as a bespoke member function? std::sort should work on your collection class. At the very worst, you should be able to call std::sort on the internal array as the implementation of this member.

---

       /**
         * Clears the list of all elements and resetting the length to zero.
         * 
         * @return (void).
        **/
        void clear(void) {
            this->elements = nullptr;
            this->length = 0;
        }

You seem to have forgotten to delete the memory!

---

void shrink(const int& newSize) {
Why are you passing an int by reference?

---

Your shrink function is grossly inefficient. It reallocates (copies) the entire array for each element deleted, instead of just once.
The constructor that takes an initialization_list is the same: why reallocate/copy again for each element, instead of doing it once?

---

When you reallocate and copy your array, you require that T has a default constructor, and you use assignment to set its value. The std:: collections have no such requirement. The std::vector initializes the elements directly from the item it's being set to, using the copy constructor, move constructor, or (when using emplace_back) calling some specified constructor directly in-place.

---

for (int i = 0; i < this->length; i++)
     this->elements[i] = previous[i];

Just use std::copy algorithm.
You need to be aware of what's available in the library.

---

            T* previous = new T[this->length];
            for (int i = 0; i < this->length; i++)
                previous[i] = this->elements[i];
            this->elements = new T[++this->length];
            for (int i = 0; i < this->length; i++)
                this->elements[i] = previous[i];

Holy 💩, you are copying the current array, then copying it again! And you're completely forgetting to delete elements before overwriting that pointer.

The "normal" way to do this would be to copy to a longer array, then just assign that pointer back to the elements member; you don't have to copy it again. I think you're not understanding that elements is a pointer not a built-in collection of some kind. Your like this->element= new... is not re-allocating the existing array, but allocating a different array and assigning a pointer to the first element to elements, losing the old pointer value (dropping it on the floor without deleting it).