3

Possible Duplicate:
Are std::vector elements guaranteed to be contiguous?

does std::vector always contain the data in sequential memory addresses as array[number]?

Community
  • 1
  • 1
Carl17
  • 59
  • 3
  • 1
    Duplicate of [Are std::vector elements guaranteed to be contiguous?](http://stackoverflow.com/questions/849168/are-stdvector-elements-guaranteed-to-be-contiguous) – James McNellis Jun 20 '10 at 01:03

5 Answers5

6

For all types except bool, the standard requires the elements are contiguous in memory:

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()

Do keep in mind that std::vector<bool> has special requirements and is not the same as an array of bool.

R Samuel Klatchko
  • 74,869
  • 16
  • 134
  • 187
5

Yes. Given:

std::vector<int> arr;

you can be sure that

&arr[0]

will give you a pointer to a contiguous array of ints that can (for instance) be passed legacy APIs.

Steve Fallows
  • 6,274
  • 5
  • 47
  • 67
  • 1
    No, you can't. The standard allocator allocates memory with new. Allocated memory is *not* an array. The whole premise is wrong. I might be picky, but it's still true. Allocated memory is not an array. They simply share semantics. –  Jun 20 '10 at 00:47
  • Typically you write it as &arr.front() – Brian R. Bondy Jun 20 '10 at 00:48
  • @Brian R. Bondy: I would disagree. &arr[0] is what is specified in Effective STL, and I've never seen anyone use &arr.front() myself. &arr[0] is also the specification in the standard 23.2.4/1 quoted in R Samuel Klatchko's post. – Billy ONeal Jun 20 '10 at 01:09
  • @Billy: OK fair enough, I have just seen it the .front way everywhere before. – Brian R. Bondy Jun 20 '10 at 01:13
  • @Mads: What are you talking about? The standard is very clear about this issue: "Entities created by a *new-expression* have dynamic storage duration [...] If the entity is a nonarray object, the *new-expression* returns a pointer to the object created. If it is an array, the *new-expression* returns a pointer to the initial element **of the array**." – fredoverflow Jun 20 '10 at 08:26
  • FredOverflow: A pointer is not an array. They share some semantics, but that's all. Because of the standard allocator, I would not call Vector for an array. Is that better? :) –  Jun 20 '10 at 09:31
1

Yes. It does not, however, allocate on the stack.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
0

Yes, the vector use sequential memory for all the elements stored. That means random access is almost as fast as normal array's index.

But vector allocate its memory in heap instead of stack. So it could be less less efficient in some cases.

Shuo
  • 8,447
  • 4
  • 30
  • 36
0

When you use the standard allocator, you can be sure that the allocated memory is continuous when using std::vector. In other words, foo[n+1] is the next element in the sequence after foo[n]. But std::vector is not an array, just like

int* blah = new int[100];

is not an array. But

int blah[100];

made on the stack is an array. Pointers to allocated memory and arrays just happen to share semantics. They are not equal per the standard, so don't confuse the two.

  • 2
    This is not correct. `new int[100]` does indeed create an array. "Entities created by a new-expression have dynamic storage duration... If [the entity] is an array, the new-expression returns a pointer to the initial element of the array" (C++03 §5.3.4/1). `blah` is not an array, but the object created by `new int[100]` is. – James McNellis Jun 20 '10 at 00:57
  • Ah, right. Thanks for the correction :-) –  Jun 20 '10 at 01:29