Vectors,Stacks... how do they add new elements without erasing what they've got?

[Blessman11]

hi

I've just learnt that with runtime arrays, each time you want to expand the array you'd have to to clear everything in the array like this?

...
Int * iaExample;

iaExample = new int [x];

...

//relised that iwould have to add/reduce array

iaExample = new int [n];
//But as soon as that happens above with 'n', the whole array is cleared thus 
//ruining everything.

//why is this? 
//Yet when pushing and poping vectors, stacks...the  elements aren't damaged in 
//the resizing process. 

//What magic was bjarne stroustrup using?
...

[Gaminic]

The "magic" behind vectors becomes clear once you start using very large ones.

This is one of the major problems with premade container classes. You may think they are efficient, or even "magic", but they are simply hiding the calculations rather than forcing you to think about the efficiency.

A vector does the same thing an array does when it needs to insert (or erase) an element or resize the array for any reason:
-Make new array with new size.
-Copy all elements of old array.
-Return address of new array to old array.

The complexity of any insert/erase/resize function is linear to amount of elements in it.

[edit]

The complexity of push/pop is "constant". By insert/erase, I meant "at any location other than end (and for some: start).

[Dacster13]

@Blessman11 that would be a bit difficult to understand without basic understanding of the theories behind data structures and algorithms, which is actually a whole subject on it's own in computer science. A good book on the subject will explain it a lot more concisely and help you understand it better though.

The basic idea is that instead of allocating a group of memory at once like in an array, it instead allocates each element called nodes one at a time, and chains them up via pointers. So you can keep allocating one node and just attach it to the end of the chain of nodes that you have. So you can grow the chain dynamically without erasing anything. I hope that helps clarify it.

A vector does the same thing an array does when it needs to insert (or erase) an element or resize the array for any reason:
-Make new array with new size.
-Copy all elements of old array.
-Return address of new array to old array.

@Gaminic are you sure it does that? I've always thought of vectors more like a linked list with added functionality of stacks and queues, where you can push in the front or back of the whole thing. Allocating a whole new array and then copying it just seems way to inefficient so vectors probably don't really do it that way, although I'm not certain about that and I could be wrong.

[helios]

Allocating a whole new array and then copying it just seems way to inefficient

It is, but it's an acceptable sacrifice to get efficient random access.
The definition of "vector" in the standard guarantees that every conforming implementation of vectors is like this, by the way. You won't find a vector trying to do anything smart because that would break some semantics. A vector must behave like this:
Access: O(1)
Resize (n>0): O(n)
Insertion at the back: amortized O(1) (capacity filled implies a resize operation)
Insertion elsewhere: O(n)
Also, this is guaranteed: (&(vector[i]))+1==&(vector[i+1])

[shacktar]

The basic idea is that instead of allocating a group of memory at once like in an array, it instead allocates each element called nodes one at a time, and chains them up via pointers.

std::lists do that, std::vectors use arrays.

Allocating a whole new array and then copying it just seems way to inefficient

They only allocate a whole new array and copy when their capacity is filled. What vectors do is they allocate more than is necessary. Say, for instance you instantiate a vector and do 5 push_back calls. The underlying array won't have 5 elements, but rather something like 10. Then, the next 5 push_back calls wouldn't require a resize. This is how they accomplish O(1) amortized time when inserting at the back. Inserting elsewhere requires moving every element from that index on forward, hence the O(n) time for insertions elsewhere.