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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

Есть С++ 11 rvalue reference и move constructors.

Там есть отличная видео-беседа.

Ответ 5

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

Является ли внутренний буфер вашего массива непрерывным? если см. ответ вашей ссылки
if not, Дерево массивов Hashed или список массивов может быть ваш выбор, чтобы избежать повторного выделения.

Ответ 6

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

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

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