4

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.

Improve this question
18
  • 2
    First time I heard that std::vector is unimplementable in pure C++. Can you provide a reference so I can get up to speed? Commented Mar 2, 2020 at 0:50
  • 3
    @davidbak There's a link in the question. Commented Mar 2, 2020 at 0:51
  • 2
    OK. Answers at that link strongly suggest that the problem is a bug in the standard which doesn't reflect the actual intent (or actual practice). So, is this the premise for this question? That the bug in the standard won't be fixed anytime soon and in the meantime some hypothetical compiler will take advantage of it and cause anyone's std::vector, no matter how implemented, to erase your hard disk due to UB? Commented Mar 2, 2020 at 0:54
  • 1
    @Nazinho It is relevant when you're asking how to do something in practice. This particular UB falls into the category of "standard wording oversight", not into the category of "omg never do this in your program it's something the compiler will assume you don't do". This is real life so you have to have a little flexibility. That being said I vaguely recall a proposal that may be relevant; still trying to find it. Commented Mar 2, 2020 at 0:58
  • 1
    @AsteroidsWithWings: "still trying to find it" You probably mean P0593. Commented Mar 2, 2020 at 1:05

2 Answers 2

Reset to default
8

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[].

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That's probably the pragmatical POV. 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[]. can you please provide some insight for whether there's some discussion on this?
I've added a link to a relevant proposal with plenty of discussion and rationale (thanks Nicol for getting me the link)
5

dynamic array is used here to denote a linear data structure that can grow/shrink "in place",

You can't. It is precisely the growing/shrinking in-place that makes vector unimplementable in C++17.

The problem is that the C++17 object model recognizes "array" as a thing, a special object type with its own properties. Pointer arithmetic recognizes arrays and works within them. But an "array" has a specific element count, and merely creating a live object of the array element type at the end of the array doesn't actually make the array longer. Which means pointer arithmetic doesn't work to access this newly created object.

That problem doesn't go away just because you change the wrapper. It is a problem which is fundamental to the idea of being able to make an array bigger and smaller, while still having pointer arithmetic work.

Improve this answer

4 Comments

What this mean in pratice? Is such inconsistency irrelevant for pratical applications?
@Nazinho: "Is such inconsistency irrelevant for pratical applications?" For this case? Yes.
Where overlooking this can cause trouble?
@Nazinho: Pretty much nowhere. I don't understand your question.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.