time complexity of vector and array

I don't think you understand what "time complexity" means.
Vectors have the same complexity as arrays: O(1). That is, accessing any element takes always the same time regardless of previous conditions and element being accessed.

However, accessing a vector's elements using the overloaded operator[]() carries a small overhead for bounds checking. IIRC, the last time I benchmarked it, the overhead was 1-10% in relation to using an array with no bounds checking.

Helios, what do you mean by bounds checking? the vector's operator[] isn't supposed to do any bounds checking. That is what the member function "at" does. Am I misunderstanding you?

ok fine if vectors take same time in accessing elements(leave apart that overhead) but what about push_back operation.
will it take same time like that of simply assingning values (a[i]=n)
@computerquip in which sense arrays are slower than vector i mean how can you say arrays are slower?
well i am working on v.size() around 10^5

Use the reserve member functions so that memory reallocations aren't being done when you call push_back (at least not until the vector runs out of memory). Even if you know how much memory you need using vectors is advantageous if you learn how to make it work more efficiently for you. One advantage is that the vector provides more options for accessing elements. If you want bound checking during accesses, use the "at" member function. If you don't, use operator[]. If you allocate the memory upfront and perform tasks such as accessing elements or inserting at the end of the container, there shouldn't be any noticable performance degradation plus you get the added benefit of having an object oriented array that provides a convenient user interface that C arrays just don't have.

@gameon: why don't you write some example functions that use arrays and another that uses vectors. Perform similar operations while allowing a timer to count clock ticks. You can profile the functions yourself and identify what types of performance challenges are presented by a vector. By the way, the vector would have to be extraordinarly slow for it to make a noticeable difference. The thing that you should be concerned with most is memory reallocation. Using push_back without having reserved memory can result in a lot of reallocations where the entire block of data has to be copied to another and subsequently destroyed because vectors guarantee contiguous arrays internally. This happens when you use push_back or insert after the vector has already reached its capacity.

jRaskell (347)

well i am working on v.size() around 10^5

While a million elements may, on the surface, sound like a lot of data to work with, the reality is, in the eyes of a multi-gigahertz cpu, it's not a lot of data at all.

That being said, the next question would be what, in general, are you doing with all that data? As my first post said, if you are only trivially accessing it (as in say, doing a simple sort), then you may see some increase in performance going to an array, as helios said, 10% or less, and that's whether reading or writing (likely a combination of both).

On the other hand, if you're performing some non-trivial calculations on all that data as well, say processing some analog input data, morphing some image data, etc, then these calculations are going to represent the bulk of the cpu usage, and access time becomes trivial, which will then make the difference between using vector or array beyond trivial.

std::vector::operator[]() calls std::vector::at() (or viceversa). There's no difference between the two functions.

I found that the bigger an object gets, the more benefit there is in using a vector over an array. If the objects are too small or even primitives, it means that iterating over a vector may come to use more time accessing elements than performing operations, as smaller types are faster. I wrote a bit about this a couple days ago: http://www.cplusplus.com/forum/lounge/11434/
If you need to perform very fast operations on many (10^6-10^7 or more) elements, it will probably be faster to do something like this:

1
2

T *array=&vector[0];
for (unsigned a=0,size=vector.size();a<size;a++){/*...*/}

That combines the sizefulness of vectors with the overheadlessness of arrays.
If the size of the vector is not expected to reach the million mark or the elements are non-integrals or non-primitives, just using operator[]() will do, since each operation is likely to be long enough to make the bounds checking insignificant.

TL;DR: Use operator[]() whenever possible, as it prevents those nasty buffer overflows. If you're in serious need of speed over safety, access the underlying array directly.

Last edited on

std::vector::operator[]() calls std::vector::at() (or viceversa). There's no difference between the two functions.

There is according to this website. Where did you get this information? I looked at my compilers implementation of operator[] and at and neither does what you are saying. They both do this

return (*(begin() + _Pos));

with the exception that there is an extra if statement in the at member function to test the range.

jsmith (5804)

Yes. According to the specification of vector, operator[] is supposed to mimic array access (ie, no bounds check) whereas at() throws if the index is out of range. Therefore at() is slower than operator[] in a compliant implementation.

You should not really see any difference at all between vector and arrays given an algorithm, [i]provided that you implement the vector-based version in the same way as the array-based version[i]. A lot of people don't do that. They think that

1
2
3

int a[ 10 ];
for( int z = 0; z < 10; ++z )
    a[ z ] = z;

is the same as

1
2
3

vector<int> a;
for( int z = 0; z < 10; ++z )
   a.push_back( z );

whereas in fact they aren't even close. The end result is the same, but algorithmically speaking they are as different as they can get.

I guess I was wrong, then. That would explain why the overhead was so small.

after all these expert comments, we can say that its better to use std::vector::operator[]() hence specifying the size during declaration itself to avoid bound checks while dealing with large input (large size of vector) while for small input its better to use arrays as said by halios.
so in any case std::vector::at() will be expensive and will be used only when input is given at runtime(i.e. we don't know the no. of input).

jsmith (5804)

So having said all that, one of vector's benefits over arrays is also one of its detriments: it likes to default construct elements.

That means that not even

vector<int> v( 10 );

is equivalent to

int* pv = static_cast<int*>( malloc( 10 * sizeof int ) );

since vector's constructor will initialize all 10 elements to zero whereas the malloc will not.
(calloc is the closest equivalent; it will initialize to zero).

and vector<> cannot be made equivalent in any way to the stack declaration:

int a[ 10 ];

since vector requires dynamic memory allocation which is inherently more expensive than
allocating stack space.

The closest equivalent to a stack-based array is therefore boost::array<>, which does not
dynamically allocate memory nor does it initialize any elements.

Anyway, academic exercise.

But I have to disagree with you, GameOn, because for small input, any performance difference between vector and array will be less than for large input. It would therefore make more sense to do the converse of what you suggested. However, see above discussion.

I think he must have confused the two while typing and actually meant to write it the other way around. That happens to me, sometimes.

I think he must have confused the two while typing and actually meant to write it the other way around. That happens to me, sometimes.