Вроде как знание о векторах в плюсах довольно тривиальное, но тем не менее.
Общеизвестный факт, что вектор это по факту такая структурка:
template <typename T>
struct vector {
T* data;
int size, capacity;
}Кажется, сделать динамический массив меньшими усилиями ну никак нельзя. В самописных версиях иногда вместо двух чиселок также хранят указатели, а size/capacity вычисляют каждый раз. Можно упороться и хранить их в одной
int64 переменной: первые 4 байта на размер, вторые на вместимость. А можно вообще не хранить размер, а сделать ваш вектор нуль-терминированным и считать длину ручками каждый раз. Раз в k случаев такое тоже работает хорошо. Стандартная библиотека предлагает для кастомизации своего вектора подсунуть свой аллокатор вторым шаблонным аргументом. И всё. Больше пользователю ничего не надо. Но ведь есть ещё такая важная характеристика как resize policy -- то, как ваш вектор изменяет свой размер. Как много выделить в первой аллокации? 1, 2, 8? С единицы начинать плохо: после первого push_back почти наверняка придёт второй. С восьми тоже плохо: может у нас вектор объектов, каждый из которых 3Мб, а юзать мы хотим всего для трёх элементов. Да и для двойки свой кейс можно придумать.
Теперь про изменение этого размера. В clang довольно дефолтная схема с умножением на 2 (с оговорками). Но есть ощущение, что умножение на 2 оч плохое решение. Точнее, умножение на любую константу плохо. Когда речь идёт о расширении 8->16, это вполне себе хорошее решение (или нет?🧐без знания размера объектов непонятно). Но когда у вас уже 1кк элементов и вы хотите положить ещё пару штук, расширение 1кк->2кк выглядит как из пушки по воробьям.
И что делать?
Как вариант не расти всегда с одинаковой скоростью. Можно смотреть на текущее кол-во элементов. Можно на занимаемую память. И после выбора какой-то границы, расти в 2 раза до неё и в 1.2 после (понятно что тут стоит покрутить и найти компромисс между занимаемой памятью и временем работы в зависимости от ваших данных и паттерна работы с ними). В go в этом плане примерно так и сделано.
Ещё есть вопрос, уменьшаться ли, если размер стал слишком маленький: если у меня capacity на 1кк, а размер 10, то наверное можно было бы пожаться до этих самых 10, а потом расти по обычным правилам. Вроде как так почти никто не делает. Правда слышал, что в каком-то языке реализовано сжатие, если размер в 4 раза меньше вместимости (сходу не вспомнил где).
В студвекторе из подобного есть метод shrink_to_fit, который уменьшает вместимость до размера. Прошу заметить, что метод этот non-binding, i.e. необязательный. Тут авторы вольны делать что хотят. В clang честно пытаются уменьшиться.
Учитывая, что resize policy это что-то, что нельзя описать одним числом, интересно попробовать придумать, как это могло бы выглядеть в стандартной библиотеке. Что-то такое:
template <
typename T,
typename Allocator = ... ,
template <typename T> Recap = std::twice>
class vector;где Recap может выглядеть как что-то вроде
template <typename T>
size_t MyRecap(size_t sz, size_t cp) {
if (sz * 4 < cp) { return sz; }
if (cp * sizeof(T) > 10 * kBytesInMB) {
return cp * 1.2;
}
return cp * 2;
}Понятно, что всё это можно делать и сейчас, вычисляя новый размер/капасити снаружи и используя
resize/reserve, но менеджерить размеры не изнутри как неестественно. Возвращаясь к теме пооптимизировать вектор, кроме всем известной специализации для булов иногда пишут специализацию для POD-типов, где можно не вызывать конструкторы/деструкторы при различных операциях.
Можно ещё писать контейнеры кусками (вроде дека), чтобы немножко получше жить с аллокациями. Или пробовать хранить мало данных на стеке, прям как sso.
Зачем это всё? А хер его знает. Почти наверняка на практике это вам не пригодится, потому что если вам не хватает
std::vector, то у вас уже либо все остальные проблемы с производительностью решены, либо очень специфическая задача. Но знать полезно.Такие дела.