是`std :: vector <primitive> :: clear（）`常量時間操作嗎？

在矢量上調用clear()將調用存儲在矢量中的任何析構函數，這是一個線性時間操作。但是，當矢量包含基本類型如int或double時，情況如何？是`std :: vector <primitive> :: clear（）`常量時間操作嗎？

來源

2013-02-20 user2020792

（或不變，除非它是不是比線性多，這並不重要）可能的重複[什麼是std :: vector :: clear（）是什麼時候T是一個基本類型？]（http://stackoverflow.com/questions/11235975/what-is-the-complexity-of- stdvectortclear-when-t-a-a-primitive-type） – nneonneo 2013-02-20 02:14:12

[std :: vector :: clear，constant time？]的可能重複（http://stackoverflow.com/questions/14094302/stdvectorintclear-constant-time ） – jogojapan 2013-02-20 02:15:18

從可能實施vector的POV中考慮這一點。當您調用時：

delete [] internalPtr;

會發生什麼情況？

堆必須回收的空間相鄰塊
析構函數必須解僱或internalPtr

前者，則仍必須爲基本類型的每個對象，但是析構函數不爲他們存在。所以delete[]將執行堆上如何快速刪除的記憶

來源

2013-02-20 00:45:37

至少使用默認分配器，'std :: vector'不會使用'delete [] internalPtr;'。 – 2013-02-20 00:50:10

塊在這個鏈接完全基於：

http://www.cplusplus.com/reference/vector/vector/clear/

它說的clear()複雜的大小（殘害）線性。

來源

2013-02-20 00:52:05 Barney

我不能在C++ 11標準中找到任何支持它的東西。鏈接可能是錯誤的。 – juanchopanza 2013-02-20 00:59:04

我相信答案是依賴於實現的。線性時間最多需要，但有些實現可能會選擇優化此操作。

根據'Does clearing a vector affect its capacity?'，即使調用.clear，MSVC和G ++都不會降低其向量的容量。看看G ++頭文件，只要元素是標量（基本算術類型或指針），顯然.clear與默認分配器是恆定時間的。

來源

2013-02-20 00:58:03 nneonneo

這似乎與標準中找不到有關'vector :: clear（）'（或順序容器'clear（）'）的事實一致。當然，這可能歸咎於我沒有正確搜索...... – juanchopanza 2013-02-20 01:09:37

@juanchopanza：我看了規範，它確實似乎[缺少]（http://stackoverflow.com/questions/14970747/is-the-complexity-of-vectorclear-未指定）。但請注意，指定'erase（begin（），end（））'需要的時間等於調用每個析構函數所需的時間量。 – nneonneo 2013-02-20 01:27:36

嗯..它說清楚了（）是線性的，但我們也知道，它要求每一個項目的析構函數...

http://www.cplusplus.com/reference/vector/vector/clear/

如果析構函數調用IST不是線性的是什麼？

然而，在原語的析構函數調用是線性

所以是的，在原語是明確的（）總是線性操作

來源

2013-02-20 00:59:18 cIph3r

OP特別詢問了具有微不足道的析構函數的基元。 – nneonneo 2013-02-20 01:00:06

它說它是線性的？我在C++ 11標準的任何地方都找不到它，但我可能會錯過一些東西。 – juanchopanza 2013-02-20 01:00:06

@juanchopanza和nneonneo固定 – cIph3r 2013-02-20 01:04:31

是`std :: vector <primitive> :: clear（）`常量時間操作嗎？

回答

相關問題