Is it safe to assume that STL vector storage is always contiguous?
Yes, that is a valid assumption (*).
From the C++03 standard (23.2.4.1):
The elements of a vector are stored
contiguously, meaning that if v is a
vector where T is some
type other than bool, then it obeys
the identity &v[n] == &v[0] + n for
all 0 <= n < v.size().
(*) ... but watch out for the array being reallocated (invalidating any pointers and iterators) after adding elements to it.
Are std::vector elements guaranteed to be contiguous?
This was missed from C++98 standard proper but later added as part of a TR. The forthcoming C++0x standard will of course contain this as a requirement.
From n2798 (draft of C++0x):
23.2.6 Class template vector [vector]
1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized)
constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage
management is handled automatically, though hints can be given to improve efficiency. The elements of a
vector are stored contiguously, meaning that if v is a vector where T is some type other
than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
Is data storage in std::vector continuous?
From the n2798 (draft of C++0x)::
23.2.6 Class template vector [vector]
1 A vector is a sequence container that supports random access
iterators. In addition, it supports (amortized) constant time insert
and erase operations at the end; insert and erase in the middle take
linear time. Storage management is handled automatically, though hints
can be given to improve efficiency. The elements of a vector are
stored contiguously, meaning that if v is a vector where T is some
type other than bool, then it obeys the identity &v[n] == &v[0] + n
for all 0 <= n < v.size().
Also do check array being reallocated (invalidating any pointers and iterators) after adding elements to it.
Also check this article:- Cringe not: Vectors are guaranteed to be contiguous
contiguity is in fact part of the vector abstraction. It’s so
important, in fact, that when it was discovered that the C++98
standard didn’t completely guarantee contiguity, the C++03 standard
was amended to explicitly add the guarantee.
Also from the C++ FAQ
#include <vector>
#include "Foo.h" /* get class Foo */
// old-style code that wants an array
void f(Foo* array, unsigned numFoos);
void g()
{
std::vector<Foo> v;
...
f(v.empty() ? NULL : &v[0], v.size()); ← safe
}
The funny expression v.empty() ? NULL : &v[0] simply passes the NULL pointer if v is empty, otherwise passes a pointer to the first (zeroth) element of v. If you know a priori that v is not empty, you can change that to simply &v[0].
In general, it means you are guaranteed that &v[0] + n == &v[n], where v is a std::vector<T> and n is an integer in the range 0 .. v.size()-1.
However v.begin() is not guaranteed to be a T*, which means v.begin() is not guaranteed to be the same as &v[0]:
void g()
{
std::vector<Foo> v;
...
f(v.begin(), v.size()); ← Error!! Not Guaranteed!!
^^^^^^^^^-- cough, choke, gag; not guaranteed to be the same as &v[0]
}
std::vector of std::vectors contiguity
No. The elements of a vector are stored in a dynamically allocated block of memory; otherwise, the capacity of the vector could not increase. The vector object just holds a pointer to that block.
The requirement that the elements be stored sequentially applies only to the elements themselves, and not to any dynamically allocated members of those elements.
Why is std::vector contiguous?
If std::vector didn't guarantee contiguousness, a new container would be invented which did.
The contiguity guarantee makes it easier to inter-operate with existing code that expects a contiguous array, and also gives very good performance because it is cache-friendly. (Inserting/deleting in the middle is in practice very fast for moderate sizes because of this.)
Copying the array on expansion is surprisingly cheap - if you append to a vector a million elements one at a time, each element will have been copied on average around once.
Is an array of vectors entirely contiguous memory?
Memory footprint of std::vector consists of two parts:
- The memory for the
std::vectorobject itself (very small, and independent of the size), and - The memory for the data of the vector (depends on the number of elements in the vector).
The first kind of data will be contiguous in an array; the second kind of data is allocated dynamically, so it would not be contiguous in an array.
This would not be the same as with a C struct that has a flexible data member, because the data portion of std::vector is not always allocated in the same kind of memory, let alone being adjacent to it. The vector itself may be allocated in static, dynamic, or automatic memory areas, while its data is always in the dynamic area. Moreover, when vector is resized, the memory for its data may be moved to a different region.
Each time you call push_back, std::vector checks if it has enough dynamic memory to accommodate the next data element. If there is not enough memory, then the vector allocates a bigger chunk of memory, and moves its current content there before pushing the new item.
std::vector contiguous meaning
Contiguous in this context means that sequentially numbered vector's elements are located next to each other in memory space. For example, if an element i is located at the address a, and has a size of s, then the element i+1 would be located at the address a+s, the element i+2 would be at a+s+s, and so on.
This is important for two reasons:
- Contiguous requirement makes random access possible - you can compute the location of any element based on vector's base address and element's index
- You can predict locality of reference - processing vector elements sequentially is the same as processing array elements sequentially for the purposes of cache behavior analysis.
Contiguous allocation of objects using STL vector
"I need to create objects dynamically"
Are you REALLY sure you NEED the dynamic allocation? If it is possible, use vector of objects instead:
std::vector<T> myObjects(100);
this allocates the single block of memory big enough to hold 100 instances of T and initializes them using the default constructor.
What does std::vector look like in memory?
It roughly looks like this (excuse my MS Paint masterpiece):
The std::vector instance you have on the stack is a small object containing a pointer to a heap-allocated buffer, plus some extra variables to keep track of the size and and capacity of the vector.
So it seems as though when I
push_back()to thenumbersvector, its older elements change their location.
The heap-allocated buffer has a fixed capacity. When you reach the end of the buffer, a new buffer will be allocated somewhere else on the heap and all the previous elements will be moved into the new one. Their addresses will therefore change.
Does it maybe store them together, but moves them all together, when more space is needed?
Roughly, yes. Iterator and address stability of elements is guaranteed with std::vector only if no reallocation takes place.
I am aware, that
std::vectoris a contiguous container only since C++17
The memory layout of std::vector hasn't changed since its first appearance in the Standard. ContiguousContainer is just a "concept" that was added to differentiate contiguous containers from others at compile-time.
How does std::vector support contiguous memory for custom objects of unknown size
Your concept of size is flawed. A std::vector<type> has a compile time known size of space it is going to take up. It also has a run time size that it may use (this is allocated at run time and the vector holds a pointer to it). You can picture it laid out like
+--------+
| |
| Vector |
| |
| |
+--------+
|
|
v
+-------------------------------------------------+
| | | | | |
| Element | Element | Element | Element | Element |
| | | | | |
+-------------------------------------------------+
So when you have a vector of things that have a vector in them, each Element becomes the vector and then those point of to their own storage somewhere else like
+--------+
| |
| Vector |
| |
| |
+----+---+
|
|
v
+----+----+---------+---------+
| Object | Object | Object |
| with | with | with |
| Vector | Vector | Vector |
+----+----+----+----+----+----+
| | | +---------+---------+---------+---------+---------+
| | | | | | | | |
| | +--->+ Element | Element | Element | Element | Element |
| | | | | | | |
| | +-------------------------------------------------+
| | +-------------------------------------------------+
| | | | | | | |
| +--->+ Element | Element | Element | Element | Element |
| | | | | | |
| +-------------------------------------------------+
| +-------------------------------------------------+
| | | | | | |
+--->+ Element | Element | Element | Element | Element |
| | | | | |
+---------+---------+---------+---------+---------+
This way all of the vectors are next to each other, but the elements the vectors have can be anywhere else in memory. It is for this reason you don't want to use a std:vector<std::vector<int>> for a matrix. All of the sub vectors get memory to wherever so there is no locality between the rows.
Do note that this applies to all of the allocator aware containers as they do not store the elements inside the container directly. This is not true for std::array as, like a raw array, the elements are part of the container. If you have an std::array<int, 20> then it is at least sizeof(int) * 20 bytes in size.
Related Topics
Differences Between Unique_Ptr and Shared_Ptr
What Are Inline Namespaces For
Why Is Std::Map Implemented as a Red-Black Tree
Running My Program Says "Bash: ./Program Permission Denied"
How to Calculate Execution Time of a Code Snippet in C++
Unresolved External Symbol in Object Files
C++ Pass an Array by Reference
How Std::Unordered_Map Is Implemented
Is the Return Type Part of the Function Signature
Boost Asio Async_Write: How to Not Interleaving Async_Write Calls
Opencv Better Detection of Red Color
Is Std::Vector or Boost::Vector Thread Safe
C++ Call Pointer to Member Function
Undefined Symbol _Gxx_Personality_V0 on Link
Function With Missing Return Value, Behavior At Runtime