Problem with vector class (and suggestions)

This is a discussion on Problem with vector class (and suggestions) within the C++ Programming forums, part of the General Programming Boards category; I'm trying to implement my own version of the stl vector class. I have gotten the push method to work ...

  1. #1
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39

    Problem with vector class (and suggestions)

    I'm trying to implement my own version of the stl vector class. I have gotten the push method to work properly, as well as the pop to semi-work. The only problem is when the logical size of the array is less then half of the allotted size for the array. I then try to shorten the size of the array by half. I get a runtime error saying I got a memory access problem on "delete[] dynamic_array;"

    Any ideas on why I'm getting the runtime error, as well as suggestions on how I could better improve the class would be greatly appreciated.

    Thanks,

    cs_student

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    stl vector doesn't attempt to shorten the array.

    It's hard to say anything without seeing code.
    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).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The best way to learn to write these things is to learn from existing ones. To that end I highly recommend downloading the Loki library and taking a look at yasli_vector.
    If that doesn't suit you then you'll need to just post code.
    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"

  4. #4
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39
    rofl, I don't know why I didn't post the code, I must of forgot.

    Anyways, I'm also planning on implementing a insert method later on.
    I'll also be sure to take a look at that library.

    Here is the code however,

    Code:
    #ifndef CONTAINER_H
    #define CONTAINER_H
    
    
    namespace JP
    {
    
    template <class Elem> class Container
    {
    public:
    
    	Container( unsigned int start_size = 10 )
    	{
    		dynamic_array = new Elem [ start_size ];
    		current_size = start_size;
    		logical_size = 0;
    	}
    
    	void Push( Elem data )
    	{
    		if( logical_size >= current_size )
    		{
    			
    			temp_array = new Elem[ current_size * 2];
    
    			// Copy dynamic_array to temp_array
    			for( unsigned int i = 0; i <= logical_size; i++)
    			{
    				temp_array[i] = dynamic_array[i];
    			}
    
    			current_size *= 2;
    			delete[] dynamic_array;
    			dynamic_array = new Elem [ current_size ];
    			
    			dynamic_array = temp_array;
    			delete[] temp_array;
    		}
    		else
    		{
    			dynamic_array[logical_size] = data;
    			logical_size++;
    		}
    	}
    	
    	void Pop( unsigned int index )
    	{
    		if( index <= logical_size )
    		{
    			for( unsigned int i = index; i <= logical_size - 1; i++)
    			{
    				dynamic_array[i] = dynamic_array[i+1];
    			}
    
    			dynamic_array[logical_size] =  NULL;
    			logical_size--;
    			
    			if( logical_size < current_size / 2 )
    			{
    				temp_array = new Elem[ current_size / 2 ];
    
    				// Copy dynamic_array to temp_array
    				for( unsigned int i = 0; i <= logical_size; i++)
    				{
    					temp_array[i] = dynamic_array[i];
    				}
    
    				current_size /= 2;
    
    				delete[] dynamic_array;     // debugger shows the runtime error occurs on this line
    				dynamic_array = new Elem [ current_size ];
    				
    				dynamic_array = temp_array;
    				delete[] temp_array;
    			}
    		}
    	}
    
    
    
    private:
    	unsigned int	current_size;		// size of array
    	unsigned int	logical_size;		// size taken up of array
    
    	Elem * dynamic_array;
    	Elem * temp_array;
    
    
    };
    
    } // namespace JP
    
    
    #endif // CONTAINER_H
    
    
    /*********************
    container.cpp
    *********************/
    
    // Container.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include "Container.h"
    struct mystruct {
    };
    
    mystruct struc, struc2, struc3;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	
    	JP::Container< int > MyContainer;
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Pop( 4 );
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Push( 1 );
    	MyContainer.Push( 5 );
    	MyContainer.Push( 33 );
    	MyContainer.Pop( 3 );
    
    	
    	return 0;
    }

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Firstly, temp_array probably shouldn't be a member of the class, since it will be only used locally in a few functions.

    Secondly the name Pop suggests removing the last element, which should trivially mean decrementing the logical_size (unless you really want to shrink the array). What you really have there is what (one version of) vector::erase does.

    Thirdly, it appears that in practically all loops and if conditions you are going out of bounds. If you allocate 10 items, then the indices go from 0 to 9 and using index 10 leads to invalid memory access.

    Fourthly, you appear to have bad memory leaks:
    Code:
    dynamic_array = new Elem [ current_size ];
    dynamic_array = temp_array;
    What was the point of allocating all this memory, if the next line throws away the pointer.

    You are also throwing away memory that you actually hope to use later:
    Code:
    dynamic_array = temp_array;
    delete[] temp_array;
    //dynamic_array now points to deleted memory
    Minor nitpick:
    Code:
    dynamic_array[logical_size] =  NULL;
    Assigning 0 (because that's exactly what NULL means) to any (or most non-numeric) types may not compile. You don't have to do anything about popped items: as far as the user is concerned, they don't exist (the STL vector probably has to destruct the object at that point, though, but that's because the implementation and requirements are different).
    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).

  6. #6
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39
    Thank you for your reply.

    Firstly, temp_array probably shouldn't be a member of the class, since it will be only used locally in a few functions.
    I figured that it would be better to have it locally declared rather than declaring it on the heap every time.

    Code:
     Secondly the name Pop suggests removing the last element, which should trivially mean decrementing the logical_size (unless you really want to shrink the array). What you really have there is what (one version of) vector::erase does
    I now realize that looking back at previous code I've used (OpenGL).

    Please correct me if I'm wrong, or confused, but I thought what I was doing in that section is.

    Code:
    				// Copy dynamic_array to temp_array
    				for( unsigned int i = 0; i <= logical_size; i++)
    				{
    					temp_array[i] = dynamic_array[i];
    				}
    				
    				current_size /= 2;	// change the current size
    
    				delete[] dynamic_array;     // delete current memory of dynamic_array
    				dynamic_array = new Elem [ current_size ];	// allocate new memory to dynamic_array
    				
    				dynamic_array = temp_array;		// copy temp_array to dynamic_array
    				delete[] temp_array;			// delete temp_array


    Again thanks for your help,


    cs_student

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cs_student View Post
    I figured that it would be better to have it locally declared rather than declaring it on the heap every time.
    A variable declared as part of the class takes up space all the time. If you declare the variable as a local variable in that function, it only takes up space when it is actually being used - in that function. And it's not on the heap, but on the stack. The space you allocate when you use new is on the heap.

    Detailed comments on your code below:
    Code:
    				delete[] dynamic_array;     // delete current memory of dynamic_array
    				dynamic_array = new Elem [ current_size ];	// allocate new memory to dynamic_array
    				
    				dynamic_array = temp_array;		// copy temp_array to dynamic_array
    				delete[] temp_array;			// delete temp_array
    delete[] dynamic_array - frees the memory allocated previously (that is twice the size of the new array).
    dynamic_array = new ... - creates space for current_size elements, and store the address of this mmeory in dynamic_array.
    dynamic_array = temp_array. - Make dynamic_array point to temp_array. The memory you allocated one line ago is now lost forever [as in, it is no longer known to your application, and leaked]
    delete[] temp_array - free the memory pointed to by temp_array. dynamic_array is pointing to the same bit of memory - so you have freed the memory that contains your data you want to keep.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Allways learning cs_student's Avatar
    Join Date
    Aug 2008
    Location
    ~/
    Posts
    39
    How can I make dynamic_array simply point to the data that temp_array points to?

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Example:
    Code:
    dynamic_array = temp_array;
    Right? Is there some secret trick I am not aware of in your question?

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,031
    Let's get this straight.
    First you allocate twice the memory in temp_array.
    Then you copy all the data from your current array (dynamic_array) to temp_array.
    Then you allocate new data in dynamic_array for no reason.
    Then you assign the newly allocated array temp_array to dynamic_array. This is right since temp_array is your newly allocated array with all the existing data and all, except... the memory newly allocated to dynamic_array will now be lost! Memory leak!
    Now you for some reason free the memory in temp_array (which is also pointed to by dynamic_array!), which results in that both dynamic_array and temp_array points to freed memory now!

    See that logic above? It's what you're doing. The text in red indicates something strange and/or wrong. See if you can solve it and make it correct.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 10-29-2008, 07:33 AM
  2. Possible Windows MDAC problem
    By BobS0327 in forum Tech Board
    Replies: 3
    Last Post: 06-28-2006, 05:57 AM
  3. Replies: 4
    Last Post: 01-10-2006, 01:23 PM
  4. Some suggestions about an approach to a problem
    By AngKar in forum C Programming
    Replies: 0
    Last Post: 01-03-2006, 03:58 PM
  5. Replies: 0
    Last Post: 02-05-2002, 07:44 PM

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