c++ - 方法 vector::push_back 的 new/alloc 的复杂性

Question

对于巨大的 N 值，下面代码的 alloc(realloc)/new 操作的复杂度是多少。

据我了解 push_back 分配内存:
大小 = cst*old_size;
cst = 2;//对于 gcc
所以我们在 k 循环内有 O(1)，在 i 循环内有 ~O(N)。总之我有 O(N)，对吗？

std::vector<int> data;  
for (int i = 0; i < N; ++i)  
{  
    for (int k = 0; k < 2 * N; ++k)  
        data.push_back(k);  
    for (int k = 0; k < N; ++k)  
        data.pop_back();  
}  

Answer 1

---

vector::push_back 不完全是 O(1)，而是 C++ 标准要求的 amortized O(1)。参见 Constant Amortized Time