如何在C++中實現矢量

我在想如何從頭開始實現std :: vector。如何在C++中實現矢量

它如何調整矢量大小？

realloc似乎只適用於普通的舊工作，或者我錯了嗎？

2010-06-17 John Smith

realloc只能在堆上分配字節。它不知道任何數據類型。如果您想使用它，請查看http://stackoverflow.com/questions/827552/explicitly-calling-a-constructor-in-c以查看如何初始化存儲的數據。 – 2010-06-17 18:55:33

+21

爲什麼倒票？我知道傳統觀點認爲「不要重新發明輪子」，但是想要知道某件事在內部是如何工作的也不是壞事。 – 2010-06-17 18:59:21

它是一個簡單的模板類，它包裝了一個本地數組。它不是使用malloc/realloc。相反，它使用傳遞的分配器（默認爲std::allocator）。

調整大小是通過分配一個新的數組，並從舊的數組中複製構造新數組中的每個元素來完成的（這樣對於非POD對象來說是安全的）。爲了避免頻繁分配，他們通常會遵循非線性增長模式。

更新：在C++ 11中，如果存儲類型可能會移動元素而不是構建副本。

除此之外，它將需要存儲當前的「大小」和「容量」。大小是向量中實際有多少元素。容量是多少個可能在向量中。

所以，作爲一個起點，一個載體將需要在一定程度上是這樣的：

template <class T, class A = std::allocator<T> > 
class vector { 
public: 
    // public member functions 
private: 
    T*     data_; 
    typename A::size_type capacity_; 
    typename A::size_type size_; 
    A      allocator_; 
};

的另一個常見的實現是存儲指向數組的不同部分。這樣做的代價是end()（不再需要增加）的代價，只需要稍微昂貴的size()調用（現在需要減法）。在這種情況下，它可能是這樣的：

template <class T, class A = std::allocator<T> > 
class vector { 
public: 
    // public member functions 
private: 
    T* data_;   // points to first element 
    T* end_capacity_; // points to one past internal storage 
    T* end_;   // points to one past last element 
    A allocator_; 
};

我相信，海灣合作委員會的libstdC++做到這一點，這兩種方法同樣有效，符合。

來源

2010-06-17 18:44:09

那麼這是否意味着在調整時間暫時分配的內存加倍？ – 2010-06-17 20:14:53

是的，在調整大小的過程中，有一段時間新的內存已被分配，但舊內存尚未被釋放。 – 2010-06-17 21:17:31

是的，在我使用帶有千兆字節數據的矢量並且沒有內存的情況下，我有點受傷。 – 2014-08-15 23:27:03

它分配一個新的數組並複製一切。所以，如果你經常這樣做，擴展它是非常低效的。如果必須使用push_back（），請使用reserve（）。

來源

2010-06-17 18:44:07 Macke

挑剔，它複製構建一切=） – 2010-06-17 18:50:07

而現在，它的動作！ :) – Macke 2014-12-28 15:35:55

是的未來我精彩:) – 2015-01-05 11:01:45

-5

realloc只適用於堆內存。在C++中，您通常要使用免費商店。

來源

2010-06-17 18:44:31

「免費商店」？你是什麼意思？ – 2010-06-17 18:48:31

http://www.gotw.ca/gotw/009.htm – 2010-06-17 18:55:34

FWIW，沒有什麼說你不能使用堆做免費商店。 – 2010-06-17 19:38:05

從Wikipedia，這是一個很好的答案。

一個典型矢量實現由在內部，一個指針到動態分配的數組，[2]和可能的數據成員保持向量的容量和尺寸。向量的大小是指元素的實際數量，而容量是指內部數組的大小。當插入新元素時，如果矢量的新大小變得大於其容量，則會發生重新分配 [2] [4]。這通常會導致向量分配一個新的存儲區域，將以前保存的元素移動到存儲區域的新區域，並釋放舊區域。由於元素的地址在此過程中發生更改，因此向量中元素的任何引用或迭代器都將失效。[5]使用被無效引用導致未定義的行爲

來源

2010-06-17 18:44:56 Serapth

調整大小的矢量需要分配的空間的新塊時，和現有的數據複製到新的空間（因此，該物品放置到載體可以是要求複製）。

注意其不使用new []要麼 - 它使用則傳遞分配器，但是這需要分配生內存，不是對象的數組一樣new []一樣。然後您需要使用placement new來構建適當的對象。 [編輯：好吧，你可以在技術上使用new char[size]，並使用它作爲原始內存，但我無法想象任何人寫這樣的分配器。]

噹噹前分配用盡並且新的內存塊需要與舊尺寸相比，尺寸必須增加因子以滿足push_back的分攤恆定複雜度的要求。雖然許多網站（以及其他網站）稱這種尺寸翻了一番，但大約1.5到1.6的因子通常效果更好。特別是，這通常會提高重新使用釋放塊以備未來分配的機會。

來源

2010-06-17 18:47:49

需要注意的是''realloc''可能有OS的高級支持，因爲它不僅僅是一個普通的'malloc/free'（例如參見Windows上的HeapReAlloc'），並且符合的'vector'實現可以使用例如。類型特徵來檢測類型是否是POD，並且在這種情況下使用'malloc/realloc/free'而不是'new/delete'。 – 2010-06-17 23:14:20

像這樣： https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h

（在github GCC官方鏡像）

來源

2010-06-17 18:49:38 log0

鏈接已經壞了，唉。 – 2014-08-05 21:30:16

更新了鏈接 – log0 2014-08-15 22:41:31

你需要確定你的意思是「普通老式結構。」

realloc本身只創建一個未初始化的內存塊。它沒有對象分配。對於C結構來說，這足夠了，但對於C++來說則不行。

這並不是說你不能使用realloc。但如果你使用它（！注意你不會被重新實現std::vector正是在這種情況下），你需要：

確保您始終使用malloc/realloc/free整個類。
使用「placement new」初始化內存塊中的對象。
在釋放內存塊之前，顯式調用析構函數來清理對象。

這實際上是非常接近到什麼矢量確實在我的實現（GCC /油嘴），只不過它採用C++低級例程::operator new和::operator delete做原始內存管理，而不是malloc和free，改寫使用這些原語的realloc例程，並將所有這些行爲委託給可以用自定義實現替換的分配器對象。

由於vector是一個模板，實際上你應該有它的源代碼來看看你是否需要引用 - 如果你可以通過下劃線的優勢，它不應該太難閱讀。如果您在使用GCC的Unix機器上，請嘗試尋找/usr/include/c++/version/vector或其附近。

來源

2010-06-17 19:22:08

如何在C++中實現矢量

回答

相關問題