Sign in to follow this  

Array algorithm for pushing back items (home-made).

This topic is 4304 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In C++, I am trying to do the best I can to replicate the std::vector object (and others). Currenty I am making a function to push back/front objects, but it fails once I call it. The application terminates and the usual "This application has terminated in an unusual way..." appears. This is the function:
template<class _type, class _allocater>
    array<_type, _allocater> &array<_type, _allocater>::push_back(const _type &object) {
        if (++m_size > m_capacity) {
            m_capacity *= 2;

            _type *old_array = m_array;

            m_array = m_allocater.allocate(m_capacity);
            for (unsigned i = 0; i < m_size; i++)
                m_array[i] = old_array[i];

            m_allocater.deallocate_array(old_array);
        }

        m_array[m_size - 1] = object;

        return *this;
    }

m_allocater is a default allocater for (in it's default form) uses new, new[] and delete, delete[] to manage the heap. Does anyone see what I may be doing wrong or incorrectly? My theory is to double the capacity every time the size is larger than it... Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
What's the initial value of m_capacity?


m_capacity is either:
1) Set to 0 (default)
2) Set to a copy's capacity
3) Set to a user defined size (if it's array arr(1), etc.)
4) Umm... That's it I think

Any ideas? Thanks for the quick reply!

Share this post


Link to post
Share on other sites
Quote:
Original post by agi_shi
Quote:
Original post by jyk
What's the initial value of m_capacity?


m_capacity is either:
1) Set to 0 (default)
2) Set to a copy's capacity
3) Set to a user defined size (if it's array arr(1), etc.)
4) Umm... That's it I think

Any ideas? Thanks for the quick reply!


I think I see what I did wrong. If it's zero and I *= by 2 then it would be 0 and I am allocating an array of size 0 :(. I'll see if that's it...

EDIT: Nope, not it...

Share this post


Link to post
Share on other sites
Quote:
Original post by agi_shi
If it's zero and I *= by 2 then it would be 0 and I am allocating an array of size 0
That's what I was getting at. You said it still doesn't work though. Does it crash the very first time you call it? If so, you might post the new code (with the fix for m_capacity == 0). You could also cout << some debug info, such as what m_size and m_capacity are before and after you change their values.

Share this post


Link to post
Share on other sites
I may be wrong but should:

_type *old_array = m_array;

be:

_type old_array = m_array;

cause it looks like it's pointing to the same memory and then you deallocate old_array.

Share this post


Link to post
Share on other sites
Quote:
Original post by nomichi
I may be wrong but should:

_type *old_array = m_array;

be:

_type old_array = m_array;

cause it looks like it's pointing to the same memory and then you deallocate old_array.


That's exactly what I wanted to do. Use the memory from m_array to copy to a new m_array. So I assign a pointer to m_array's memory and allocate new memory for m_array without deleting it so I can copy it over. Then I have a pointer that I can use to delete the old memory.

Anyone have any ideas?

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by agi_shi
If it's zero and I *= by 2 then it would be 0 and I am allocating an array of size 0
That's what I was getting at. You said it still doesn't work though. Does it crash the very first time you call it? If so, you might post the new code (with the fix for m_capacity == 0). You could also cout << some debug info, such as what m_size and m_capacity are before and after you change their values.


I am thinking of putting this in VC2k5EE and debugging...

Thanks for giving a suggestion though :).

Share this post


Link to post
Share on other sites
Quote:
Original post by Plasmarobo
Maybe you should just use namespace std and vectors? Wouldn't that be more efficent?


I should have stated that this is to learn. [smile]

Share this post


Link to post
Share on other sites
Theres another bug which could be causing the crash. One of the very first things you do is increment m_size. When you go to copy the old array to the new one, it copies m_size elements - but the old array only contains m_size-1 elements. Two things happen here; you call the the assignment operator on an un-constructed object (incidentally, it looks like you never construct ANY of the objects. This is fine for builtins, but bad for classes) and your source object is outside the bounds of the array.

Rewritten, with the 0-capacity bug fixed too. And a tweak in the middle to make it more exception safe.

