Почему «unbounded_array» более эффективен, чем «вектор»?

Question

Здесь говорится , что

Неограниченный массив похож на std :: vector может расти в размер за пределы любой фиксированной границы. тем не мение unbounded_array нацелен на оптимальное спектакль. Следовательно, unbounded_array не моделирует последовательность как std :: vector делает.

Что это значит?

Answer 1

Как разработчик Boost, я могу вам сказать, что совершенно нормально подвергать сомнению утверждения в документации; -)

Из чтения этих документов и чтения исходного кода (см. storage.hpp ) я могу сказать, что это несколько правильно, учитывая некоторые предположения о реализации std :: vector в то время, когда код был написано. Этот код изначально датируется 2000 годом, а, возможно, и поздним 2002 годом. Это означает, что в то время многие реализации STD не помогали оптимизировать уничтожение и конструирование объектов в контейнерах. Заявление о неизменении размера легко опровергается с помощью изначально большого вектора емкости. Утверждение о скорости, я думаю, полностью вытекает из того факта, что unbounded_array имеет специальный код для исключения dtors & ctors, когда хранимые объекты имеют тривиальные реализации их. Следовательно, он может избегать их вызова, когда ему нужно что-то переставить или когда он копирует элементы. По сравнению с действительно недавними реализациями STD это не будет быстрее, поскольку новая реализация STD, как правило, использует преимущества таких вещей, как перемещение семантики, для еще большей оптимизации.

Answer 2

Кажется, что отсутствуют методы insert и erase.Поскольку они могут быть «медленными», то есть их производительность зависит от size() в реализации vector, они были опущены, чтобы программист не мог выстрелить себе в ногу.

insert и eraseСтандарт требует, чтобы контейнер назывался Sequence, поэтому в отличие от vector, unbounded_array не является последовательностью.

Эффективность не достигается, если не быть последовательностью как таковой.

Однако он является более эффективным в своей схеме выделения памяти, поскольку избегает концепции vector::capacity и всегда имеет выделенный блок точно в соответствии с размером содержимого.Это делает объект unbounded_array меньшим и делает блок в куче настолько большим, насколько это необходимо.

Answer 3

Как я понял из связанной документации, все дело в стратегии распределения. std :: vector afaik откладывает выделение до необходимого и затем может выделить некоторый разумный кусок meory, unbounded_array швы, чтобы выделить больше памяти на ранней стадии, и, следовательно, он может выделяться реже Но это только предположение из заявления в документации, что оно выделяет больше памяти, чем может потребоваться, и что выделение ресурсов обходится дороже.