C++ 中的向量是如何工作的

C++ 中的向量可以在添加更多元素时调整大小。它还允许删除元素。

下面是当数组充满时，用户希望添加项的一个非常基本的想法。

1）在堆内存上创建一个更大的内存（例如双倍大小的内存）。

2）将当前内存元素复制到新内存中。

3）现在添加了新项目，因为现在有更大的内存可用。

4）删除旧内存。

但是实际的库实现可能更加复杂。如果我们每当当前数组变满（或即将变满）时创建一个新的双倍大小数组，并将当前元素复制到新的双倍大小数组中，则可以获得摊销时间复杂度为 O（1）。因此，特定的插入操作可能很昂贵，但总体时间复杂度仍为O（1）。请参见算法分析 | 第 5 集（分摊分析介绍）以获得证明。因此，push_back（）的时间复杂度为 O（1）。

// CPP program to illustrate push_back()
#include <iostream>
#include <vector>
using namespace std;
  
int main()
{
    vector<int> myvector{ 1, 2, 3, 4, 5 };
 
    myvector.push_back(6);
  
    // Vector becomes 1, 2, 3, 4, 5, 6
  
    for (auto x : myvector)
        cout << x << " ";
}

输出：

1 2 3 4 5 6

向量中 erase（）的时间复杂度是什么？
由于擦除元素需要移动其他元素（以确保随机访问），擦除的时间复杂度为O（n）。

// CPP program to illustrate
// working of erase() function
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    vector<int> myvector{ 1, 2, 3, 4, 5 };
 
    auto it = myvector.begin();
    myvector.erase(it);
 
    // Printing the Vector
    for (auto x : myvector)
        cout << x << " ";
    return 0;
}