Отказ от построения элементов по умолчанию в стандартных контейнерах

Я заинтересован в создании контейнера uninitialized_vector, который будет семантически идентичен std::vector с оговоркой, что новые элементы, которые в противном случае были бы созданы с помощью конструктора без аргументов, вместо этого будут создаваться без инициализации. В первую очередь я заинтересован в том, чтобы избежать инициализации POD в 0. Насколько я могу судить, нет способа добиться этого, комбинируя std::vector с распределителем особого типа.

Я хотел бы построить свой контейнер в том же духе, что и std::stack, который адаптирует контейнер, предоставленный пользователем (в моем случае, std::vector). Другими словами, я хотел бы избежать повторной реализации всего std::vector и вместо этого создать «фасад» вокруг него.

Есть ли простой способ управлять построением по умолчанию «снаружи» std::vector?


Вот решение, к которому я пришел, которое было вдохновлено ответом Керрека:

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <cassert>

// uninitialized_allocator adapts a given base allocator
// uninitialized_allocator's behavior is equivalent to the base
// except for its no-argument construct function, which is a no-op
template<typename T, typename BaseAllocator = std::allocator<T>>
  struct uninitialized_allocator
    : BaseAllocator::template rebind<T>::other
{
  typedef typename BaseAllocator::template rebind<T>::other super_t;

  template<typename U>
    struct rebind
  {
    typedef uninitialized_allocator<U, BaseAllocator> other;
  };

  // XXX for testing purposes
  typename super_t::pointer allocate(typename super_t::size_type n)
  {
    auto result = super_t::allocate(n);

    // fill result with 13 so we can check afterwards that
    // the result was not default-constructed
    std::fill(result, result + n, 13);
    return result;
  }

  // catch default-construction
  void construct(T *p)
  {
    // no-op
  }

  // forward everything else with at least one argument to the base
  template<typename Arg1, typename... Args>
    void construct(T* p, Arg1 &&arg1, Args&&... args)
  {
    super_t::construct(p, std::forward<Arg1>(arg1), std::forward<Args>(args)...);
  }
};

namespace std
{

// XXX specialize allocator_traits
//     this shouldn't be necessary, but clang++ 2.7 + libc++ has trouble
//     recognizing that uninitialized_allocator<T> has a well-formed
//     construct function
template<typename T>
  struct allocator_traits<uninitialized_allocator<T> >
    : std::allocator_traits<std::allocator<T>>
{
  typedef uninitialized_allocator<T> allocator_type;

  // for testing purposes, forward allocate through
  static typename allocator_type::pointer allocate(allocator_type &a, typename allocator_type::size_type n)
  {
    return a.allocate(n);
  }

  template<typename... Args>
    static void construct(allocator_type &a, T* ptr, Args&&... args)
  {
    a.construct(ptr, std::forward<Args>(args)...);
  };
};

}

// uninitialized_vector is implemented by adapting an allocator and
// inheriting from std::vector
// a template alias would be another possiblity

// XXX does not compile with clang++ 2.9
//template<typename T, typename BaseAllocator>
//using uninitialized_vector = std::vector<T, uninitialized_allocator<T,BaseAllocator>>;

template<typename T, typename BaseAllocator = std::allocator<T>>
  struct uninitialized_vector
    : std::vector<T, uninitialized_allocator<T,BaseAllocator>>
{};

int main()
{
  uninitialized_vector<int> vec;
  vec.resize(10);

  // everything should be 13
  assert(std::count(vec.begin(), vec.end(), 13) == vec.size());

  // copy construction should be preserved
  vec.push_back(7);
  assert(7 == vec.back());

  return 0;
}

Это решение будет работать в зависимости от того, насколько точно компилятор конкретного поставщика и реализация STL std::vector соответствуют С++ 11.


person Jared Hoberock    schedule 28.08.2011    source источник
comment
Можете ли вы просто определить конструктор по умолчанию, который ничего не делает? Бьюсь об заклад, компилятор может встроить или опустить его, особенно с включенной оптимизацией.   -  person Doug T.    schedule 28.08.2011
comment
@Doug T. - Это может решить случай с конструктором по умолчанию, но интересные вещи, похоже, происходят в resize - неясно, как вызывать такие функции, как resize, без вызова конструкторов.   -  person Jared Hoberock    schedule 28.08.2011
comment
@Doug: с оговоркой, что вы больше не POD с пользовательским конструктором ...   -  person Kerrek SB    schedule 28.08.2011


