Интересно, много ли C++ программистов задумывается о том, а как растет std::vector, когда мы в него добавляем элементы через push_back и не имеем возможности сделать предварительно reserve?
А ведь рост размера std::vector может существенным образом повлиять на расход памяти.
Предположим, что реализация std::vector в вашей стандартной библиотеке использует коэффициент 1.5 для увеличения размера вектора. Т.е. вы делаете push_back в полный вектор и опа! Ваш вектор увеличился в полтора раза. Была емкость на 1000 элементов, а стала на 1500. А использоваться оттуда будет 1001.
А если реализация стандартной библиотеки использует коэффициент 2, то дела еще хуже.
Сильно негативно это начинает проявляться на векторах размером в миллион-два-три и т.д. Если у вас в программе таких векторов не один и не два, то вы с удивлением для себя сможете обнаружить, что в этих векторах где-то 1/5 или 1/4, а то и 1/3 объема не занято. Что в сумме может дать десятки мегабайт впустую потраченной памяти.
Чтобы этого не происходило приходится вручную контролировать размер и емкость вектора и, опять же, вручную дергать reserve перед push_back-ами.
А то, что делается вручную, легко забыть или же сделать неправильно 😣
Поэтому мне лично не хватает возможности задать для std::vector какую-то собственную политику роста. Что-то типа:
struct my_growth_policy {
[[nodiscard]] std::size_t operator()(std::size_t current_capacity) {
return ... // здесь какие-то вычисления.
}
};
using my_vector = std::vector<my_data, std::allocator<my_data>, my_growth_policy>;
Тогда не пришлось бы вручную контролировать емкость перед каждым push_back-ом.
Но, боюсь, в стандартном std::vector такого не будет никогда.
4 комментария:
Наслаждайтесь: https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit
Произойдет то же самое, если вы выберете growth_factor, который не будет соответствовать вашей задаче. Вся эта политика роста вектора - трейдофф между перформансом по времени и потреблением памяти. Прочитав ваш пост создается впечатление, что вас интересуют те кейсы, когда вы знаете характер и количество данных в вашем проекте и можете использовать это для ускорения работы с вектором. В таком случае использование кастомной growth_policy и применение shrink_to_fit в том месте, где добавление элементов в вектор более не предполагается дадут одинаковый результат и одинаковые риски - вы можете как забыть написать shrink_to_fit в каком-то учатске проекта, так и неверно выбрать growth_policy в том же самом участке.
Надо написать велосипед - обертку... :)
> Надо написать велосипед - обертку... :)
Впечатления от написания такой обертки ждут своей публикации.
Отправить комментарий