3
\$\begingroup\$

Please review my custom ArrayList class I constructed from scratch and add any suggestions or constructive criticisms. The point of this template class is give the user a lightweight ArrayList with optimal control over how it operates.

It is automatically created on the heap with an optional seed value which determines how much space to give it upon being recreated after filling up. It comes with a refine function which cuts off the garbage values at any time and it can also be reseeded. Seed default is 10 new array spots for each recreation.

#ifndef MEMORYLIST_H
#define MEMORYLIST_H

//Class is designed to be a basic array list off the stack
template <class Heap> class MemoryList {
private:
    Heap *array;    //ArrayList on Heap
    int length;     //Max Length of ArrayList
    int counter;    //Current Position on ArrayList
    int seed;       //amount to add by when limit is breached

    //Increase list if needed
    inline void spaceCheck() {
        if (counter == length) {
            int i;

            Heap *temp = new Heap[length];

            for (i = 0; i < length; ++i) {
                temp[i] = array[i];
            }

            delete [] array;

            length += seed;
            array = new Heap[length];

            for (i = 0; i < length - 10; ++i) {
                array[i] = temp[i];
            }

            delete[] temp;
        }
    }

    inline void shiftRight(int place) {
        for (int i = length - 1; i >= place + 1; --i) {
            array[i] = array[i - 1];
        }
    }

public:
    MemoryList(int seed = 10) {
        this->seed = seed;
        length = seed;
        counter = 0;
        array = new Heap[length];
    }

    //just shows what value is stored in what position
    Heap showValue(int position) {
        return array[position];
    }

    //tack a value to the end
    void newValue(Heap variable){
        spaceCheck();

        array[counter] = variable;
        ++counter;
    }

    //tack a value anywhere you want and array will self adjust
    void insertValue(int position, Heap variable) {
        spaceCheck();
        shiftRight(position);

        array[position] = variable;
        ++counter;
    }

    //delete any value you'd like and array will self adjust
    void deleteValue(int position) {
        for (int i = position; i < length - 1; ++i) {
            array[i] = array[i + 1];
        }

        --counter;
    }

    //Overwrite any value you'd like, no need to adjust anything
    void overWrite(int position, Heap variable) {
        array[position] = variable;
    }

    //swap any two array points
    void swap (int position1, int position2) {
        Heap temp;
        temp = array[position1];
        array[position1] = array[position2];
        array[position2] = temp;
    }

    //reseed amount of space you'd like to allocate when you're running out
    //of room
    void reSeed(int seed) {
        this->seed = seed;
    }

    //is item in array?
    bool search(Heap item) {
        //this might make it faster ::shrug::
        for (int i = 0, j = counter; i < counter; ++i, --j) {
            if (array[i] == item || array[j] == item) return true;
        }
        return false;
    }

    //Creates perfect ArrayList stored on heap without garbage
    void refine() {
        int i;

        length = counter;     
        Heap *temp = new Heap[length];

        for (i = 0; i < length; ++i) {
            temp[i] = array[i];
        }

        delete [] array;
        array = new Heap[length];

        for (i = 0; i < length; ++i) {
            array[i] = temp[i];
        }

        delete[] temp;
    }

    void finished(){
        delete[] array;
    }
};

#endif // MEMORYLIST_H
\$\endgroup\$
  • \$\begingroup\$ Unfortunately this question appears to be off topic because it is about understanding code. The point of a code review is to identify things about the code that can be improved and discuss possible improvements. \$\endgroup\$ – Malachi Jul 7 '15 at 13:12
  • \$\begingroup\$ Sorry, completely new user. Won't happen again, although could you possibly point me toward a more proper forum or subforum? \$\endgroup\$ – Jonathan Hernandez Jul 7 '15 at 13:23
  • \$\begingroup\$ Stack Overflow would be a good place. Possibly also [programmers.stackexchange.com](programmers.stackexchange.com). (Though I'm unclear on whether this question would be on topic there, since it sounds like an implementation issue.) \$\endgroup\$ – user1118321 Jul 7 '15 at 13:39
  • 1
    \$\begingroup\$ I edited your question to make it, in my opinion, on-topic for Code Review. For the part that I edited out, I suggest you post on Stack Overflow \$\endgroup\$ – Simon Forsberg Jul 7 '15 at 13:47
  • \$\begingroup\$ @user1118321 This does not belong on Programmers. \$\endgroup\$ – Simon Forsberg Jul 7 '15 at 13:47
6
\$\begingroup\$

A couple of things jump out:

Use size_t for the all allocation sizes/indices. I have had real-world bugs because of this in third-party libraries.

Use exponential, not linear, reallocations. Doubling each time is the best way. This allows .newValue to append in \$O(1)\$ amortized time, as opposed to the current \$O(n)\$.

\$\endgroup\$
  • \$\begingroup\$ Apparently, doubling each time is not the best way, it may even be the worst growth factor :) \$\endgroup\$ – Morwenn Jul 8 '15 at 15:34
  • \$\begingroup\$ @Morwenn I'm not aware of a single real-world memory allocator that would even try to coalesce. They use separate bins for each size, though once it gets past the mmap threshold the kernel can give new virtual address space from anywhere. \$\endgroup\$ – o11c Jul 8 '15 at 17:40
