C++でインクリメンタル配列を実装する

Question

新しい値が追加されるとインクリメントできる配列を実装したいと思います。 Javaと同じように。私はこれをどうやって行うのか分かりません。誰か私に方法を与えることができますか？

これは学習目的で行われるため、std::vectorは使用できません。私はあなたが欲しいすべてを見つけることができますhere考えるhttp://www.cplusplus.com/reference/stl/vector/

とキャットプラスプラスから

Answer 1

私は興味深いがやや難しいトピック、つまり例外についてお話したいと思います。

• メモリを自分で割り当ててから、生ポインタで再生すると、メモリリークを回避するのが難しい状況に陥ります。
• 正しいクラス（たとえば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メソッドを実装します。

次に、「トランザクションのような」セマンティクスをはるかに簡単に実装できます。

Answer 2

これは良い出発点になります。

Answer 3

コメントを読まなければならない：

Answer 4

ここに出発点があります：nelems、capacityの3つの変数と実際の配列へのポインタが必要です。だから、あなたのクラスはTは、保存したいデータの種類がある

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

として始めるでしょう。クレジットを追加するには、これをテンプレートクラスにします。今あなたの教科書またはWikipedia page on dynamic arraysで議論されたアルゴリズムを実装してください。 new/delete割り当てメカニズムは、Cのreallocないような配列の成長をサポートしていませんので、容量を成長させる際、あなたが実際に周りdataの内容を移動することがありますことを

は

注意。

Answer 5

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++）を呼び出すためのラッパー関数を記述する必要があります。

あなたはベクトルはあなたが

Answer 6

我々は動的配列、可変長配列と呼ばれる要素を追加すると、動的に成長し、ここでdynamic arrayの完全な実装である配列...探しているものです見つけるかもしれませんが。