2

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

これは学習目的で行われるため、使用できませんstd::vector。

4

4 に答える 4

5

出発点は次のとおりです。必要なのは、3 つの変数 とnelems、capacity実際の配列へのポインターだけです。したがって、クラスは次のように始まります

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

どこTに保存したいデータのタイプです。追加のクレジットとして、これをテンプレート クラスにしてください。ここで、教科書またはウィキペディアの動的配列に関するページで説明されているアルゴリズムを実装します。

new/delete割り当てメカニズムは、C のように配列の拡張をサポートしていないことに注意してください。そのreallocため、実際にはdata、容量を拡張するときに の内容を移動することになります。

于 2012-01-17T13:57:20.760 に答える
3

この機会を利用して、興味深いがやや難しいトピックである例外に興味を持っていただきたいと思います。

  • 自分でメモリの割り当てを開始し、その後生のポインタで遊んでいると、メモリリークを回避するという困難な状況に陥ることになります。
  • メモリの簿記を適切なクラス（たとえば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-17T14:53:04.053 に答える
2

要素を追加するにつれて動的に成長する配列は、動的配列、拡張可能配列と呼ばれ、動的配列の完全な実装です。

于 2012-01-17T14:37:02.783 に答える
0

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-17T14:04:41.603 に答える