Dynamic array resize function problems

Question

NOTE: I am aware that it would be easier to just use the STL Vector, however, for a programming class that I'm in, we are required to write our own dynamic array template class because our professor apparently enjoys making us reinvent the wheel.

Anyway, I made a resize function for my dynamic array template class that goes as follows. Note that the private member variables are T* arr, unsigned used, and unsigned cap.

template <class T>
void darray<T>::resize(unsigned size)
{
    if (size > cap)
    {
        T* temp_arr = new T[size];

        for (int count = 0; count < used; ++count)
            temp_arr[count] = arr[count];

        for (int count = used; count < size; ++count)
            temp_arr[count] = T();

        delete []arr;
        arr = temp_arr;
        cap = size;
        used = size;
    }

    if (size < cap)
    {
        used = size;
    }
}

Whenever I use this function to increase the size of the array, it will work the first time I need to use it, but after that, Visual Studios will trigger a breakpoint at line 14 (delete[] arr), and if I continue past the breaks, I eventually get _CrtIsValidHeapPointer(pUserData) assertion failure. What is causing this, and how can I fix it?

constructor:

template <class T>
darray<T>::darray()
{
used = 0;
cap = 64;

arr = new T[cap];

for (int count = 0; count < cap; ++count)
    arr[count] = T();

}

assignment operator:

template <class T>
darray<T>& darray<T>::operator= (const darray& right_operand)
{
    delete[] arr;
    arr = new T[right_operand.capacity()];
    used = right_operand.size();
    cap = right_operand.capacity();

    for (int count = 0; count < used; ++count)
        arr[count] = right_operand[count];
    return *this;
}

destructor:

template <class T>
darray<T>::~darray()
{
    delete[] arr;
}

There's been some requests for the push_back function, so here's that as well:

template <class T>
void darray<T>::push_back(const T& input)
{
    if ((used + 1) > cap)
    {
    resize(cap * 2);
    arr[used + 1] = input;
    ++used;
    }

    else
    {
        arr[used] = input;
        ++used;
    }
}

You have a memory leak if you expand -> contract -> expand again due to unreleased memory of the objects themselves — Karthik T, Apr 22 '14 at 08:18
Seems the professor made a good choice, as it's apparently not trivial to create a working implementation ;) — Willem van Rumpt, Apr 22 '14 at 08:19
If you know vector already, why don't you have a look at it's source code to see how it's done? It's going to be hard to come up with a better implementation.. A+++ all the way :P — stijn, Apr 22 '14 at 08:20
I see nothing wrong with this piece of code. Did you initialize arr to be nullptr in the constructor? — Ophir Gvirtzer, Apr 22 '14 at 08:25
Does your class follow the [Rule of Three](http://stackoverflow.com/questions/4172722) properly? (One good reason for reinventing this particular wheel is to learn the complications of resource management and copy/move semantics. You can usually use library classes to take care of these details for you, but it's important to understand how they work.) — Mike Seymour, Apr 22 '14 at 08:29
I didn't initialize it to be nullptr, but I did initialize it to be an array of 64 empty values and set cap to 64 — Matthias, Apr 22 '14 at 08:29
@user3559437 Can we see the constructor that was used for the object in question? — Potatoswatter, Apr 22 '14 at 08:30
Yes, I followed the Rule of Three, I could post the implementations of those as well if it would help — Matthias, Apr 22 '14 at 08:33
Does it crash for trivial instantiations, such as `int`? Also, do you do anything inbetween the resizings? — molbdnilo, Apr 22 '14 at 08:42
It does crash for int, that's what I'm currently using it for. The only thing that I'm doing in between the resizeings is using a simple push_back, which just gives a value to the appropriate location, increments used, and calls resize if used is > cap — Matthias, Apr 22 '14 at 08:46
You should post your `push_back` code as well. The error might be there although it it is reported on deletion. — Stephan, Apr 22 '14 at 08:54
Could you post the full code? Also why do you set used to equal size after a resize? — Veritas, Apr 22 '14 at 08:59
You're right about the used being set to size, I changed that in my actual code. I don't think I can post my entire code here, but I did include puch_back — Matthias, Apr 22 '14 at 09:08
Actually, not setting used = size fixed the problem. Thank you, Veritas! — Matthias, Apr 22 '14 at 09:18

Stephan · Accepted Answer · 2014-04-22T09:37:17.673

Your resize function increases used. When you access arr[used+1] in push_back, than you access an invalid array location.

You should add another function, which is similar to resize, but changes only the capacity of your array and not the stored object count. (i.e. it does not increment used). This function should be called by push_back. (As you mentioned std::vector in your question, see the difference between vector::resize and vector::reserve.)

Also: array indexes are zero-based. Do not insert at position used + 1 but on position used.

score 0 · Answer 2 · answered Apr 22 '14 at 08:52

I would use next implementation. I assume that "cap" member is for capacity of vector and "used" is for amount of elements in array.

template <class T>
void darray<T>::resize(unsigned size)
{
  if (size > cap)
  {
    cap = size * 2;
    T* temp_arr = new T[cap];

    for (int count = 0; count < used; ++count)
        temp_arr[count] = arr[count];

    delete [] arr;
    arr = temp_arr;
  }   

  // zero members if size was decreased
  if (size < used)
  {  
     for (int count = size; count < used; ++count)
          arr[count] = T();
  }

  used = size;
}

Pros: You don't need to reallocate the whole array each time you do a resize with larger number of elements.

Cons: You spend an extra space when you don't need to.

Dynamic array resize function problems

2 Answers2