stl vector uses link list ?????????

stl vector uses link list ?????????

Linked lists are not contiguous, and the getting of data not at the ends is linear, not constant time.

Vectors on the other hand are all stored in one big block of memory (moved and doubled in size when necessary) so that you can get elements in constant time.

I don't see how one can store the other...


However, if i remember correctly, deques have some strange list-type structure that gives pointers to large blocks of memory, so access is almost constant... but it is certainly not one big long list.

You mean it is a dynamic array.

Yeah basically. The major difference between the two is random access.

Check out my vectro info
http://www.techno-coding.com/pages/t...tor/vector.htm

I also have some basic tutorials for vectors as well.

How does vector allocate memory?

With an allocator object, which asks the system for the memory. (and may do other stuff - you can write your own allocator for special purposes).

Thanks.
If I want to add new items in the vector then
it creates a new array of new size and copy the old array into it and delete the old array.Is it?

If there's not enough space for the new item, it will have to allocate a new array and copy, yes. But when it has to do that, it will allocate more memory than it's currently using (doubling in size I think) so that when you add more items in the future, it doesn't have to allocate and copy every time.