Paper: P0805R0<br/>
Audience: Library Evolution, Library<br/>
Title: Comparing Containers<br/>
Author: Marshall Clow <a href="mailto:mclow.lists@gmail.com">mclow.lists@gmail.com</a><br/>

<h2>Rationale</h2>

<p>When I was attempting to implement <a href="http://wg21.link/P0122R5">P0122R5</a>, I became frustrated with the inability to compare spans of different lengths, and sometimes spans of the same lengths as well. I started thinking about this in general, and realized that our comparison conventions for containers are limited, but for no good reason.</p>

<p>In C++17, <code>std::optional</code> has a nice set of comparison operators.</p>

<ul>
<li>An <code>optional&lt;T&gt;</code> can be compared to a <code>T</code>.</li>
<li>An <code>optional&lt;T&gt;</code> can be compared to a <code>U</code>.</li>
<li>An <code>optional&lt;T&gt;</code> can be compared to an <code>optional&lt;T&gt;</code>.</li>
<li>An <code>optional&lt;T&gt;</code> can be compared to an <code>optional&lt;U&gt;</code>.</li>
<li>An <code>optional&lt;T&gt;</code> can be compared to a <code>nullopt_t</code>.</li>
</ul>


<p>But an <code>array&lt;int, 5&gt;</code> cannot be compared to an <code>array&lt;int, 6&gt;</code>. Nor can an <code>array&lt;int, 5&gt;</code> cannot be compared to an <code>array&lt;long, 5&gt;</code>.  This seems like an artificial limitation to me - these comparisons &ldquo;make sense&rdquo;, we just don&rsquo;t implement them.  We <em>can</em> compare a <code>vector&lt;int&gt;</code> that contains five elements to a <code>vector&lt;int&gt;</code> that contains six elements, but not a <code>vector&lt;int&gt;</code> to a <code>vector&lt;long&gt;</code>, no matter what size. And if the allocators are different, that won&rsquo;t work either.</p>

<p>As people write more and more generic code, these arbitrary limitations will cause increasing friction.</p>

<p>In the header <code>&lt;algorithm&gt;</code> we have <code>lexicographical_compare</code>. This is a very general algorithm - it compares two sequences, which may be of differing lengths, and/or different underlying types, and returns whether one is &ldquo;less than&rdquo; the other. But that generality is not reflected in the containers, even though their comparisons are defined in terms of <code>lexicographical_compare</code> (Table 85).</p>

<p>The same logic applies to <code>std::tuple</code>. The comparison operators for <code>tuple</code> require that both tuples be the same size ([tuple.rel]/1) but (surprisingly) not that they contain the same types.</p>

<h2>Suggested changes</h2>

<p>The changes here are just for <code>array</code> and <code>tuple</code>; if there is interest, I can provide wording for the rest of the sequence containers.</p>

<p>These wording changes are relative to N4687.</p>

<p>In [array.syn], add the following functions:</p>

<pre><code>template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator==(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator!=(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator&lt;(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator&gt;(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator&lt;=(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
template &lt;class T1, class T2, size_t N1, size_t N2&gt;
  bool operator&gt;=(const array&lt;T1,N1&gt;&amp; x, const array&lt;T2,N2&gt;&amp; y);
</code></pre>

<p>In [tuple.rel]/1,</p>

<ul>
<li>replace: &ldquo;<code>i &lt; sizeof...(TTypes)</code>&rdquo; with &ldquo;<code>i &lt; min(sizeof...(TTypes), sizeof...(UTypes))</code>&rdquo;</li>
<li>and delete: &ldquo;<code>sizeof...(TTypes) == sizeof...(UTypes).</code>&rdquo;</li>
</ul>


<p>In [tuple.rel]/2,</p>

<ul>
<li>add:  &ldquo;<code>false</code> if <code>sizeof...(TTypes) != sizeof...(UTypes)</code>, otherwise &rdquo; after <em>Returns:</em></li>
</ul>


<p>In [tuple.rel]/4,</p>

<ul>
<li>replace: &ldquo;<code>i &lt; sizeof...(TTypes)</code>&rdquo; with &ldquo;<code>i &lt; min(sizeof...(TTypes), sizeof...(UTypes))</code>&rdquo;</li>
<li>and delete: &ldquo;<code>sizeof...(TTypes) == sizeof...(UTypes).</code>&rdquo;</li>
</ul>


<p>In [tuple.rel]/4,</p>

<ul>
<li>add:  &ldquo;A zero-length tuple is lexicographically less than any non-zero-length tuple.&rdquo; after &ldquo;lexicographical comparison between <code>t</code> and <code>u</code>.&rdquo;</li>
</ul>


<h2>Implementation status</h2>

<p>I have implemented the changes for both <code>tuple</code> and <code>array</code>.</p>

<h2>Future Directions</h2>

<ul>
<li>Provide similar functionality for <code>vector</code>, <code>list</code>, <code>deque</code>, and <code>forward_list</code>.</li>
<li>Provide compatibility with <a href="https://wg21.link/P0515">P0515 - Consistent Comparisons</a>.</li>
<li>Research and decide if similar functionality should be provided for the associative containers.  P0809R0 - &ldquo;Comparing Unordered Containers&rdquo; (no link yet) may influence this direction.</li>
</ul>