Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dynamic arrays in C++ without Undefined Behavior

After learning that std::vector is unimplementable in pure C++, I was wondering if it is possible to write a dynamic array without evoking UB. We can't do pointer arithmetic without an array, which implies we cannot have a dynamic buffer with partially initizalized memory and treat it as an array; so std::vector must rely on the implementation defining some behavior where it would otherwise be UB.

Dynamic arrays are pretty ubiquitious data structures, and generally simple. The seemed impossibility of being able to implement this conformantly makes C++ seem like a not-so-general-purpose system language, IMO.

As so, my questions are:

  • How one can write a dynamic array (a mundane one, not necessarily a Container) in C++ (without using std::vector) that conforms to the standard?
  • How can such implementation be made space-time efficient (preferably without UB or implementation specific behavior)?

N.B.: dynamic array is used here to denote a linear data structure that can grow/shrink "in place", like a std::vector or, similarly, a C buffer (m)alloced in the heap.

like image 391
Nazinho Avatar asked Sep 03 '25 14:09

Nazinho


1 Answers

If std::vector can't, then you can't either.

But I wouldn't worry about it. This is one of those cases where people have found a problem with the wording of the standard, that technically makes an extremely common use case undefined. But your vectors still work.

Now, the key: that's not because of magic innate to std::vector, or to some particular std::vector implementation: it's because the compiler doesn't perform absurd optimisations that make use of this undefined behaviour that somebody only just spotted while studying the text with a fine-toothed comb.

Perhaps it'll be tidied up in a future revision, but for practical purposes you do not need to worry about it, whether you use std::vector or you use new[].

like image 78
Asteroids With Wings Avatar answered Sep 05 '25 04:09

Asteroids With Wings