STL Vector vs List

[Gdschaf]

I don't know if Windows Programming is the best place for this, or just General C++ Programming, but I have a question about how the STL vector works behind the scenes. I've used both, I know that vectors have random access and you have to walk through a list to find anything, but how is a vector laid out in memory? is it contiguous? or does it use a link list sort of thing with nodes pointing to other nodes? if it is contiguous, does the vector manage one large block of memory and splits it up like a list? i think the STL vector has an option of resizing

What i'm trying to do is recreate a library of containers that are optimized for what I'm using them for.

any information is much appreciated, thanks.

[ResidentBiscuit]

It's contiguous. A vector is just a dynamic array, that resizes when need be. Thing to keep in mind there, are that when this resizing happens, any pointers you have to the vector could become invalid due to the vector possibly having to find a new spot in memory that can hold it.

[Gdschaf]

oh I didn't think about that, pointers to pointers may be in order

I have a few more questions too, what if something is deleted in them middle of a vector? is everything shifted over?
how does it resize? like, current size *= 2?
and how would I access things from the large chunk of memory? like address of large chunk + (size of type * index)?

Thanks for the response

[ResidentBiscuit]

I have a few more questions too, what if something is deleted in them middle of a vector? is everything shifted over?

Yup, the vector has to shift to fill that hole. Can be costly, and also can invalidate pointers. Vectors aren't suited for this.

how does it resize? like, current size *= 2?

I would imagine this is implementation defined, but don't quote me on that.

and how would I access things from the large chunk of memory?

Same way you would do it with an array, that's all vectors are behind the scenes.

[Gdschaf]

oh ok, I got it, that makes a lot of sense and you answered pretty much all of my questions, thanks a lot!