std :: vector <T> :: clear（）是什麼時候T是一個原始類型？

Question

我知道clear（）操作的複雜性在容器的大小上是線性的，因爲必須調用析構函數。但是原始類型（和POD）呢？看起來最好的做法是將矢量大小設置爲0，以便複雜度保持不變。

如果這是可能的，std :: unordered_map也可能嗎？

Answer 1

gcc的版本std::_Destroy，這是最終由clear()，試圖模板上的類型是否有一個平凡的析構函數，所以在這種情況下，複雜性是恆定的，即使沒有一個優化過程。但是我不知道模板的工作情況。

Answer 2

看起來最好的做法是將矢量大小設置爲0，以便複雜度不變。

通常，的resizing a vector to zero複雜度是在當前存儲在vector元件的數量線性。因此，將vector的大小設置爲零與呼叫clear()沒有任何優勢 - 兩者基本相同。

但是，至少有一個實現（libstdC++，源碼bits/stl_vector.h）通過採用部分模板特化爲您提供原始類型的O（1）複雜性。

的clear()實施導航其方式在bits/stl_construct.h的std::_Destroy(from, to)功能，其執行一個非平凡編譯時優化：它聲明一個輔助模板類_Destroy_aux與bool類型的模板的參數。該班有部分專業爲true和顯式專業化爲false。這兩個專業化定義了一個稱爲__destroy的靜態函數。如果模板參數爲true，則函數體爲空;如果參數是false，則body contains a loop invoking T's destructor通過調用std::_Destroy(ptr)。

訣竅來自於line 126：

std::_Destroy_aux<__has_trivial_destructor(_Value_type)>:: 
__destroy(__first, __last); 

輔助類是基於__has_trivial_destructor檢查的結果實例化。對於內置類型，檢查器返回true，對於具有非平凡析構函數的類型，檢查器返回false。因此，撥打__destroy成爲int,double和其他POD類型的禁用。

的std::unordered_map距離vector不同，它可能需要刪除表示POD對象的「散列桶」的結構，而不是刪除對象本身^*。 clear到O(1)的優化是可能的，但它很大程度上依賴於實現，所以我不會指望它。基於開放尋址（線性探測，探測二次等）可能能夠刪除所有水桶O(1)實施collision resolution哈希表;：

---

^*確切的答案取決於實施但是，基於單獨鏈接的實現將不得不一個一個地刪除存儲桶。