Справедливо ли всегда рекомендовать std :: vector over realloc?

Question

Справедливо ли всегда рекомендовать std :: vector over realloc?

От Часто задаваемые вопросы Бьярна Страуструпа:

Если вы чувствуете необходимость в realloc () — и многие это делают — подумайте об использовании
стандартный вектор библиотеки.

Я предвожу свой вопрос, соглашаясь с тем, что std::vector лучше по многим причинам, и я лично всегда предпочел бы использовать его вместо написания своих собственных динамических массивов с выделением памяти на Си.

Но, std::vector фрагменты памяти по мере ее роста, потому что C ++ не имеет эквивалента realloc (редактировать Чтобы уточнить, я знаю, что std::vectorХранилище является смежным и не будет фрагментированным, я имею в виду фрагментацию пространства памяти, вызванную выделением и освобождением, что realloc можно избежать путем расширения существующего распределения). Так справедливо ли всегда рекомендовать это realloc? С большой осторожностью, не могли бы вы написать что-то, что работает так же, как std::vector но используя функции выделения C, у которых есть возможность увеличивать объем памяти, не перемещая ее адрес и не копируя существующие элементы, делая его таким же хорошим или лучшим с точки зрения фрагментации и производительности?

И соответственно (бонусный вопрос!), Зачем разве C ++ не имеет эквивалента realloc? Кажется странным, что пропустить язык, который так сосредоточен на производительности. Раздел в часто задаваемых вопросах Бьярне имеет именно этот заголовок (без акцента), но ответ не касается «почему». Было ли это просто случайное упущение? Есть ли принципиальная несовместимость с тем, как new/delete Работа? Неужели это на самом деле не дает тех преимуществ, которые кажется на практике?

редактировать: ok, так что я пренебрегал проблемой realloc — std::vector не может быть переписан с помощью realloc потому что он работает только с POD, не выбрасывает и так далее. Возможно, для некоторых ситуаций неплохо было бы использовать контейнер, предназначенный только для POD, написанный для борьбы с гадостью. В любом случае, тем более интересным становится вопрос: std::vector извлечь выгоду из C ++ эквивалента reallocна который (более или менее) ответили здесь:

Имеет ли std :: vector * возможность * перемещать объекты при увеличении емкости? Или, может распределители "перераспределять"?

К сожалению, ответ, кажется, «да, но комитет по стандартам не голосовал за него». Здесь надеемся.

4

c++realloc

Решение

Другие решения

new/new[] а также delete/delete[] обычно располагаются поверх функций выделения библиотеки C (аля malloc/realloc/free), возможно, с дополнительным слоем для оптимизации небольших объектов, которые используют один mallocрегион для быстрого удовлетворения многих маленьких new Запросы. Это наслоение означало поддержку new а также delete потребовалось очень мало усилий для реализации со стороны ранних авторов библиотеки C ++.

Использовать встроенную функцию изменения размера в realloc для C ++, тем не менее, инвазивные изменения в realloc Функция библиотеки нужна для того, чтобы при перемещении в новую область памяти является код библиотеки C ++ получает возможность копировать-конструировать / уничтожать перемещаемые объекты. Это можно сделать как:

обратный вызов происходит после realloc понял, что необходимо переместить, попросив библиотеку C ++ выполнить фактическое перемещение данных вместо выполнения memcpy() стиль побайтовой копии или
в качестве дополнительной функции изменения размера на месте или сбоя без перемещения, чтобы код библиотеки C ++ мог попробовать это, а затем вернуться к malloc и правильное / безопасное копирование перед удалением оригинальных объектов и освобождением оригинальной памяти.

Как большинство C библиотеки realloc функциям не хватает такой возможности перехвата / запроса, стандарт C ++ — и стандартная библиотека — не требуют этого. Как отмечает Мердад, этот ответ документы SGI о признании этого вопроса.

Учитывая широкое использование C ++ в наши дни, имхо, имело бы смысл malloc/realloc/free реализация в самой библиотеке C ++, которая обеспечивает такой перехват / запрос, так что авторы библиотеки C ++, которые видят полезность в realloc можете использовать его свободно; это было бы достойным кандидатом для включения в будущий стандарт.

С большой осторожностью, не могли бы вы написать что-то, что работает так же, как std :: vector, но с использованием функций выделения C, которые имеют возможность увеличивать объем памяти, не перемещая ее адрес и не копируя существующие элементы, делая это таким же хорошим или лучшим с точки зрения фрагментация и производительность?

