Vector 中的动态内存分配

Question

我对向量（STL - C++）中的内存分配有疑问。据我所知，每当向量的大小等于其容量时，其容量就会动态加倍。如果是这样的话，为什么分配是连续的呢？它如何仍然允许像数组一样使用 [] 访问运算符进行 O(1) 访问？谁能解释这种行为？（列表也有动态内存分配，但我们无法使用 [] 访问运算符访问其元素，向量怎么可能呢？）

#include<iostream>
#include<vector>
using namespace std;

int main() {
    // your code goes here
    vector<int> v;

    for(int i=0;i<10;i++){
        v.push_back(i);
        cout<<v.size()<<" "<<v.capacity()<<" "<<"\n";
    }

    return 0;
}

输出：

1 1
2 2
3 4
4
4 5
8 6
8 7
8 8 8
9 16
10 16

Answer 1

据我所知，每当向量的大小等于其容量时，其容量就会动态加倍。

它不需要像您的情况那样加倍，它是实现定义的。因此，如果您使用其他编译器，情况可能会有所不同。

如果是这样的话，为什么分配是连续的呢？

如果向量没有更多的连续内存可以分配，则向量必须将其数据移动到满足其大小要求的新连续内存块。旧块将被标记为空闲，以便其他人可以使用它。

它如何仍然允许像数组一样使用 [] 访问运算符进行 O(1) 访问？

因为事实之前说过，可以通过 the[] operator或 a进行访问pointer + offset。对数据的访问将是 O(1)。

List 也有动态内存分配，但我们无法使用 [] 访问运算符访问其元素，向量怎么可能呢？

列表（例如 std::list ）与std::vector完全不同。在 C++ std::list 的情况下，它保存带有数据的节点、指向下一个节点的指针和指向前一个节点的指针（双链表）。因此，您必须遍历列表才能获取所需的一个特定节点。向量的工作原理如上所述。