Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Avoiding default construction of elements in standard containers

I'm interested in building an uninitialized_vector container, which will be semantically identical to std::vector with the caveat that new elements which otherwise would be created with a no-argument constructor will instead be created without initialization. I'm primarily interested in avoiding initializing POD to 0. As far as I can tell, there's no way to accomplish this by combining std::vector with a special kind of allocator.

I'd like to build my container in the same vein as std::stack, which adapts a user-provided container (in my case, std::vector). In other words, I'd like to avoid reimplementing the entirety of std::vector and instead provide a "facade" around it.

Is there a simple way to control default construction from the "outside" of std::vector?


Here's the solution I arrived at, which was inspired Kerrek's answer:

#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;
}

This solution will work depending on how closely a particular vendor's compiler & STL's std::vector implementation conforms to c++11.

like image 566
Jared Hoberock Avatar asked Aug 28 '11 01:08

Jared Hoberock


3 Answers

Instead of using a wrapper around the container, consider using a wrapper around the element type:

template <typename T>
struct uninitialized
{
    uninitialized() { }
    T value;
};
like image 104
James McNellis Avatar answered Nov 10 '22 03:11

James McNellis


I think the problem boils down to the type of initialization that the container performs on elements. Compare:

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

The problem with the standard containers is that they take the default argument to be value initialized, as in resize(size_t, T = T()). This means that there's no elegant way to avoid value-initialization or copying. (Similarly for the constructor.)

Even using the standard allocators doesn't work, because their central construct() function takes an argument that becomes value-initialized. What you would rather need is a construct() that uses default-initialization:

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

Such a thing wouldn't be a conforming standard allocator any more, but you could build your own container around that idea.

like image 43
Kerrek SB Avatar answered Nov 10 '22 03:11

Kerrek SB


I don't believe this is possible by wrapping a vector (that works with every type), unless you resize the vector on every add and remove operation.

If you could give up wrapping STL containers, you could do this by keeping an array of char on the heap and using placement new for each of the objects you want to construct. This way you could control exactly when the constructors and destructors of objects were called, one by one.

like image 30
Seth Carnegie Avatar answered Nov 10 '22 02:11

Seth Carnegie