Ответы (3)


Я думаю, что проблема сводится к типу инициализации, которую контейнер выполняет для элементов. Сравнивать:

T * p1 = new T;   // default-initalization
T * p2 = new T(); // value-initialization

Проблема со стандартными контейнерами заключается в том, что они принимают аргумент по умолчанию для инициализации значения, как в resize(size_t, T = T()). Это означает, что не существует элегантного способа избежать инициализации или копирования значений. (Аналогично для конструктора.)

Даже использование стандартных распределителей не работает, потому что их центральная функция construct() принимает аргумент, который инициализируется значением. Что вам скорее нужно, так это construct(), который использует инициализацию по умолчанию:

template <typename T>
void definit_construct(void * addr)
{
  new (addr) T;  // default-initialization
}

Такая вещь больше не будет соответствующим стандартным распределителем, но вы можете создать свой собственный контейнер вокруг этой идеи.

person Kerrek SB    schedule 28.08.2011
comment
Спасибо за этот ответ, но я не понимаю вашего комментария о том, что construct() принимает аргумент, который становится инициализированным значением. Почему это не может быть бездействующим? - person Jared Hoberock; 28.08.2011
comment
@Jared: я просто имею в виду то, как стандартные распределители используются в стандартных контейнерах - их функция construct() обычно похожа на construct(void *, const T &), поэтому во время создания есть по крайней мере одна копия, но я предполагаю, что эта функция будет вызываться с объектом, инициализированным значением во всяком случае, как construct(p, T()), поэтому вы не можете избежать инициализации значения внутри стандартных контейнеров. (Даже устанавливающие распределители С++ 11 не могут вам помочь, потому что вы не можете перемещать что-то более одного раза...) - person Kerrek SB; 28.08.2011
comment
Итак, я имею в виду, что вы можете настроить контейнер, который будет вести себя очень похоже на vector, но вместо вызова стандартного распределителя вы просто заставите его говорить new (addr) T; вместо вызова construct(). Вы можете сохранить другие аспекты распределителя (например, выделение памяти). - person Kerrek SB; 28.08.2011
comment
Интересно - похоже, что ваш пример resize(size_t, T = T()) на самом деле не является стандартным. std::vector требуется, чтобы различать resize(size_t) и resize(size_t, const T &) (аналогично для его конструкторов). Таким образом, стандартный распределитель может работать, в зависимости от того, насколько точно соответствует std::vector. - person Jared Hoberock; 28.08.2011
comment
Под стандартом я подразумевал, конечно, взятый из надежного источника :-) Действительно, N3290 говорит, что существуют две разные подписи resize(size_t) и resize(size_t, const T &). Так что вполне возможно, что resize(n) уже ведет себя так, как вы хотите. - person Kerrek SB; 28.08.2011
comment
Проблема в том, что существует три типа инициализации, но std::allocator имеет только два : ноль и значение. Метода инициализации по умолчанию не существует. Если бы это было так, контейнеры могли бы использовать это вместо этого. - person Mooing Duck; 06.05.2020

Вместо использования оболочки вокруг контейнера рассмотрите возможность использования оболочки вокруг типа элемента:

template <typename T>
struct uninitialized
{
    uninitialized() { }
    T value;
};
person James McNellis    schedule 28.08.2011
comment
Разве это не конструкция по умолчанию value? - person Seth Carnegie; 28.08.2011
comment
Ах, не знал, что он использует только типы POD. - person Seth Carnegie; 28.08.2011
comment
Я думаю, что что-то вроде этого может сработать, но у меня есть дополнительные требования по сохранению таких черт, как std::vector::value_type, std::vector::reference и т. д. Они не должны выставлять unintialized<T>. - person Jared Hoberock; 28.08.2011
comment
Запись uninitialized_vector<T> в терминах vector<uninitialized<T>> должна быть простой; каждая функция-член просто должна откладываться на соответствующую функцию-член базового vector, инкапсулируя доступ к value, если это необходимо. - person James McNellis; 28.08.2011

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

Если бы вы могли отказаться от упаковки контейнеров STL, вы могли бы сделать это, сохранив массив char в куче и используя размещение new для каждого из объектов, которые вы хотите создать. Таким образом, вы можете точно контролировать, когда вызываются конструкторы и деструкторы объектов, один за другим.

person Seth Carnegie    schedule 28.08.2011