{"id":108524,"date":"2023-08-02T07:00:00","date_gmt":"2023-08-02T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108524"},"modified":"2025-03-04T21:21:44","modified_gmt":"2025-03-05T05:21:44","slug":"20230802-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230802-00\/?p=108524","title":{"rendered":"Inside STL: The vector"},"content":{"rendered":"

The C++ language comes with a standard library, and although implementations are welcome to implement the library types in whatever manner they choose, there are constraints imposed by the standard which often force one of a small number of possible implementations.<\/p>\n

The std::vector<\/code> is one of those types which is constrained to the point that there’s really only one viable implementation.<\/p>\n

Internally, a std::vector<\/code> basically looks like this:<\/p>\n

template<typename T>\r\nstruct vector\r\n{\r\n    T* first;\r\n    T* last;\r\n    T* end;\r\n};\r\n<\/pre>\n
The first<\/code> is a pointer to the beginning of a single memory allocation that holds the vector contents.<\/p>\n
The last<\/code> is a pointer one past the end of the last valid vector element.<\/p>\n
The end<\/code> is a pointer one past the end of the last allocated memory for the vector.<\/p>\n
The picture for this is as follows:<\/p>\n\n\n\n\n\n
\u00a0<\/td>\n
<\/p>\n
first<\/td>\n
<\/p>\n
 <\/td>\n <\/td>\n <\/td>\nlast<\/td>\n <\/td>\nend<\/td>\n<\/tr>\n
\u2193<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n\u2193<\/td>\n <\/td>\n\u2193<\/td>\n<\/tr>\n
T<\/td>\nT<\/td>\nT<\/td>\nT<\/td>\nT<\/td>\n?<\/td>\n?<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The first<\/code> points to the start of the allocation.<\/p>\n
The memory between first<\/code> and last<\/code> is used to hold live elements of the vector. The size()<\/code> of the vector is last - first<\/code>.<\/p>\n
The memory between last<\/code> and end<\/code> is not being used for anything. The capacity()<\/code> of the vector is end - first<\/code>.<\/p>\n
If you actually dump the std::vector<\/code> in the debugger, you’ll see that it’s actually more complicated than this due to the need to store an allocator. The allocator is usually an empty class (the default allocator certainly is), so I didn’t show it in the conceptual version above.<\/p>\n
Since the allocator is usually an empty class, it is stored as a compressed pair with one of the other members so that it usually occupies no memory.<\/p>\n
The Visual Studio debugger contains a visualizer to view the contents of a std::vector<\/code> more conveniently, but if you need to dig out the three magic pointers yourself, here’s how you can do it with the Microsoft implementation of the standard library:<\/p>\n
0:001> ?? v\r\nclass std::vector<T,std::allocator<T> >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::allocator<T>,std::_Vector_val<std::_Simple_types<T> >,1>\r\n0:000> ?? v._Mypair\r\nclass std::_Compressed_pair<std::allocator<T>,std::_Vector_val<std::_Simple_types<T> >,1>\r\n   +0x000 _Myval2          : std::_Vector_val<std::_Simple_types<T> >\r\n0:000> ?? v._Mypair._Myval2\r\nclass std::_Vector_val<std::_Simple_types<T> >\r\n   +0x000 _Myfirst         : T* \u21d0\r\n   +0x008 _Mylast          : T* \u21d0\r\n   +0x010 _Myend           : T* \u21d0\r\n<\/pre>\n
The language requirements pretty much require this layout for a vector because the data()<\/code> method must return a pointer to contiguous memory, and the constraints on the capacity()<\/code> require that the excess elements come immediately after.<\/p>\n
In particular, the language forbids a “small vector optimization” analogous to the small string optimization (which we’ll see soon), because the standard requires that\u00b9 moving a vector not invalidate iterators or references. The vector elements have to remain where they are. A small-vector optimization would put them in vector-internal storage, which would require that the element move from one vector to another on a vector move operation, which is not allowed.<\/p>\n
\u00b9 Assuming you’re using a well-behaved allocator.<\/p>\n","protected":false},"excerpt":{"rendered":"
A contiguous memory block, reallocated as necessary.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-108524","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
A contiguous memory block, reallocated as necessary.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108524","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108524"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108524\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108524"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108524"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108524"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}