是C++语句的大-O'delete [] Q;' O（1）或O（n）？

标题不言自明。非常容易的问题。我认为这是O（n），但是想在我明天的决赛之前进行核实。是C++语句的大-O'delete [] Q;' O（1）或O（n）？

2013-05-09 Ethan Barron

我给你一个提示：'std :: string ::〜string（）' – 2013-05-09 21:57:06

'Q'是什么类型？ – 2013-05-09 21:59:16

密切相关：http://stackoverflow.com/q/16420357/179910 – 2013-05-09 22:01:52

简短的答案是......它取决于。

如果Q是一个指向具有析构函数的对象数组的指针，那么delete[] Q将需要调用所有这些析构函数。这将调用O（n）析构函数，其中n是数组中元素的数量。另一方面，如果Q指向没有析构函数的对象数组（例如，int s或简单struct s），则不需要调用仅析O（1）次的析构函数。

现在请注意，这些析构函数不必每次都运行O（1）次。如果对象是，例如，std::vector对象，则每个析构函数都必须触发更多的释放。如果不知道更多关于这些对象的内容，我们可以说的是，如果有析构函数调用，如果析构函数不重要，将调用0个析构函数，否则调用O（n）析构函数。

但是这忽略了堆分配器如何工作的实现细节。解除分配一块内存可能需要O（log K）时间，其中K是分配块的总数，或者无论内存有多少块或可能需要花费O（1）次O（log log K）等等。不知道分配器是如何工作的，你实在不能确定。简而言之，如果您只关注清理对象的工作，然后再将块返回给内存分配器，则存在称为O（n）的析构函数，前提是存储的对象具有析构函数，否则调用0析构函数。这些析构函数可能需要很长时间才能完成。然后，将内存块重新引入内存分配器会花费自己的时间。

希望这会有所帮助！

来源

2013-05-09 21:59:34 templatetypedef

@Ethan巴伦现在把它写在一张干净的纸上。把它放在你的衬衫下。随着问题文件的发布，迅速采取行动，将问题文件下的论文放在衬衫下面。祝你好运。 – 2013-05-09 22:02:39

我想添加一些重要的东西，很多人会错过。数组包含的对象不需要*需要定义析构函数。重要的是析构函数（定义或默认）是*微不足道*。也就是说，如果一个类有一个'vector'作为成员，那么默认的析构函数是非平凡的，并且会运行，即使没有明确定义的析构函数 – Duncan 2013-05-10 02:06:01

@templatetypedef这是一个很好的答案，非常感谢。 – 2013-05-10 05:07:04

我同意它取决于，但让我们谈谈释放X字节的内存，而不用担心析构函数。

一些内存分配器为“小”（1到500字节）对象保留空闲列表。插入到列表是O（1）。如果所有线程都有一个空闲列表，则需要获取互斥锁。获取互斥锁通常涉及多达1000个“旋转”，然后可能是系统调用（这非常昂贵）。一些分配器使用线程本地存储器为每个线程提供空闲列表，因此它们不会获得互斥锁。

对于一个介质（500到60000字节）大小的对象，许多分配器将会阻塞合并。也就是说，他们检查相邻块是否也是空闲的，并且它们合并2或3个空闲块以形成1个更大的空闲块。合并是O（1），但它又需要获取互斥锁。

对于大块，某些分配器使用系统调用获取内存。所以释放内存也是一个系统调用。

来源

2013-05-09 22:12:59

是C++语句的大-O'delete [] Q;' O（1）或O（n）？

回答

相关问题