陣列性能問題

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

矢量實際上是一個數組的包裝，所以它們應該提供相同的性能保證。