STL容器插入元素和內存透視

這個問題是question的擴展我想了解元素是如何插入STL Container的。STL容器插入元素和內存透視

假設我有A object;，我想插入任何STL Container，我知道有處理內存的allocators的概念。但我不明白如何將實際對象複製到STL memory。因此，當我呼叫Container.insert時，我的object存儲在stack上STL如何創建此對象的副本並將此對象存儲到其存儲器中。

任何等價物C++代碼將會有幫助，其中模擬相同。

來源

2011-10-24 Avinash

@馬塞洛坎託斯，我明白它使用複製構造函數。但是以std :: map爲例，現在忘記了比較邏輯，當新節點實際添加到樹中時會發生什麼。 – Avinash

我不太確定你到底在問什麼......你關心的是對象是如何分配的或者將節點放在容器中的算法是什麼？分配器將用於獲取新節點的內存，並且將使用* placement-new *調用node的構造函數，構造函數將初始化其自己的數據結構，並且* copy-construct *其「T」數據成員。如果你擔心RB-Tree（或任何其他平衡二叉搜索樹的實現，我建議你谷歌或檢查維基百科） –

@DavidRodríguez - dribeas：我感興趣的是知道STL如何爲每個元素分配內存，其實我試圖找出在STL類 – Avinash

的方法並不複雜。基本上容器將從分配器獲得內存，然後執行復制構建（通過該內存的放置 - 新的）。該容器更容易看到的是vector：

void push_back(T const & value) { 
    ensure_enough_capacity(); 
    new (end_ptr++) T(value); 
}

凡ensure_enough_capacity()確定矢量是否有成長，做它，就是它最終會調用如果size()==capacity()時push_back被稱爲分配器。

複雜程度的下一個層次是list，其中每個節點都是獨立分配的，並且還有一些額外的信息需要管理。在這種情況下，代碼將類似於：

void push_back(T const& value) { 
    node* n = allocator::allocate(sizeof(node)); 
    new (n) node(value, x, y); 
}

凡x和y是適當的指針來初始化節點的next和last指針（通常是一個指向最後一個節點爲last和指針哨兵節點 - 無效結束 - 對於next），並假設此特定構造函數將copy-constructvalue然後修復所有引用的指針。

有序關聯容器具有管理平衡樹的額外複雜度，但方法是相同的：分配一個足以容納該值和額外信息的塊，然後使用放置 - 新建來構建節點。其餘的是數據結構的細節。

來源

2011-10-24 07:46:34

使用適當的複製構造函數（或者，也許，C++ 11中的移動構造函數）複製該對象。假設你已經預先分配的N個Foo對象的數組，並已經在它length對象，在std::vector代碼可能看起來像：

void std::vector<Foo>::push_back(const Foo& n) { 
    new(my_memory+length) Foo(n); 
    ++length; 
}

新後的括號表示「放置新的」，也就是說，在預先分配的存儲上調用新功能。

來源

2011-10-24 06:55:52 thiton

分配器的用法：謝謝，但這將如何與關聯容器一起工作，我知道它在內部實現爲RB-Tree，但現在在這種情況下，節點內存不會預先存儲，分配。 – Avinash

@Avinash：然後節點只使用Foo的拷貝構造函數。 – thiton

最的插入函數原型爲

void insert(const A& a);

隔空cost&是-essentially-傳遞一個值，而在正規的參數複製的方式。

容器 - 根據它們的工作方式 - 具有包含A的內部結構。例如，一個列表具有

struct node 
{ 
    A val; 
    node* next; 
    node* prev; 

    node(const A& a) :val(a), next(), perv() 
    { } 
};

插入，在這一點上不提多於

void insert(const A& a) 
{ 
    node* n = new(allocator.allocate()) node(a); 
    /*set next and prev accordingly to list functionality*/ 
}

參考通過節點傳入構造和提供給所述初始化爲節點的嵌入式A，這是它自己的拷貝構造函數。

注意allocator.allocate（）atually具有節點分配空間，而不僅僅是A.由於這個原因，名單內的分配情況將是typename Allocator::rebind<node>::other類型，其中Allocator是list第二個模板參數，即違約到std::allocator<A>。

來源

2011-10-24 07:00:10

在內存分配方面真正發生的是：_it使用傳入的分配器作爲allocator模板參數。

map<int , long , less<int> , myAllocator<pair<int, long> > > myMap;

無論你做什麼myAllocator做它的分配從（如果有的話）將被使用。這在技術上意味着您可以預先分配所有對（可能來自矢量）。這也意味着正在使用placement new，就像在向量情況下一樣，只有這樣，而不是一次連續的分配，您的分配將在多次分配時被調用。

這隻會導致其中容器不能保證的存儲是連續的（就像在向量的情況下），但是，它miht還是發生是連續的情況，由於你的分配器的實施

寫作分配器是一個高級主題，它已在

Modern C++ Design（A.Alexandrescu）得到了解決
Boost library
另請參閱EASTL（這是專爲（嵌入式）遊戲編程;在這樣的環境中，堆通常是「不存在」或禁止的;而且，在這方面表現是最重要的。 EASTL沒有附帶一個默認的分配。）
_{https://github.com/paulhodge/EASTL}

來源

2011-10-24 07:24:42 sehe

STL容器插入元素和內存透視

回答

相關問題