Implementing Vectors

[ankursaxena]

Hi! I was wondering if you were to implement vector class, how would u resize. i mean would have have to create new size memory and copy all the old elements to the new memory location and delete old? or is there a better way. btw i somehow dont like stl vector and i do know about them, so if you could tell me this that would be great thanx a ton.

-Ankur

 

[MP456]

Why don't use the vector class in stl? Or you can inherit a new class from it.

 

[chipperMDW]

Yes, to resize, you'd have to make new memory, copy over everything, then delete the old. If there's a better way, I've never heard of it. Since vector is a template, you should be able to go into the actual vector header and see the source code. That should help you with any questions you might have in the making you your own vector.

Still, I'd recommend using the STL vector if possible. Sure, it's more fun to play around with the memory yourself, but vector saves time.

 

[ankursaxena]

thanx a lot, i know using stl vector is the best way, but making and testing your own can be fun too, i am not saying i can make it better or anything, but just to see if you, can becuase you never know when u might need an idea that u used to re-invent something, in something else...
anyhow sounds good what u said, thanx a lot..

Ankur

 

[chipperMDW]

No problem.

You have a good point and a good programming attitude: play around with stuff on the most basic level so you can figure out what's going on, and then move up to using stuff that does it for you and saves you time.

 

[jstreich]

I personally would opt for a linked list, then you avoid copy over and reallocation of memory.... The only price you pay is transversals, which are expensive... so I guess it depends on if you really need random access or a stack or queue would work better.

 

[ankursaxena]

but i think the vector speicfication states that you need to have contigous memory assigned.

Ankur

 

[jstreich]

STL vector class is a dynamic array, so yes.. you have to do the copy over, and copy back. I suppose you could use the STL algorithms to that though, but still wastes BigO time.

 

[StukA]

Actually, a dynamically allocated linked list is going to allocate memory for EVERY item added - a dynamically allocated array doesn't have to (the STL vector allows you to reserve space for a given number of items, in addition to growing as needed, and IIRC, it grows in chunks to prevent multiple memory allocations). Except for trivial examples, this is going to save large chunks of time (memory allocation calls will eat you alive in a linked list situation). Add to that the fact that a linked list doesn't provide true random access (sure you can fake it, but look at the BigO time on THAT). Top all of that off with the need to use additional memory (at least one pointer per data item, more likely two) - and a linked list implementation of a vector for ints is TRIPLE the size of a contiguous implementation (obviously for very large structures this difference becomes minute on a per item basis, but think about a large vector - those 64 bits per item may add up anyway...). All in all, I think a linked list is a BAD way to implement a vector class.

 

[jstreich]

operation Link list Vector
insert O(1) O
remove O(1) O
clear O O(1)
find O O
sort O(n^2) O(n lg n)[assuming merge sort]

Which means that if your dealing with larger groups of objects that don't neet to be sorted use a Linked list. If you have a small number, use a vector. If it has to be sorted, use a BST (set).

BST are logrithmic time, no copy overs required. You do pay a system pentalty when memory is allocated or deallocated, but the time saved saved on the search and sort make it worth wild.

I quickly did the chart counting iterations, expressed in Big Oh notation. It of course doesn't take into account system resources (memeory) or system dependant tasks (memory allocation) as it is irrelivent as n(size of job) appraoches infinity, and is varible from system to system. I like linked lists because the pointer manipulations are more interesting then indexing. If you disagree with the Oh times on my chart, I'd be happy to tell you why and how I got them.

Moreover, the copy back (everytime you run out of space) takes more memory than the byte that holds the address of the next item. Since you typically find before a remove, and don't have to copy the items over the Big Oh times are quite comperable, unless you begin talking about a sorted vector (which screams BST to me) and divide and conquor implementations.