1

For example, in the following code:

int myarray[3];
int x = myarray[1];

Is the code guaranteed to execute successfully in constant time, with x having some integral value? Or can the compiler skip emitting code for this entirely / emit code to launch GNU Chess and still comply with the C++ standard?

This is useful in a data structure that's like an array, but can be initialized in constant time. (Sorry, don't have my copy of Aho, Hopcroft and Ullman handy so can't look up the name.)

Martin C. Martin
  • 3,565
  • 3
  • 29
  • 36
  • It si undefined behavior.:) – Vlad from Moscow Apr 06 '18 at 16:02
  • See [Is uninitialized local variable the fastest random number generator?](https://stackoverflow.com/a/31746063/1708801) – Shafik Yaghmour Apr 06 '18 at 16:03
  • @VladfromMoscow do you have a reference to the spec? – Martin C. Martin Apr 06 '18 at 16:08
  • Your example is undefined behaviour, but you can safely take a reference or pointer to the element and assign a value: `auto& x = myarray[1]; x = 123;`. Is this what you require for your algorithm? – Christian Hackl Apr 06 '18 at 16:09
  • This reeks of being an X/Y question. What does "can be initialized in constant time" mean? Where do you initialise it? Anyway: Possible duplicate of [C/C++ the result of the uninitialized array](https://stackoverflow.com/questions/39351746/c-c-the-result-of-the-uninitialized-array) – underscore_d Apr 06 '18 at 16:09
  • @underscore_d Think of it as a class, ConstantTimeArray, with three methods: `T get(i)`, `void set(i, T)` and `eraseAllTo(T)`. All three methods take O(1) time, independent of the size of the array. See https://cs.stackexchange.com/questions/492/saving-on-array-initialization for an implementation. The implementation is also in the algorithms + data structures book by Aho, Hopcroft and Ullman. – Martin C. Martin Apr 06 '18 at 16:14
  • @ChristianHackl Thanks, but that's not enough. What I need is to be able to get a value from the array. Then, based on some comparisons and using it to index into another array, I can determine whether the value has actually been set yet, or is junk and should be ignored. – Martin C. Martin Apr 06 '18 at 16:16
  • 1
    You can't do that. There is no "junk" state in C/C++. This isn't SQL! An object either has a value you can read with any degree of predictability and definedness, or it doesn't. – underscore_d Apr 06 '18 at 16:17
  • 2
    @MartinC.Martin: How would you distinguish a random "junk value" from a valid value? – Christian Hackl Apr 06 '18 at 16:17
  • @MartinC.Martin: By the way, seeing as how you asked for the specification, here is information on how to obtain either the expensive official ISO document or the free latest draft: https://isocpp.org/std/the-standard – Christian Hackl Apr 06 '18 at 16:21
  • @underscore_d: Well, there is no junk state in SQL, either. `NULL` is a defined, valid thing. A modern C++ equivalent would be `std::optional`. – Christian Hackl Apr 06 '18 at 16:23
  • 1
    question is if this is automatic storage or process/thread storage? Default initialization for global array would be value initialization by zero. – Swift - Friday Pie Apr 06 '18 at 16:24
  • @underscore_d it is possible if data is protected by some kind of sanity check. But obviosly random data may accidently fit into sanity check. Question is if it is acceptable case – Swift - Friday Pie Apr 06 '18 at 16:26
  • @underscore_d Are you saying there's no such thing as unspecified behaviour in C++? What about `int f(int &x) { x=2; return 3;} int g(int &x) { x = 55; return 9;} int a; f(a) + g(a);`? The value of `a` is either 2 or 55, but the standard doesn't say which. Same for `foo(b++, b++)`, its unspecified which increment happens first, but its not undefined behavior. – Martin C. Martin Apr 06 '18 at 16:45
  • @ChristianHackl read the first answer here, they said it better than I can: https://cs.stackexchange.com/questions/492/saving-on-array-initialization – Martin C. Martin Apr 06 '18 at 16:54
  • @MartinC.Martin: If I understand correctly, the pseudo code in that answer assumes that every element in `V` starts with an *unspecified but valid* value, which is why the `V[i] < pos` comparison yields defined results. Standard C++ does not guarantee that this assumption holds because such a guarantee would make the language un-implementable on computer architectures where certain bit patterns in memory or CPU registers do not represent valid integer numbers (or other types). – Christian Hackl Apr 06 '18 at 19:41
  • @MartinC.Martin: By the way, yes, there is unspecified behaviour in C++, but that's not the same as undefined behaviour. See §3.27 and §3.28 of the ISO standard. – Christian Hackl Apr 06 '18 at 20:19
  • @ChristianHackl Right, `NULL` is well-defined. I meant that OP wants a reliable way to check whether something is set. Which is impossible, because for that flag to be reliable, someone first has to have set it... thus ruining any attempts to use this for performance. – underscore_d Apr 07 '18 at 14:45
  • @MartinC.Martin Come on. You want a reliable state that indicates 'unset but definitely unset'. I said that doesn't exist. How does that mean I'm denying the existence of unspecified behaviour? They're different things. – underscore_d Apr 07 '18 at 14:45
  • @Swift The OP seemingly wants to avoid initialising memory for performance reasons. How would requiring the OS/runtime/whatever to initialise it to zero or some other guard value help with that at all? – underscore_d Apr 07 '18 at 14:46

2 Answers2

9

It's undefined behavior.

According to the standard ([dcl.init] paragraph 12),

If no initializer is specified for an object, the object is default-initialized. When storage for an object with automatic or dynamic storage duration is obtained, the object has an indeterminate value, and if no initialization is performed for the object, that object retains an indeterminate value until that value is replaced ... If an indeterminate value is produced by an evaluation, the behavior is undefined except in the following cases

with all the following cases addressing access of unsigned narrow character type or std::byte, which can result in an indeterminate value instead of being undefined.

1201ProgramAlarm
  • 32,384
  • 7
  • 42
  • 56
-3

Accessing any uninitialized data is undefined behavior.

Mikaela Szekely
  • 192
  • 4