Почему динамические массивы в C ++ и Java имеют разные начальные возможности?
Поэтому я искал, как на самом деле работает динамический массив в целом. то, что я нашел, это две разные концепции.
В C ++
В C ++ динамический массив обычно реализуется векторами. Векторы устанавливают емкость на 0, увеличивают количество для вставки нового элемента, а затем удваивают размер емкости для новых вставок.
vector.h
/*
* Implementation notes: Vector constructor and destructor
* -------------------------------------------------------
* The constructor allocates storage for the dynamic array and initializes
* the other fields of the object. The destructor frees the memory used
* for the array.
*/
template <typename ValueType>
Vector<ValueType>::Vector() {
count = capacity = 0;
elements = NULL;
}
Для расширения размера вектора
/*
* Implementation notes: expandCapacity
* ------------------------------------
* This function doubles the array capacity, copies the old elements into
* the new array, and then frees the old one.
*/
template <typename ValueType>
void Vector<ValueType>::expandCapacity() {
capacity = max(1, capacity * 2);
ValueType *array = new ValueType[capacity];
for (int i = 0; i < count; i++) {
array[i] = elements[i];
}
if (elements != NULL) delete[] elements;
elements = array;
}
На яве
В Java динамический массив реализован с использованием arrayList. Они устанавливают емкость на 10 (на основе JVM), и, как только емкость становится полной, они увеличивают емкость на некоторый фактор.
Причиной установки емкости на 10 является то, что вам не нужно часто инициализировать память для каждой новой вставки. Когда емкость заполнится, увеличьте размер емкости.
любопытство
Почему реализация в vector.h устанавливает значение по умолчанию 0? Установка небольшого значения емкости (скажем, 10) вместо установки 0 может сэкономить накладные расходы при инициализации памяти каждый раз, когда пользователь вставляет какой-либо элемент.
Поскольку это динамический массив, установка небольшой емкости для вектора не принесет вреда, поскольку размер динамического массива обычно превышает 10.
Изменить: мой вопрос, почему по умолчанию 0? по умолчанию это может быть любое небольшое значение, потому что в любом случае вектор будет расширяться до некоторого определенного размера, поэтому цель использования вектора в первую очередь.
Решение
Наличие нулевой емкости по умолчанию имеет то преимущество, что по умолчанию создание std::vector вообще не выполняет динамического выделения памяти (вы не платите за то, что вам не нужно).
Если вы знаете, что вам нужно ~ 10 элементов, вы можете установить емкость явно с помощью вызова std::vector::reserve:
std::vector<int> vec;
vec.reserve(10);
Я могу только предположить, почему Java делает вещи по-другому, но на деле динамическое распределение памяти в Java дешевле, чем в c ++, и эти два языка также придерживаются разных принципов, когда речь идет о производительности / низкоуровневом управлении по сравнению с простотой.
Другие решения
Почему по умолчанию 0?
Это не 0 по умолчанию, на самом деле. То есть, стандарт языка C ++ не определяет (AFAIK), какой должна быть начальная емкость вектора, построенного по умолчанию.
На практике большинство / все реализации по умолчанию имеют нулевую емкость. Причина, я бы сказал, заключается в одном из принципов проектирования языка C ++:
То, что вы не используете, вы не платите.
(см .: Б. Страуструп: Дизайн и эволюция C ++. Аддисон Уэсли, ISBN 0-201-54330-3. Март 1994 г.)
И это не просто банальная тавтология, это наклон конструктивных соображений.
Так что в C ++ мы бы предпочли не платить что-нибудь для вектора, в который не вставлены какие-либо элементы, сохраните потенциальный размер, сделав начальную «жертву».
Однако, как отмечает @yurikilocheck, std::vector класс дает вам reserve() метод, так что вы можете установить начальную емкость самостоятельно — и поскольку конструктор по умолчанию ничего не выделяет, вы не заплатите «дополнительно» за два выделения — только один раз. Опять же, вы платите (по существу) минимально возможный.
Редактировать: С другой стороны, std::vector частично нарушает этот принцип, выделяя больше места, чем необходимо для достижения максимальной производительности. Но, по крайней мере, это не лишний вызов распределения.
Я использовал реализацию, которая резервирует значение по умолчанию 32 элемента на вектор. Это была нативная реализация Sun C ++ STL. Это была катастрофа. У меня была совершенно разумная программа, которая по своей природе должна была содержать несколько сотен тысяч этих векторов. Недостаточно памяти. И все должно было быть в порядке, так как из этих сотен тысяч элементов только небольшой процент имел непустые векторы.
Исходя из личного опыта, 0 — это лучший размер по умолчанию для вектора.