可以deque內存分配稀疏嗎？

Question

由deque分配的標準允許以稀疏方式存儲內存嗎？

我的理解是，大多數實現deque內部分配一些大小的塊內存。我相信，雖然我不知道這個事實，但是實現至少分配了足夠的塊來存儲當前大小的所有項目。因此，如果一個區塊是100個物品，並且您做了

std::deque<int> foo; 
foo.resize(1010); 

您將至少分配11個區塊。然而，鑑於在上述所有1010 int是默認構造你真的需要在調整大小調用時分配塊嗎？您是否可以在某人以某種方式實際插入項目時分配給定的塊。例如，實現可以將一個塊標記爲「所有默認構造」，並且在有人使用它之前不分配它。

我問，因爲我有一種情況，我可能想要一個非常大的deque，在我最終使用的元素方面可能相當稀疏。很明顯，我可以使用其他數據結構（如地圖），但我對Deque的規​​則感興趣。

給定調整大小void resize (size_type sz, T c = T());簽名的相關問題是該標準是否要求默認構造函數恰好被調用sz次？如果答案是肯定的，那麼我猜你至少對於具有非平凡默認構造函數的類型不能進行稀疏分配，儘管假設對於內置類型（如int或double）仍然可能。

Answer 1

deque中的所有元素都必須正確構造。如果你需要 一個稀疏的實現，我會建議deque（或vector）到 指針或Maybe類（你真的應該有一個在你的工具箱 無論如何），它不會構造類型，直到它是有效的。這不是的作用。

Answer 2

回答你的第二個問題。有趣的是，C++ 03和C++ 11有所不同。

使用C++ 03，你的簽名

void resize (size_type sz, T c = T()); 

將默認構造參數（除非您提供另一值），然後副本從該值構建新成員。

在C++ 11，該功能已被取代的兩個重載

void resize(size_type sz); 

void resize(size_type sz, const T& c); 

其中第一個默認構建體（或值初始化）sz元件。

Answer 3

23.3.3.3指出deque::resize將追加sz - size()默認插入元件（sz是deque::resize第一個參數）。

默認插入（見23.2.1/13）意指元件由表達式allocator_traits<Allocator>::construct(m, p)（其中m是分配器和p待構造的類型的指針）初始化。所以內存必須可用，並且元素將被默認構建（初始化？）。

總而言之：deque::resize如果想要符合，就不能懶惰地構造對象。您可以輕鬆地將惰性構造添加到boost::optional或任何其他Maybe容器中。