std::vector::~vector的时间复杂度是多少？原生动态数组效率更高吗？

核心结论 #

你的理解存在偏差，原生动态数组并不会比std::vector<Node*>在该场景下有更高的运行效率，二者的销毁开销完全一致。

具体原因解释 #

• 首先你对std::vector析构逻辑的理解有误：cppreference的描述是通用规则，仅当元素为非平凡可析构类型（存在自定义析构函数、且编译器无法优化掉析构逻辑的类型）时，才会逐个遍历元素调用析构函数。
• Node*属于指针类型，是标准的平凡可析构类型，它的析构函数没有任何实际执行逻辑，也不存在任何副作用。主流STL实现都会通过类型萃取（type traits）判断出这一点，直接跳过逐个调用析构函数的步骤，直接释放底层的整块内存，这一过程和你直接对原生动态数组执行delete[]的开销完全没有区别，根本不会产生额外的O(n)遍历操作。
• 哪怕是在最极端的未优化场景下，编译器没有自动跳过平凡类型的析构遍历，遍历执行空析构函数的开销也可以忽略不计，和排序本身O(nlogn)的开销相比完全不在一个量级，根本不会成为性能瓶颈。

实践建议 #

该场景下更推荐使用std::vector而非原生动态数组：

• 无需手动管理内存分配、释放逻辑，不会出现内存泄漏、野指针等问题
• 大部分STL实现的std::vector在Debug模式下自带边界检查，更方便开发阶段定位越界问题
• Release优化模式下，std::vector的读写、销毁性能和原生动态数组完全一致，部分场景下因为STL分配器的优化反而会有更好的性能表现

内容的提问来源于stack exchange，提问作者James Newman