c++ - 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）操作，如果可能的话，这会更快。

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

标签： c++vectordynamic-arrays

Answer 1

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

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