Эффективное перераспределение массива в C ++

Question

Как бы я эффективно изменил размер массива, выделенного с помощью некоторого, соответствующего стандартам распределителя C ++?Я знаю, что не предоставляет никаких средств для перераспределения в интерфейсе аллоктора C ++, но ревизия C ++ 11 позволила нам работать с ними легче?Предположим, у меня есть класс vec с определенным оператором копирования foo& operator=(const foo& x).Если x.size() > this->size(), я вынужден

1. Вызвать allocator.destroy () для всех элементов внутреннего хранилища foo.
2. Вызвать allocator.deallocate () ввнутреннее хранилище foo.
3. Перераспределить новый буфер с достаточным пространством для x.size() элементов.
4. Используйте std :: uninitialized_copy для заполнения хранилища.

Есть ли какой-нибудь способ, которым мне легче перераспределить внутреннее хранилище foo без необходимости проходить через все это?Я мог бы привести пример кода, если вы считаете, что он будет полезен, но я чувствую, что здесь он не нужен.

Answer 1

Исходя из предыдущего вопроса , подход, который я использовал для обработки больших массивов, которые могли расти и сжиматься с разумной эффективностью, заключался в написании контейнера, похожего на deque, который разбивал массив на несколько страниц. меньшие массивы. Например, скажем, у нас есть массив из n элементов, мы выбираем размер страницы p и создаем массивы 1 + n / p (страниц) из p элементов. Когда мы хотим перераспределить и расти, мы просто оставляем существующие страницы там, где они есть, и выделяем новые страницы. Когда мы хотим сжать, мы освобождаем полностью пустые страницы.

Недостатком является то, что доступ к массиву немного медленнее, в этом заданном и индексе i вам понадобится page = i / p и смещение на странице i% p, чтобы получить элемент. Я считаю, что это все еще очень быстро и обеспечивает хорошее решение. Теоретически, std :: deque должен делать что-то очень похожее, но для случаев, которые я пробовал с большими массивами, это было очень медленно. См. Комментарии и примечания по связанному вопросу для получения более подробной информации.

Существует также неэффективность памяти в этих n элементах, мы всегда держим p - n% p элементов в резерве. Т.е. мы только когда-либо выделяем или освобождаем полные страницы. Это было лучшее решение, которое я мог придумать в контексте больших массивов с требованием изменения размера и быстрого доступа, хотя я не сомневаюсь, что есть лучшие решения, которые я хотел бы увидеть их.

Answer 2

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

Однако все операционные системы поддерживают реализацию realloc, чтокопировать, если он не может изменить размер на месте.

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

Answer 3

Подобная проблема также возникает, если x.size() > this->size() in foo& operator=(foo&& x).

Нет, это не так.Вы просто swap.

Answer 4

Интересно, что распределитель по умолчанию для g ++ достаточно умен, чтобы использовать один и тот же адрес для последовательных освобождений и распределений больших размеров, если после конца первоначально выделенного буфера достаточно неиспользуемого пространства. Хотя я не проверял то, что собираюсь заявить, я сомневаюсь, что существует большая разница во времени между malloc / realloc и allocate / deallocate / allocate.

Это приводит к потенциально очень опасному нестандартному ярлыку, который может сработать, если вы знаете, что после текущего буфера достаточно места, чтобы перераспределение не привело к появлению нового адреса. (1) Освободить текущий буфер без вызова alloc.destroy () (2) Выделить новый, больший буфер и проверить возвращенный адрес (3) Если новый адрес равен старому адресу, продолжайте успешно; в противном случае вы потеряли свои данные (4) Вызовите allocator.construct () для элементов во вновь выделенном пространстве.

Я бы не рекомендовал использовать это для чего-то другого, кроме удовлетворения своего собственного любопытства, но это работает на g ++ 4.6.

Answer 5

Даже если перераспределение существует, на самом деле, вы можете избежать только # 2, который вы упомянули в своем вопросе в конструкторе copy .Однако в случае роста внутреннего буфера перераспределение может сохранить эти четыре операции.

1. Является ли внутренний буфер вашего массива непрерывным?если это так, см. ответ вашей ссылки
2. , если нет, Хэшированное дерево массивов или список массивов может быть вашим выбором, чтобы избежать перераспределения.

Answer 6

Существует C ++ 11 rvalue ссылка и конструкторы перемещения .

На них есть отличный видео разговор .