vector in C++

The standard \<vector> library provide methods for vector operations:
```
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4);
    v.insert(v.begin(), 0);
    v.pop_back();
    v.erase(v.begin()+1);
    for(auto &i:v) {
        cout << i << ",";
    } 
    cout << endl;  // 0,2,3
    
    vector<int> v2(10, 1);
    for(auto i = 0; i < v2.size(); i++) {
        cout << v2[i] << ",";
    }
    cout << endl; // 1,1,1,1,1,1,1,1,1,1,
    return 0;
}
```
C++ has std::vector and Java has ArrayList, and many other languages have their own form of dynamically allocated array. When a dynamic array runs out of space, it gets reallocated into a larger area and the old values are copied into the new array. A question central to the performance of such an array is how fast the array grows in size. If you always only grow large enough to fit the current push, you'll end up reallocating every time. So it makes sense to double the array size, or multiply it by say 1.5x. The reason we use 1.5x is that we want to be able to reuse older memory blocks, to take advantage of caching and avoid constantly making the OS give you more memory pages. The equation you'd solve to ensure that a subsequent allocation can re-use all prior blocks reduces to x<sup>n − 1</sup> − 1 = x<sup>n+ 1</sup>  − x<sup>n</sup>, whose solution approaches x = ϕ for large n. In practice n is finite and you'll want to be able to reusing the last few blocks every few allocations, and so 1.5 is great for ensuring that.
Home