Интересно, много ли 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
И что будет после того, как я сделаю shink_to_fit, а следом за ним еще один push_back?
Произойдет то же самое, если вы выберете growth_factor, который не будет соответствовать вашей задаче. Вся эта политика роста вектора - трейдофф между перформансом по времени и потреблением памяти. Прочитав ваш пост создается впечатление, что вас интересуют те кейсы, когда вы знаете характер и количество данных в вашем проекте и можете использовать это для ускорения работы с вектором. В таком случае использование кастомной growth_policy и применение shrink_to_fit в том месте, где добавление элементов в вектор более не предполагается дадут одинаковый результат и одинаковые риски - вы можете как забыть написать shrink_to_fit в каком-то учатске проекта, так и неверно выбрать growth_policy в том же самом участке.
Ну значит и пользы от shrink_to_fit не будет.
Если бы я знал количество данных, то можно было бы делать reserve однажды и не заморачиваться. Но проблема в том, что не знаю. Более того, нет момента, когда можно сказать, что все, вектора заполнены, больше они меняться не будут. Будь такой момент, то можно было бы пользоваться shink_to_fit и все.
Если не правильно выбран growth_policy, то это станет очевидно.
И, если бы vector поддерживал кастомные growth_policy, то я бы мог в одном месте этот growth_policy поменять и все.
А так приходится вручную расставлять контроль емкости перед всеми операциями push_back/insert. Вот это мне как раз и не нравится, т.к. надежным не выглядит.
Отправить комментарий