2

我想实现一个可以随着新值的添加而增加的数组。就像在 Java 中一样。我不知道如何做到这一点。谁能给我一个方法？

这样做是为了学习目的，因此我不能使用std::vector.

4

4 回答 4

5

这是一个起点：您只需要三个变量 ,nelems和capacity一个指向实际数组的指针。因此，您的课程将从

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

T您要存储的数据类型在哪里；为了获得额外的荣誉，请将此作为模板类。现在实现您的教科书或动态数组的维基百科页面中讨论的算法。

请注意，new/delete分配机制不支持像 C 那样增加数组，因此在增加容量时realloc实际上会移动's 的内容。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我的意思是，我们甚至会处理由的复制构造函数引发的可能异常！是的！

请注意我们有一个微妙的问题：如果抛出异常，我们已经更改了sizeandcapacity成员，但仍然有旧的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 回答