Dynamic array, InsertRange implementation

This is a discussion on Dynamic array, InsertRange implementation within the C++ Programming forums, part of the General Programming Boards category; Hey guys I'm having a mental block. I want to implement an InsertRange() function, on my array class, and I'm ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    96

    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?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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.
    Last edited by laserlight; 03-14-2008 at 01:47 PM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by laserlight View Post
    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?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by laserlight View Post
    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)....
    Last edited by sethjackson; 03-14-2008 at 03:08 PM.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Quote Originally Posted by anon View Post
    I would expect jump to depend on the arguments to range_insert.
    Right.

    Quote Originally Posted by anon View Post
    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......
    Last edited by sethjackson; 03-14-2008 at 03:43 PM.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    Quote Originally Posted by sethjackson View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    That's a good catch.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    96
    Ouch! Nice catch.

    Quote Originally Posted by iMalc View Post
    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?
    Last edited by sethjackson; 03-17-2008 at 01:17 PM.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help with dynamic array syntax
    By soldyne in forum C Programming
    Replies: 3
    Last Post: 10-11-2005, 01:59 PM
  2. two-dimensional dynamic array of pointers to classes
    By Timo002 in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 06:18 AM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. 2D dynamic array problem
    By scsullivan in forum C Programming
    Replies: 3
    Last Post: 12-30-2002, 09:02 PM
  5. Dynamic array allocation and reallocation
    By purple in forum C Programming
    Replies: 13
    Last Post: 08-01-2002, 11:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21