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?
A:
Pointer arithmetic is constant - it's usually a single multiplication and addition to base. [] is a kind of pointer arithmetic as well.
MaxVT
2010-03-31 15:11:20
+8
A:
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.
GMan
2010-03-31 15:11:34
Silly question - constant time for total operation ? So would (pObj + 1) and (pObj + 10) take the same amount of time?
Konrad
2010-03-31 15:25:42
@Konrad Yes - pointer arithmetic is just arithmetic, 1 + 1 takes the same time as 1 + 10.
anon
2010-03-31 15:28:01
Thank you, I thought so but was having a brain fail moment. Thanks!
Konrad
2010-03-31 15:32:41
Just an observation. Not only is the performance of operator[] the same for vector as it is for plain types, it is the same for the same reason. `vector` implements the data store as a C-style array.
John Dibling
2010-03-31 15:39:10
+2
A:
A vector is effectively a wrapper around an array, so they should both provide the same performance guarantees.
anon
2010-03-31 15:12:37