Должен ли вектор хранить размер дважды?

Question

Это довольно академический вопрос, я понимаю, что он не имеет большого значения для оптимизации, но это просто не в интересах.

Из того, что я понимаю, когда вы звоните new[size], для хранения выделяется дополнительное пространстворазмер выделенного массива.Это так, когда вызывается delete [], известно, сколько места можно освободить.

То, что я сделал, написано, как я думаю, что вектор будет примерно реализован:

#include <cstddef>

template <class T>
class Vector
{
public:
  struct VectorStorage
  {
    std::size_t size;
    T data[];
  };

  Vector(std::size_t size) : storage(new VectorStorage[size])
  {
    storage->size = size;
  }

  std::size_t size() 
  { 
    return storage->size; 
  }

  ~Vector() 
  { 
    delete[] storage; 
  }
private:
  VectorStorage* storage;
};

Насколько я могу судить, size хранится дважды.Однажды в объекте VectorStorage напрямую (как это должно быть, чтобы функция size() могла работать), но снова скрытно для компилятора, так что delete[] может работать.

Кажется, что size хранится дважды.Это так и неизбежно, или есть способ гарантировать, что размер сохраняется только один раз?

Answer 1

std::vector не выделяет память;std::allocator, или любой другой распределитель, который вы даете vector, это то, что выделяет памятьИнтерфейсу распределителя присваивается количество элементов для выделения / освобождения, поэтому фактически не требуется его хранить.

Answer 2

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

Answer 3

Векторы обычно не сохраняют размер.Обычная реализация держит указатель за концом последнего элемента и за концом выделенной памяти, так как можно reserve пробел без фактического сохранения элементов в нем.Однако не существует стандартного способа доступа к размеру, сохраненному в new (который может не сохраняться для начала), поэтому обычно требуется некоторое дублирование.

Answer 4

У вас есть размер не в том месте - вы храните его с каждым элементом (благодаря массиву VectorStorage), который также содержит массив (для каждого экземпляра VectorStorage) T. Вы действительно хотите иметь массив внутри массива, как это? Вы никогда не очищаете свой массив Т в своем деструкторе.