Thread: Dynamic array, InsertRange implementation

That sounds like it will work.

Incidentally, you might want to typedef size_t to size_type for your array class, and then write:

Code:

void InsertRange(size_type index, const T* data, size_type count)

Besides the fact that size_t is unsigned and logically the index and count are unsigned, it follows a little more closely what the standard containers do (though for their case they typedef the allocator size_type). data should be a const T* since you do not intend to modify what the pointer points to.

Also is my "algorithm" the correct way to do a range insert?

It seems correct to me. You just need to be careful when shifting elements such that you do not overwrite elements that are to be copied later (e.g., start copying from the end of the used portion of the array).

Incidentally, note that std::vector's range insert() member function takes an iterator pair to denote a range to insert, not an initial iterator and a count.

Originally Posted by laserlight

It seems correct to me. You just need to be careful when shifting elements such that you do not overwrite elements that are to be copied later (e.g., start copying from the end of the used portion of the array).

Ok that makes sense. So how do I "move" the objects in memory?
Like so I think?

Code:

    // move items
            
    int jump = Count() - index; // how many spaces we need to move the element "up"
            
    for (int i = Count(); i > index; --i)
    {
           m_data[i + jump] = m_data[i];
    }

Edit:

What I mean is this leaves behind the old data (I think). m_data[i] is still a valid value correct?
It will be overwritten when I insert the new data though.

The reason I'm asking is that I'm doing a range remove too (in a different function ), and it works similar (but I think it is wrong cuz old data is left)....

I would expect jump to depend on the arguments to range_insert.

In the loop you are probably accessing one beyond the end of the array ( index Count() ), and you don't copy the element at index (STL normally inserts before the location, if I'm not mistaken).

Originally Posted by anon

I would expect jump to depend on the arguments to range_insert.

Right.

Originally Posted by anon

In the loop you are probably accessing one beyond the end of the array ( index Count() ), and you don't copy the element at index (STL normally inserts before the location, if I'm not mistaken).

This is where my code differs from STL.

Does the data I copied "up" still exist?
I think it does, at least until I overwrite it......

Originally Posted by sethjackson

Check if there is enough space, if not, create new array (of T) with (capacity * 2),
copy old data upto index into new array, insert the given data, copy old data
above index.

Not quite. Say you have 2 items in your array and you want to insert 1000 items between the initial two. Perhaps your current array size is 8 (some vector implementation have a certain minimum size). You suggest only doubling it to 16. I suggest that in calculating the size of the new array, you have a while loop "while newsize isn't sufficient, double newsize. Then allocate newsize items".
There should only be one new allocation, of size 1024.

That's a good catch.

Ouch! Nice catch.

Originally Posted by iMalc

There should only be one new allocation, of size 1024.

So like this?

Code:

// Count() is number of items in Array, count is number of items to be added....

if (Count() + count > Capacity())
{
     int size = 8;
                
     while (size < Count() + count)
     {
          size *= 2;
     }
                
     Reserve(size);
}

Edit:

BTW my array has default size of 10? Should it be 8?

Tried on std::vector... Here is what I got with MinGW... :?

Code:

std::vector<int> vec;
    
std::cout << vec.capacity(); // prints 0

I thought vector had a default capacity?