在C++中實現增量數組

我想實現一個可以隨着新值添加而遞增的數組。就像在Java中一樣。我不知道如何做到這一點。任何人都可以給我一個方法嗎？在C++中實現增量數組

這是爲了學習的目的，因此我不能使用std::vector。

來源

2012-01-17 Jayanga Kaushalya

+19

使用'std :: vector'，不要重新發明輪子。 [除非你爲了學習而實現它] – amit 2012-01-17 13:49:06

Yeap，即使你爲了學習而實現它，在開始之前也要研究'std :: vector'是如何工作的。 – sharptooth 2012-01-17 13:52:41

@amit是的我正在做這個學習的目的。謝謝。 – 2012-01-17 13:53:33

我想借此機會感興趣的是一個有趣但有些困難的話題：例外。

如果您自己開始分配內存，然後使用原始指針玩，您會發現自己處於避免內存泄漏的困難位置。
即使您將內存的記錄委託給正確的類（例如std::unique_ptr<char[]>），仍然必須確保在對象失敗時，更改對象的操作會使其保持一致的狀態。

例如，下面是一個簡單的類與不正確resize方法（這是大多數代碼的心臟）：

template <typename T> 
class DynamicArray { 
public: 
    // Constructor 
    DynamicArray(): size(0), capacity(0), buffer(0) {} 

    // Destructor 
    ~DynamicArray() { 
    if (buffer == 0) { return; } 

    for(size_t i = 0; i != size; ++i) { 
     T* t = buffer + i; 
     t->~T(); 
    } 

    free(buffer); // using delete[] would require all objects to be built 
    } 

private: 
    size_t size; 
    size_t capacity; 
    T* buffer; 
};

好了，所以這是比較容易的部分（儘管已經是有點棘手）。

現在，你如何在最後推新元素？

template <typename T> 
void DynamicArray<T>::resize(size_t n) { 
    // The *easy* case 
    if (n <= size) { 
    for (; n < size; ++n) { 
     (buffer + n)->~T(); 
    } 
    size = n; 
    return; 
    } 

    // The *hard* case 

    // new size 
    size_t const oldsize = size; 
    size = n; 

    // new capacity 
    if (capacity == 0) { capacity = 1; } 
    while (capacity < n) { capacity *= 2; } 

    // new buffer (copied) 
    try { 

    T* newbuffer = (T*)malloc(capacity*sizeof(T)); 

    // copy 
    for (size_t i = 0; i != oldsize; ++i) { 
     new (newbuffer + i) T(*(buffer + i)); 
    } 

    free(buffer) 
    buffer = newbuffer; 

    } catch(...) { 
    free(newbuffer); 
    throw; 
    } 
}

感覺沒錯？

我的意思是，我們甚至考慮到T的拷貝構造函數引發的可能異常！是啊！

請注意我們的微妙問題：如果拋出異常，我們更改了size和capacity成員，但仍舊有buffer。

當然修復是顯而易見的：我們應該先改變緩衝區，然後改變緩衝區的大小和容量。當然...

但是，要讓它正確是「困難的」。

我建議使用另一種方法：創建一個不可變的數組類（容量應該是不可變，而不是靜止的）和實施例外少swap方法。

然後，您將可以更輕鬆地實現「類似事務」的語義。

來源

2012-01-17 14:53:04

我剛剛意識到我掩蓋了另一個細節：如果引發異常，則有必要正確銷燬新複製的元素。 – 2012-02-06 07:14:09

這將是一個很好的起點：http://www.cplusplus.com/reference/stl/vector/

，必須從貓加上加

來源

2012-01-17 13:50:23 Azodious

建議[cppreference]（http://en.cppreference.com/w/cpp）給cplusplus.com。 – 2012-01-17 13:52:13

@CatPlusPlus：我也傾向於使用cplusplus.com。 cppreference是否更好地維護？ – 2012-01-17 13:52:57

@larsmans：cplusplus.com未針對C++ 11進行更新，並且有錯誤記錄。 – 2012-01-17 13:54:09

閱讀評論我覺得here你會發現所有你想要的。

來源

2012-01-17 13:53:33 shift66

一個鏈接是不是一個答案.... – aProgrammer 2012-01-17 13:55:28

我不'我認爲這個問題值得更多。 – shift66 2012-01-17 13:57:51

這裏有一個出發點：你只需要三個變量，nelems,capacity和一個指向實際數組的指針。所以，你的類將開始爲

class dyn_array 
{ 
    T *data; 
    size_t nelems, capacity; 
};

其中T是要存儲的數據類型;爲了獲得額外的榮譽，請將其作爲模板課程。現在實施您的教科書或Wikipedia page on dynamic arrays中討論的算法。

注意，new/delete分配機制不支持日益增長的像C的realloc做一個數組，所以你成長的能力時，其實是可以四處移動data的內容。

來源

2012-01-17 13:57:20

在C和C++數組中，表示法基本上只是短手指針數學。所以在這個例子中。

int fib [] = { 1, 1, 2, 3, 5, 8, 13};

此：

int position5 = fib[5];

是同樣的事情，這樣說：

int position5 = int(char*(fib)) + (5 * sizeof(int));

所以基本上數組只是指針。

所以如果你想自動分配，你將需要編寫一些包裝函數來調用malloc（）或new（分別爲C和C++）。

雖然你可能會發現向量是你在找什麼...

來源

2012-01-17 14:04:41

數組是___不是指針！ http://stackoverflow.com/q/4810664/140719 – sbi 2012-01-17 14:29:55

我們添加元素被稱爲動態數組，可增長的陣列，動態的成長，這裏是一個dynamic array的完整實現的數組。

來源

2012-01-17 14:37:02 Sadanand

在C++中實現增量數組

回答

相關問題