C++矢量/鏈接列表混合

在C++中是否有一個std容器，充當向量和鏈接列表之間的混合。我的意思是一個數據結構，它克服了std :: vector頻繁的重新分配開銷和潛在的過量內存分配，而是當結構用完空間時，它增加了一個指向下一個分配片段的指針，並且只有當片段數達到整個結構被拆分成連續的新塊，並且碎片的數量被設置爲0.C++矢量/鏈接列表混合

來源

2011-11-29 dtech

你看過'std :: deque'嗎？它是否符合您的要求？ – Asha

我認爲'std :: deque'可以這樣工作，但我不確定。 – Constantinius

@Constantinius我總是認爲'std :: deque'只是一種循環緩衝區，因此它的內存分配行爲與'std :: vector'類似。 –

std::deque是最接近你描述的標準容器。然而，這並不是，正如（例如，它幾乎必須是一個數組數組而不是數組列表，因爲後者不允許恆定時間元素訪問）。

根據您的實際要求，它可能已經足夠接近。

來源

2011-11-29 13:13:03 NPE

所以我基本上可以使用一個雙端隊列，只需添加我需要的代碼的幾行代碼就可以在達到特定級別的碎片時對其進行碎片整理。這個想法很自然地消除了內存跳躍和緩存未命中...... – dtech

如前所述，std::deque接近您的要求。我只是想在std::vector和std::deque之間加上這個比較，我發現它非常有幫助。 An In-Depth Study of the STL Deque Container

來源

2011-11-29 13:17:00 Mythli

C++矢量/鏈接列表混合

回答

相關問題