confused between vector and array

[AchyMain]

I have two very simple pieces of code: reserve space for 10^6 ints, then assign ints from 0 to 10^6 in that space. There are two ways of doing this: one with vectors and one with arrays. If I understand vectors right, these two should be functionally equivalent, but one takes longer than the other. Will someone please explain this to me?

#include<iostream>
#include<vector>

using namespace std;

int main(){
  int N = 1000000;
  vector<int>t;
  t.reserve(N*sizeof(int));
  for (int i = 0; i<N; i++){
    t.push_back(i);
  }
  return 0;
}

>> g++ -O3 vector_reserve.cpp -o vector.out
>> time ./vector.out
real	0m0.015s
user	0m0.006s
sys	0m0.007s

The other code is

#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
  int N = 1000000;
  int * t = (int *)malloc(sizeof(int)*N);
  for (int i = 0; i<N; i++){
    t[i] = i;
  }


  free(t);
  return 0;

}

>>g++ -O3 array_reserve.cpp -o array.out
>>time ./array.out
real	0m0.010s
user	0m0.002s
sys	0m0.007s

Shouldn't these be the same? Or is there something about the implementation of vector that I don't understand? Or am I doing something stupid? Or all of the above?

[brokenbot]

Arrays have a fixed or static amount of elements in them. While vectors are constantly growing. Vectors will take longer because they start out at 0... you must assign them a number to allocate or add to them... and this vector has to grab another element from the heap. All this extra grabbing, reserving from the heap gives overhead to the actual operations rendering it slower than using an array.

[AchyMain]

and this vector has to grab another element from the heap. All this extra grabbing, reserving from the heap gives overhead to the actual operations rendering it slower than using an array.

Thanks for the quick reply. So

t.reserve(N * sizeof(int));

doesn't allocate a contiguous block of memory for the vector to grow in at once?

If what I'm asking makes no sense, please be patient :-) I am a nub.

[1vRz3TCk]

vector::reserve
Requests that the capacity of the allocated storage space for the elements of the vector container be at least enough to hold n elements.

This informs the vector of a planned increase in size, although notice that the parameter n informs of a minimum, so the resulting capacity may be any capacity equal or larger than this.

When n is greater than the current capacity, a reallocation is attempted during the call to this function. If successful, it grants that no further automatic reallocations will happen because of a call to vector::insert or vector::push_back until the vector size surpasses at least n (this preserves the validity of iterators on all these future call

http://www.cplusplus.com/reference/stl/vector/reserve/

[hanst99]

doesn't allocate a contiguous block of memory for the vector to grow in at once?

Actually, that's exactly what it does. A vector still does have some extra maintenance work to do when pushing elements on it though, like updating it's internal size counter etc - but as you can see, the performance difference isn't that great, so normally you'd be fine with vectors. And since dealing with vectors is in general more pleasant than dealing with arrays, I'd always prefer those. But maybe that's just me.

[1vRz3TCk]

t.reserve(N * sizeof(int));
is also allocating a bit more space than
int * t = (int *)malloc(sizeof(int)*N);

[AchyMain]

t.reserve(N * sizeof(int));
is also allocating a bit more space than
int * t = (int *)malloc(sizeof(int)*N);

and it's probably allocating memory two times: once when vector<int>t; is called and once again when the t.reserve(N * sizeof(int)); is called...

Thanks everyone, this really helps me understand vectors :-)

[hanst99]

If you are still here - don't use malloc in C++. We have new for that.

[AchyMain]

If you are still here - don't use malloc in C++. We have new for that.

I didn't realize there was a difference between the two.

[hanst99]

There is. More than one.

[DSLq5Di1]

Also note, mallocs size argument is the number of bytes to allocate, the argument for vector::reserve() is the minimum number of elements to allocate space for.. t.reserve(N);

[hanst99]

Oh, good that you spotted that one sloppy. Didn't pay attention there.

[1vRz3TCk]

o_0 I'm going to have to be less subtle in my responses in future...

[DSLq5Di1]

I was curious if that was what you were getting at CodeMonkey, though I don't think you made it very clear.

[1vRz3TCk]

though I don't think you made it very clear.

I sometimes just give crumbs for the OPs to follow, the idea is to get them to read around the subject to help it 'stick'. I know that is is a failing on my part but I prefer subtlety and suggestion to stating 'this is how it is', apart from anything, I could be wrong. :0)