CODEWITHSUNDEEP
c++arraysstl
Konrad
Konrad

Reputation: 41027

Array performance question

I am very familiar with STL vector (and other container) performance guarantees, however I can't seem to find anything concrete about plain arrays.

Are pointer arithmetic and [] methods constant or linear time?

Upvotes: 1

Views: 178

Answers (3)

anon
anon

Reputation:

A vector is effectively a wrapper around an array, so they should both provide the same performance guarantees.

Upvotes: 2

GManNickG
GManNickG

Reputation: 504313

They are constant time. (Same as vector.)

When you say a[b], it becomes *(a + b). Both (pointer arithmetic) addition and dereferencing are constant time.

When adding an integer to a pointer, it moves that many elements over:

T* p; size_t i;

T* q = p + i; // same as:
T* q = reinterpret_cast<T*>(reinterpret_cast<char*>(p) + i * sizeof(T));

Every operation in there is constant time.

Upvotes: 9

MaxVT
MaxVT

Reputation: 13244

Pointer arithmetic is constant - it's usually a single multiplication and addition to base. [] is a kind of pointer arithmetic as well.

Upvotes: 0

Related Questions