std::vector::~vector 的时间复杂度是多少？

Question

所以我在争论是否在我正在制作的程序中使用动态数组Node*或std::vector<Node*>数组。该程序本质上是在链表（定制的）上测试 STL 排序，因此将 LL 中的每个 nodeptr 插入到一个数组（动态分配的数组或向量）中，然后对其调用 std::sort。因此，在对数组进行排序后移动 LL 的指针时，我最初使用一个向量来保存所有节点。但是我意识到一旦超出范围，向量就会通过 std::vector::~vector 被销毁。根据 cppreference，我认为这是 O(n) 时间：

std::vector::~vector() 析构向量。调用元素的析构函数并释放已使用的存储空间。请注意，如果元素是指针，则指向的对象不会被销毁。

我相信粗体部分表示 O(n) 时间。所以我想知道你是否可以分配一个动态数组来保存节点，然后在所有排序后删除该数组。（而使用 ~vector()，您将遍历列表两次；一次在排序期间，第二次在释放数组时）因为如果是这样，那么您将从代码中减去整个 O(n) 操作，如果可能的话，这会更快。

我在这里误解了，还是因此常规动态数组会更快？

Answer 1

是的，std::vector::~vector需要 O(n) 时间，但是delete[]ing 一个原始的动态分配数组也是如此。

任一数据结构都必须销毁其内容，而这样做的方法是运行每个项目的析构函数。当然，原始指针的析构函数是微不足道的，因此无论您使用哪个容器，都可能根本不会发出任何代码来销毁指针本身。