Dynamic array, InsertRange implementation

Hey guys I'm having a mental block.
I want to implement an InsertRange() function, on my array class, and I'm having trouble figuring out how to implement it. (needs to work like std::vector)

Code:

---

void InsertRange(int index, T* data, int count)
{

}

---

So this is what I'm thinking....

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.

Else move everything above (index + count), by count, then insert given data.
Is that right?

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.

Quote:

---

Originally Posted by laserlight

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.

---

Oops. How could I forget const? Heh thanks.

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

Quote:

---

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.

Quote:

---

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).

Quote:

---

Originally Posted by anon

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

---

Right.

Quote:

---

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

Quote:

---

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.

Quote:

---

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?

>> I thought vector had a default capacity?
There is so defined default capacity. Some do and some don't. The capacity is only the amount of memory currently allocated. You still have to add elements to the vector even when the capacity is non-zero.

Note that while capacity() returns how many elements can fit into memory already allocated, the size() method returns how many items are actually in the vector. A vector will always default to a size of 0 when you create it without specifying a starting size.

If you use push_back (or some other inserting function) to add to the vector, then the capacity will increase to something greater than one and the size will be exactly 1.