Как и выше — нет — невозможно копировать, конструировать / разрушать объекты с какой-либо осторожностью без изменений в realloc API.

3

std::vector фрагменты памяти по мере ее роста, потому что C ++ не имеет эквивалента realloc,

realloc фрагментирует память таким же образом, так как он делает то же самое — выделяет новый блок и копирует содержимое, если старый блок не был достаточно большим.

С большой осторожностью, не могли бы вы написать что-то, что работает так же, как std::vector но используя функции выделения C, у которых есть возможность увеличивать объем памяти, не перемещая ее адрес и не копируя существующие элементы, делая его таким же хорошим или лучшим с точки зрения фрагментации и производительности?

Вот только что vector делает. Вы можете контролировать вместимость независимо от размер, и он будет перераспределяться только при превышении емкости. realloc аналогично, но без средств управления производительностью vector лучше с точки зрения фрагментации и производительности.

почему C ++ не имеет эквивалента realloc?

Поскольку он имеет std::vector, что делает то же самое с большей гибкостью. Помимо возможности точно контролировать, как и когда выделяется память, он работает с любым подвижным типом, а realloc будет идти ужасно неправильно при использовании с нетривиальными типами.

2

Есть веская причина, почему C ++ не имеет realloc; вместо того, чтобы повторять это, я укажу вам ответ Вот.

И для записи, правильное vector реализация до некоторой степени смягчает проблему фрагментации, выбрав фактор роста, близкий к золотому сечению, так что это не совсем потерянное дело.

2

Источник

Accepted Answer

Прямое сравнение

                        |  std::vector     | C memory functions
------------------------+------------------+------------------------
default capacity        | undefined        | undefined
default grow            | towards capacity | undefined
deterministic capacity  | available        | no
deterministic grow      | available        | no
deterministic mem.-move | available        | no
non-POD types           | yes              | f***ing no (*)
no-throw                | no               | yes

deterministic mem.-move следует из deterministic capacity/grow, Это когда realloc а также std::vector должны переместить свои сохраненные элементы в новую ячейку памяти.

Я думаю, что (доступный) детерминизм в отношении перемещения памяти вдвойне важен, когда вы рассматриваете перемещение (умные) ссылки любого рода.

_{ПРИМЕЧАНИЕ. В этом отношении я использую термин «детерминистический» в отношении своего времени жизни исходных кодов, то есть его времени жизни в разных версиях разных библиотек с разными флагами компиляции и т. Д.}

Источник

Это делает фрагменты памяти столько, сколько realloc делает:

Краткий обзор вектора шаблона класса [vector.overview]

Элементы
вектор хранится смежно, это означает, что если v это vector<T, Allocator> где T это какой-то тип, кроме boolтогда он подчиняется личности &v[n] == &v[0] + n для всех 0 <= n < v.size()

Другими словами, используемая память находится в одном куске.

Одна большая разница в том, что realloc может на самом деле увеличить выделенные части памяти, не заказав это, однако, это не требуется (man 3 realloc):

человек 3 реаллок

Функция realloc () изменяет размер блока памяти, на который указывает ptr, на размер в байтах. Содержание будет
быть неизменным в диапазоне от начала региона до минимума старого и нового размеров. Если новый
размер больше старого, добавленная память не будет инициализирована. Если ptr равен NULL, то вызов
эквивалентно malloc (size) для всех значений размера; если размер равен нулю, а ptr не равен NULL, то вызов
эквивалентно свободному (ptr). Если ptr не равен NULL, он должен быть возвращен более ранним вызовом malloc (), cal-
loc () или realloc (). Если область, на которую указывает указатель, была перемещена, выполняется освобождение (ptr).

Так что это может увеличить размер, но не обязательно.

std::vector несет в себе не только sizeно также capacity, Если вы знаете заранее, вам понадобится большой vectorпока вы не можете инициализировать все прямо сейчас, вы имеете право увеличить емкость вашего вектора следующим образом:

std::vector<T> vec(32);
vec.reserve(1024);
// vec has size 32, but reserved a memory region of 1024 elements

Итак, в отличие от reallocмомент перераспределения может быть детерминированным с std::vector,

Чтобы ответить на ваш вопрос: потому что есть std::vector, realloc не нужен А также, realloc не разрешено для не POD типов; попытки использовать malloc, free а также realloc непосредственно на не POD приводит к неопределенному поведению.

3