Databases
StackOverflow2013
Postsdbo
POAre IEEE floats valid key types for std::map and std::set?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAre IEEE floats valid key types for std::map and std::set?
    primarykey
    data
    text
    <h2>Background</h2> <p>The requirement for a comparator on the key type of an associative container (for example std::map) is that it imposes a strict weak order on the elements of the key type.</p> <p>For a given comparator <code>comp(x, y)</code> we define <code>equiv(x, y) = !comp(x, y) &amp;&amp; !comp(y, x)</code>.<br> The requirements for <code>comp(x, y)</code> being a strict weak order are </p> <ol> <li>Irreflexibility (<code>!comp(x, x)</code> for all <code>x</code>)</li> <li>Transitivity of the ordering (if <code>comp(a, b)</code> and <code>comp(b, c)</code> then <code>comp(a, c)</code>).</li> <li>Transitivity of equivalence (if <code>equiv(a, b)</code> and <code>equiv(b, c)</code> then <code>equiv(a, c)</code>)</li> </ol> <p><code>std::less&lt;float&gt;</code> (the default comparator) uses <code>operator&lt;</code>, which does not create a strict weak order because of <code>NaN</code>. Because <code>x &lt; NaN</code> and <code>NaN &lt; x</code> are false for all <code>x</code>, <code>NaN</code> is equivalent to all floats under this comparator, this breaks condition #3: <code>equiv(1.0, NaN)</code> and <code>equiv(NaN, 2.0)</code> but not <code>equiv(1.0, 2.0)</code>. For IEEE floats except NaN, it is a strict weak order (where each number has its own equivalence class except for <code>0</code> and <code>-0</code>).</p> <h2>The question</h2> <p>Does this mean that one is not allowed by the C++ standard to use IEEE floats (and (long) doubles) as a key type in an associative container because of the above issue, even if I make sure that NaN never gets inserted into the container? I'm not quite sure about the "elements of <code>Key</code>" wording in the standard—if it means all possible elements or just the elements that end up in the container.</p> <p>Note: The question is not about issues wrt. truncation/rounding, I'll likely post a different question regarding that soon.</p> <h3>Update:</h3> <p><em>Sigh</em>. I should've posed the question without specifying float, I just thought it was a nice example.</p> <p><strong>The question really is</strong>: Is it allowed to use a comparator that only imposes a strict weak order on the elements that get put into the container, not all possible instances of the key type? Please don't just answer "yes" or "no", I'd like some references to the standard / prior discussions about this / an answer from a commitee member or something.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USetarion
    1. USetarion
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAre IEEE floats valid key types for std::map and std::set?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAre IEEE floats valid key types for std::map and std::set?
      1. USKos
      1. VTFavorite
    3. VO
      singulars
      1. POAre IEEE floats valid key types for std::map and std::set?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI commented in my answer what I think would happen if you tried inserting a NaN into one, depending on whether or not the container was empty at the time.
      singulars
      1. POAre IEEE floats valid key types for std::map and std::set?
      1. USCashCow
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload