3

Из описания std::vector::resize: https://www.cplusplus.com/reference/vector/vector/resize/

Никак не могу понять - при изменении размера вектора в меньшую сторону - его capacity гарантировано остается тем, что было до изменения размера или же на усмотрение реализации ?

5
  • 1
    В стандарте ничего нет об изменении емкости. Если бы что-то такое происходило - об этом должно было бы быть написано, так как это могло бы приводить к неприятностям. Так что считаю, что емкость будет неизменной.
    – Harry
    17 апр 2022 в 8:29
  • @Harry from Kiev, но, если в стандарте нет ничего про изменение емкости, то значит изменение емкости не запрещено. А что не запрещено, то разрешено.
    – user480802
    17 апр 2022 в 8:31
  • Т.е. вы хотите сказать, что resize инвалидирует итераторы/указатели, и об этом не написано? Хотя в других случаях это явно оговорено. А ваше "что не запрещено, то разрешено" фактически разрешает при resize винт отформатировать - не запрещено же!
    – Harry
    17 апр 2022 в 8:42
  • @Harry from Kiev, да resize() инвалидирует итераторы на те элементы, которые были ресйзнуты. Я не только хочу это сказать, я говорю это. Об этом написано.
    – user480802
    17 апр 2022 в 8:53
  • Он НЕ инвалидирует итераторы на валидные элементы.
    – Harry
    17 апр 2022 в 11:53

3 ответа 3

4

В стандарте ничего нет об изменении емкости. Если бы что-то такое происходило - об этом было бы написано, так как это могло бы приводить к неприятностям. Например, к перемещению памяти, т.е. к инвалидации итераторов/указателей на остающиеся в контейнере элементы, ко времени работы O(n) и т.д.

В стандарте все такие неприятности оговариваются явно.

Так что емкость будет неизменной.

"По-моему, так" (с) Пух

10
  • но, если в стандарте нет ничего про изменение емкости, то значит изменение емкости не запрещено. А что не запрещено, то разрешено.
    – user480802
    17 апр 2022 в 8:53
  • 1
    В частности, разрешено отформатировать винт. Не запрещено же? :) Смешно даже. Кстати, у меня хоть какое-то обоснование с учетом написанного в стандарте; остальные ответы скорее рассуждения...
    – Harry
    17 апр 2022 в 10:22
  • к инвалидации итераторов/указателей, ко времени работы O(n), Да, std::vector::resize инвалидирует итераторы начиная с удалённого элемента и имеет линейную сложность.
    – wololo
    17 апр 2022 в 11:19
  • @wololo Естественно, итератор на удаленный элемент валидным не бывает :) Неужели это надо было писать явно?... А вот на неудаленные - нет, эти итераторы не инвалидируются.
    – Harry
    17 апр 2022 в 11:46
  • А разве там нет чего-то про реальный размер не более чем в 4 раза больше занятого при удалениях?
    – Qwertiy
    17 апр 2022 в 12:36
3

Изменение размера буфера вектора приводит к инвалидации всех итераторов и ссылок на все его элементы. При этом изменение размера буфера в большую сторону может быть и неявным (например при обычном emplace_back), а в меньшую сторону - только явным, при вызове shrink_to_fit. Соответственно метод resizereserve тоже) никогда не уменьшает capacity.

6
  • Выглядит убедительно, но чисто с формальной точки зрения, что мешает «злой» реализации возвращать уменьшенный capacity при этом не изменяя фактический размер буфера? Т.е. и capacity уменьшили и итераторы не инвалидировали.
    – wololo
    17 апр 2022 в 11:35
  • Мешает то, что capacity не должно тут уменьшаться. Ну и capcity и размер буфера - это одно и то же. Понятно, что у буфера еще наверное есть какой-то свой размер с точки зрения менеджера памяти, однако инвалидация происходит именно при модификации логического размера буфера, который доступен как capacity, а меняется ли реальный буфер или он остается точно таким же - не важно. 17 апр 2022 в 11:50
  • инвалидация происходит именно при модификации логического размера буфера из каких пунктов стандарта это следует?
    – wololo
    17 апр 2022 в 11:54
  • @wololo Из описания методов vector. Собственно размер нижележащего буфера там вообще нигде не фигурирует, только capacity. 17 апр 2022 в 12:07
  • 1
    @wololo То, что изменение capacity отсутствует в перечисленных эффектах. 17 апр 2022 в 13:05
-1

Сам контейнерный класс(в частности std::vector), не занимается распределением памяти, это делает отдельный класс _ его allocator_type, который передается вторым параметром шаблона. Так, что вы можете передать туда любой распределитель, и он останется стандартным вектором.

Если речь идет о стандартном распределителе, который передается по умолчанию, то он не может себе позволить выполнять не эффективные действия, в том числе и перераспределение памяти( в случаи, если контейнеру нужна память меньше, чем для него уже было распределено. Ответ однозначен _ стандартный распределитель гарантировано оставляет выделенную память тем, что было до изменения размера, если даже есть попытка изменить размера вектора в меньшую сторону (то есть стандартныйallocator_type::deallocate ничего не делает в этом случаи).

6
  • 3
    Все-таки это решает сам вектор, а не его аллокатор. 17 апр 2022 в 10:16
  • 1
    Вопрос - как написать свой аллокатор так, чтобы емкость уменьшалась? Если resize по сути к нему не обращается?
    – Harry
    17 апр 2022 в 10:23
  • 1
    "allocator_type::deallocate в любой своей реализации должна ... выделить новый кусок подходящей памяти" Закусывать надо. 17 апр 2022 в 10:47
  • @Harry from Kiev, если функция_член не обращается к распределителю, при попытке изменить размер, значит тем более емкость не меняется, но я обобщал _ если даже есть обращение, то стандартный распределитель этого не сделает. 17 апр 2022 в 11:21
  • Я просто к тому, что, как мне кажется, что аллокатор к данному вопросу в полной мере ни при чем...
    – Harry
    17 апр 2022 в 11:52

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.