STL向量的實現

我在想如何實現STL std::vector。STL向量的實現

確切地說，STL向量是否保存一個對象表或者指向對象的表？

實際執行過程中：最好是std::vector<char>的大小約爲10^8，或者有一個char的數組？

第一個選項有明顯的優點：像其他所有容器一樣迭代，已知大小，自動內存管理，很難做出真正錯誤的事情。

第二個選項可能使用的空間減少了9倍（指針是64位，其中char是8位），但代價是上面列出的所有舒適方法。

我看着 /usr/include/c++/4.8.2/bits/stl_vector.h ，看見push_back()是如下實施，但即使檢查alloc_traits.h讓我不知道它是如何真正做。

類型char僅用於顯示與所保持的值大小相比，指針的大小顯着。

我正在使用C++ 11。

void 
push_back(const value_type& __x) 
{ 
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) 
    { 
     _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 
            __x); 
     ++this->_M_impl._M_finish; 
    } 
    else 
#if __cplusplus >= 201103L 
    _M_emplace_back_aux(__x); 
#else 
    _M_insert_aux(end(), __x); 
#endif 
}

來源

2013-12-12 styrofoam fly

不，不持有指針的元素。具有10^8個元素的「矢量」將具有可忽略的簿記足跡。 –

一個矢量管理單個連續的對象數組，因此它不需要指向每個元素的指針。它僅需要：

一個指針，指向標記陣列
的指針（或索引）標記所使用的元件的端部（即，大小）
的指針（或索引）的開始分配的存儲結束（即容量）

（它也需要存儲的分配，但通常情況下，這是無狀態的，和一個體面的實現將使用「空基類優化」，以確保它佔用在這種情況下，沒有空格）。

如果你管理自己的動態數組，你將需要至少兩種的;所以使用矢量的額外成本是單個指針。

如果你不需要動態分配，那麼自動數組（或者std::array，如果你想要更多的STLy）會更有效率：它不會涉及任何堆分配或任何額外的存儲。但是，只有在編譯時已知大小的情況下才有可能，並且存在大型數組可能溢出堆棧的危險。

來源

2013-12-12 15:50:46

std :: vector保存一個連續的存儲塊，動態（重新）分配。認爲它，如果它是：

struct vector { size_t size, capacity; void *data; };

來源

2013-12-12 15:48:49 chill

它並不真正保存「大小」，而是指向存儲結束的指針。 – Tobias

@tobias：它如何表示大小取決於實現。 –

std::vector<T>保持在保證連續的緩衝區T類型的對象的一個序列。

就問題

具體實現：這是最好有標準::向量的規模大約是10^8，或有字符數組？

大小本身是無關緊要的。

但是，如果您將大數組char分配爲本地自動變量，那麼您的堆棧空間很可能會用完，並且會出現非定義行爲。您可以通過動態分配數組來避免這種情況。一個合理的方法是使用std::string（或std::vector，但很可能這是一個字符串）。

來源

2013-12-12 15:50:38

STL向量的實現

回答

相關問題