3
\$\begingroup\$

This is an excellent exercise! I wish I'd tried something like this when I first learned C++. Overall, this code is very straightforward and easy to understand. I was easily able to figure out what everything does. Nice work!

I have a few suggestions on how you could improve it in addition to what @o11c suggests.

Naming

The use of the name Heap is a bit strange. The word "heap" describes a few important things in computer science, and this doesn't seem like either of them. The heap is the area of memory where things that need to outlive the scope of where they're declared are allocated, and there's also an organizational structure called a heap (i.e.the heap used in heapsort). Traditionally, the type used in a template definition is T. I'd stick with that.

Likewise, the name MemoryList makes me think that its implementation is a linked list. A linked list has certain properties that make it inappropriate for some uses, so it might affect when I would use it. Also, all your data for a class like this is in memory, so the word "Memory" in the name seems redundant. A better name might be something like ResizableArray or AutosizingArray or something like that.

Your showValue() method doesn't show anything. It just returns the value at the index. I'd rename it valueAtIndex(). Or better yet, maybe implement the operator[]() so a user of this class can use it like a normal array:

MemoryList<some type> foo(100);
...
for (int i = 0; i < 100; i++)
{
    std::cout << "Item " << i << " = " << foo [ i ] << "\n";
}

The name newValue() makes it sound like it returns a new value. I'd rename it append(). The standard template library uses push_back(), which I find cumbersome, but users of STL would know what it means.

The name refine() doesn't tell me much about what it does. Maybe compact() or removeUnusedSpace() or something like that would be more telling?

Also, why is there a finished() method? Why not just implement a destructor which deletes the array?

Error Handling

What happens when a caller calls insertValue(), deleteValue(), overWrite(), or swap() with indices that are not valid? They could be negative or past the end of the array (either in the allocated-but-unused area, or past the end of the allocated area altogether). You need to either return a value that indicates whether the operation succeeded, or you need to throw an exception when something goes wrong. An exception is probably a better choice here, but there are trade-offs. You should read up on them to see which is best for your use-case.

Iterators

I've mentioned a few features of C++ you could use to improve this, but there are more. Most container classes implement iterators. An iterator can be used for a variety of tasks, but is most often used to iterate though all members in a container in a loop like this:

MemoryList<someType> foo(100);
... insert various things into foo ...
MemoryList::iterator iter = foo.begin();
while (iter != foo.end())
{
    someType nextItem = *iter;
    ... do something with next Item ...
    iter++;
}

It is also used to return the element found in a search() or find() method.

Do Something Useful

The search() method returns a bool that simply tells whether the array contains the item or not. If that's really your intent, I'd rename it contains(). But it would probably be more useful to return either the index of the item in the array (or at least of the first occurrence in the array), or return an iterator that points to that instance.

\$\endgroup\$
1
\$\begingroup\$

In addition to the two reviews above, I do not see a destructor here freeing the memory held in array pointer. You should use RAII as the main purpose of it is to allow implementers to control class resources. You should use something like:

MemoryList(std::size_t seed = 10)
{
    //...
    array = new Heap[length];
}

~MemoryList()
{
    delete[] array;
}

This of course will make your finished function obsolete since the user should never be allowed to make handle resources explicitly (that's the point of RAII).

You use a signed value to represent a value that should always be positive (seed and length). As someone from above recommended, use std::size_t for all your values. This also allows you to have a MemoryList that can grow to be much bigger than 2^31 - 1 elements since std::size_t is either an unsigned long or unsigned long long type.

An algorithm like "search" is already available in the STL (std::find). Your class should provide an iterator interface that allows the users to be able to "plug-in" your data structure to the available STL algorithms. Your shiftRight function can be replaced by a call to std::copy() in <algorithm> and your swap function can be replaced by a call to std::swap() in <algorithm> as well.

Your insertValue and newValue functions take a Heap argument by value - which means it's passed by copy. What if the Heap type is expensive to construct/copy? Use a constant reference to a Heap type instead:

void insertValue(std::size_t position, const Heap& value);
void newValue(const Heap& value);

Your showValue function should really be transformed into a operator[] member overload and return a reference to the object it's showing. You'll have to provide a const and non-const version of these:

Heap& operator[](std::size_t i);
const Heap& operator[](std::size_t i) const;

In your refine function, you're using the i variable twice inside for loops yet you've declared it non-local to those loops. Declare the i variable to be local to the loop:

for (std::size_t i = 0; /*...*/){ /*...*/ }

You also might want to implement some convenience functions for the user of your data structure like returning the size or returning whether or not your structure is empty:

bool isEmpty() const;
std::size_t size() const;

Finally, the inline specifier is unnecessary if you're implementing the function in the header definition file (as you are in this case).

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