template<class _type, class _allocater>
array<_type, _allocater> &array<_type, _allocater>::push_back(const _type &object) {
if (m_size >= m_capacity) {
size_t new_capacity = (m_capacity * 2) + 1; //fixes capacity=0 bug

//replace this with some variation of std::auto_pointer that calls
//the deallocation function to prevent memory leaks
_type* new_array = m_allocater.allocate(new_capacity); //can throw

for (unsigned i = 0; i < m_size; i++)
new (new_array + i) _type(m_array[i]); //if this throws, we leak. :(
//also, note the call to the copy constructor.

//If we've made it this far, we have a new copy - but haven't actually
//modified the old copy yet! This is the strong exception safety
//guarantee.
std::swap(new_array,m_array); //can't throw
m_capacity = new_capacity; //can't throw
m_allocater.deallocate_array(new_array); //if this throws, we leak. :(
}

new (m_array + m_size) _type(object); //again, copy constructor
//if this constructor throws, the capacity has changed, but not the
//size - the exception does no damage.
++m_size; //finally, update the size.

return *this; //WTF? mycontainer.push_back(1).push_back(2).push_back(etc)?
}

Share this post


Link to post
Share on other sites
Sorry. I neglected to de-construct the contained objects. :(


template<class _type, class _allocater>
array<_type, _allocater> &array<_type, _allocater>::push_back(const _type &object) {
if (m_size >= m_capacity) {
size_t new_capacity = (m_capacity * 2) + 1; //fixes capacity=0 bug

//replace this with some variation of std::auto_pointer that calls
//the deallocation function to prevent memory leaks
_type* new_array = m_allocater.allocate(new_capacity); //can throw

unsigned i = 0;
try {
for (; i < m_size; ++i)
new (new_array + i) _type(m_array[i]); //if this throws, we leak. :(
//also, note the call to the copy constructor.
} catch(...) {
for (i -= 1; i >= 0; --i)
(new_array + i)->~_type(); //Why destructors should never throw...
throw; //re-emmit exception
}

//If we've made it this far, we have a new copy - but haven't actually
//modified the old copy yet! This is the strong exception safety
//guarantee.
std::swap(new_array,m_array); //can't throw
m_capacity = new_capacity; //can't throw

//destroy old objects.
for (unsigned i = 0; i < m_size; ++i)
(new_array + i)->~_type();
m_allocater.deallocate_array(new_array); //if this throws, we leak. :(
}

new (m_array + m_size) _type(object); //again, copy constructor
//if this constructor throws, the capacity has changed, but not the
//size - the exception does no damage.
++m_size; //finally, update the size.

return *this; //WTF? mycontainer.push_back(1).push_back(2).push_back(etc)?
}

Share this post


Link to post
Share on other sites
Dare I suggest cracking open your compiler's implementation of std::vector and reading through it instead? The variable names are likely to suck, but it's still very instructive.

Share this post


Link to post
Share on other sites
Not really.


void push_back(const _Ty& _Val)
{ // insert element at end
if (size() < capacity())

#if _HAS_ITERATOR_DEBUGGING
{ // room at end, construct it there
_Orphan_range(_Mylast, _Mylast);
_Mylast = _Ufill(_Mylast, 1, _Val);
}

#else /* _HAS_ITERATOR_DEBUGGING */
_Mylast = _Ufill(_Mylast, 1, _Val);
#endif /* _HAS_ITERATOR_DEBUGGING */

else
insert(end(), _Val);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
One of the very first things you do is increment m_size. When you go to copy the old array to the new one, it copies m_size elements - but the old array only contains m_size-1 elements.
It looks to me like that's the problem.
Quote:
Original post by Deyja
Two things happen here; you call the the assignment operator on an un-constructed object (incidentally, it looks like you never construct ANY of the objects. This is fine for builtins, but bad for classes)
I don't think that's the case here. I'm guessing his allocator is parameterized by the type he's working with, and it uses new/new[] and delete/delete[] for allocation/deallocation, so his objects should be constructed just fine. Think something along these lines:

template<typename T>
class allocator
{
T* allocate(unsigned int count)
{
return new T[count];
}

void deallocate_array(T* array)
{
delete[] array;
}
};

Using an allocator in this fashion means you won't have to manually construct/destruct each individual object as in your post.

Share this post


Link to post
Share on other sites
It also means that objects that aren't really 'in the array', ie, objects within capacity but above m_size, are fully constructed.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
It also means that objects that aren't really 'in the array', ie, objects within capacity but above m_size, are fully constructed.
And that there'll be a lot of extra default constructor calls. I hadn't considered those performance aspects. Point taken.

Share this post


Link to post
Share on other sites
I'd recommend learning (and then using) assertions. Figure out your preconditions and postconditions and then assert them at the beginning/end of every method on your object.

Share this post


Link to post
Share on other sites

This topic is 4304 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this