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

Question

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

Это делается для учебных целей, поэтому я не могу использовать std::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

Это будет хорошей отправной точкой: http://www.cplusplus.com/reference/stl/vector/

и должен прочитать комментарий от Cat Plus Plus

Answer 3

Я думаю here вы найдете все, что вы хотите.

Answer 4

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

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

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

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

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.