Вопрос о производительности массива

Question

Я очень хорошо знаком с гарантиями производительности вектора STL (и других контейнеров), однако я не могу найти ничего конкретного о простых массивах.

Арифметика указателя и методы [] - постоянное или линейное время?

Answer 1

Это постоянное время. (То же, что и vector.)

Когда вы говорите a[b], оно становится *(a + b). И (арифметика указателей) сложение и разыменование имеют постоянное время.

При добавлении целого числа к указателю он перемещает столько элементов на:

T* p; size_t i;

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

У каждой операции есть постоянное время.

Answer 2

Вектор фактически является оберткой вокруг массива, поэтому они оба должны обеспечивать одинаковые гарантии производительности.

Answer 3

Арифметика указателя постоянна - обычно это одиночное умножение и сложение с базой. [] также является своего рода арифметикой указателей.