Реализация инкрементного массива в C ++

Question

Я хочу реализовать массив, который может увеличиваться при добавлении новых значений.Так же, как в Java.Я понятия не имею, как это сделать.Кто-нибудь может дать мне способ?

Это сделано для целей обучения, поэтому я не могу использовать std::vector.

Answer 1

Вот отправная точка: вам нужны только три переменные, nelems, capacity и указатель на фактический массив.Итак, ваш класс начнется с

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

, где T - это тип данных, которые вы хотите сохранить;для дополнительного кредита, сделайте это классом шаблона.Теперь реализуйте алгоритмы, обсуждаемые в вашем учебнике или на странице Википедии для динамических массивов .

. Обратите внимание, что механизм выделения new / delete не поддерживает увеличение массива, подобного C realloc делает, так что вы фактически будете перемещать содержимое data при увеличении емкости.

Answer 2

Я хотел бы воспользоваться возможностью, чтобы заинтересовать вас интересной, но несколько сложной темой: исключения.

• Если вы начнете выделять память самостоятельно и впоследствии будете играть с необработанными указателями, вы окажетесь в трудном положении, чтобы избежать утечек памяти.
• Даже если вы доверяете учет памяти нужному классу (скажем, 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 3

Массив, который динамически увеличивается при добавлении элементов, называется динамическим массивом, расширяемым массивом, и здесь представлена ​​полная реализация динамического массива .

Answer 4

В 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 ++ соответственно).

Хотя вы можете найти векторы, это то, что вы ищете ...