Reordering of operations and lock-free data structures
<p>Assume we have a <code>Container</code> maintaining a set of <code>int</code> values, plus a flag for each value indicating whether the value is valid. Invalid values are considered to be <code>INT_MAX</code>. Initially, all values are invalid. When a value is accessed for the first time, it is set to <code>INT_MAX</code> and its flag is set to valid.</p>

<pre><code>struct Container {
  int&amp; operator[](int i) {
    if (!isValid[i]) {
      values[i] = INT_MAX; // (*)
      isValid[i] = true;   // (**)
    }
    return values[i];
  }
  std::vector&lt;int&gt; values;
  std::vector&lt;bool&gt; isValid;
};
</code></pre>

<p>Now, another thread reads container values concurrently:</p>

<pre><code>// This member is allowed to overestimate value i, but it must not underestimate it.
int Container::get(int i) {
  return isValid[i] ? values[i] : INT_MAX;
}
</code></pre>

<p>This is perfectly valid code, but it is crucial that lines <code>(*)</code> and <code>(**)</code> are executed in the given order.</p>

<ol>
<li>Does the standard guarantee in this case that the lines are executed in the given order? At least from a single-threaded perspective, the lines could be interchanged, couldn't they?</li>
<li>If not, what is the most efficient way to ensure their order? This is high-performance code, so I cannot go without <code>-O3</code> and do not want to use <code>volatile</code>.</li>
</ol>