building a vector to allow uninitialized storage

Question

Let's say I want to build a vector container that, unlike std::vector, allows uninitialized storage. The usage of the container, say vec <T>, would be roughly like this:

• User explicitly states the vector should allocate N uninitialized elements like that:

  vec <T> a(N, no_init);

• At some point when data are known, user explicitly initializes an element at position n using arguments args...:

  a.init(n, args...);

• OR, equivalently, constructs the element manually:

  new (&a[n]) T(args...);

• Other operations may initialize or copy more massively (like std::uninitialized_copy), but that's only for convenience; the basic underlying operation is the same.

• After completing some task, the vector may be left with some elements initialized and others not. The vector does not hold any extra information, so eventually, before releasing memory, it either destructs all elements anyway, or only destructs depending on T.

I am pretty sure this can be done, only I am not sure of the consequences. Naturally we'd like this structure to be safe for all types T assuming the user does not attempt to use an uninitialized element before constructing it. This may sound like a strong assumption but accessing elements only within the vector's range is not so different an assumption and it's so common.

So my questions are:

1. For which types would it be safe to allow this kind of uninitialized operation as in vec <T> a(no_init)? I guess is_pod would be ok and most probably is_trivial as well. I wouldn't like to put more constraints than necessary.

2. Should destruction be performed always or only for some types? Would the same constraint be ok as above? How about is_trivially_destructible? The idea is that destructing an element that has not been constructed or vice versa (not destructing a constructed element) should do no harm.

3. Is there a major flaw in this attempt, other than the apparent risk of putting more responsibility to the user?

The whole point is that when a user does need such functionality for performance, lower-level solutions like std::get_temporary_buffer or manual allocation (e.g. with operator new()) may be more risky in terms of leaking. I know about std::vector::emplace_back() but that's really not the same thing.

Answer 1

To answer the questions:

1. no restriction on T : if it works for standard containers it works for yours.
2. destruction is conditional, you can statically disable it if std::is_trivially_destructible<T>, else you must track constructed elements and only delete those which were actually constructed.
3. I don't see a major flaw in your idea, but make sure it is worth it: profile your use-case and check that you really spend a lot of time initializing elements.

I'm making the assumption that you implement your container as a block of contiguous memory of size size() * sizeof(T). Also, if the element's destructor must be called, i.e. !std::is_trivially_destructible<T>, you must enable an additional storage, like a std::vector<bool> of size() elements use to flag elements for destruction.

Basically, if T is trivially destructible, you just init when the user asks and don't bother with destroying anything. Else, things are a little more tricky and you need to track which element was constructed and which is uninitialized, so that you only destroy what's needed.

• up-sizing or container creation:
  1. if !std::is_trivially_destructible<T> resize flags storage accordingly
  2. Memory allocation
  3. Optional initialization depending on what the user asked:
     • no_init => if !std::is_trivially_destructible<T>, flag elements as non-initialized. Else do nothing.
     • (Args...) => if std::is_constructible<T, class... Args> call that constructor for each element. If !std::is_trivially_destructible<T>, flag elements as constructed.
• down-sizing or container destruction:
  1. Optional destruction:
     • If std::is_trivially_destructible<T> do nothing
     • else for each element, if it is flagged as constructed, call its destructor
  2. Memory deallocation
  3. If !std::is_trivially_destructible<T> resize flags storage accordingly

From a performance point of view, if T is trivially destructible, things are great. If it has a destructor, things are more constrasted: you gain some constructors/destructors calls, but you need to maintain additional flags storage - in the end it depends if your constructors/destructors are complex enough.

Also like some suggested in the comments, you could just use an associative array based on std::unordered_map, add a size_t vector_size field, implement resize and override size. That way, uninitialized elements would not even be stored. On the other hand, indexing would be slower.