Boost C++ Libraries: Ticket #2130: De-pessimize compilation complexity for get<N> et. al.

Boost C++ Libraries: Ticket #2130: De-pessimize compilation complexity for get<N> et. al. https://svn.boost.org/trac10/ticket/2130 <p> With some hints from Stephen Watanabe, I came up with the following proof-of-concept, which avoids the O(N<sup>2</sup>) instantiation behavior of <code>get<0>(t)</code>, <code>get<1>(t)</code>, ... <code>get<N>(t)</code>. </p> <p> Seems to me that Boost.Tuple code is pretty old and crufty, and we could improve it a lot even for broken compilers. If we're going to "ship" a TR1, it ought to be best-of-breed, right? </p> <div class="wiki-code"><div class="code"><pre><span class="c1">// Copyright David Abrahams 2008. Distributed under the Boost</span> <span class="c1">// Software License, Version 1.0. (See accompanying</span> <span class="c1">// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)</span> <span class="cp">#include</span> <span class="cpf"><cassert></span><span class="cp"></span> <span class="k">template</span> <span class="o"><</span><span class="kt">unsigned</span> <span class="n">N</span><span class="o">></span> <span class="k">struct</span> <span class="n">tuple_drop_front</span> <span class="p">{</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="c1">// compute resultant tuple</span> <span class="k">struct</span> <span class="n">result_</span> <span class="p">{</span> <span class="k">typedef</span> <span class="k">typename</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">-</span><span class="mi">1</span><span class="o">>::</span><span class="k">template</span> <span class="n">result_</span><span class="o"><</span><span class="n">Tuple</span><span class="o">>::</span><span class="n">type</span><span class="o">::</span><span class="n">tail_type</span> <span class="n">type</span><span class="p">;</span> <span class="p">};</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="k">typename</span> <span class="n">result_</span><span class="o"><</span><span class="n">Tuple</span><span class="o">>::</span><span class="n">type</span> <span class="k">const</span><span class="o">&</span> <span class="k">operator</span><span class="p">()(</span><span class="n">Tuple</span> <span class="k">const</span><span class="o">&</span> <span class="n">x</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">-</span><span class="mi">1</span><span class="o">></span><span class="p">()(</span><span class="n">x</span><span class="p">).</span><span class="n">tail</span><span class="p">;</span> <span class="p">}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="k">typename</span> <span class="n">result_</span><span class="o"><</span><span class="n">Tuple</span><span class="o">>::</span><span class="n">type</span><span class="o">&</span> <span class="k">operator</span><span class="p">()(</span><span class="n">Tuple</span><span class="o">&</span> <span class="n">x</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">-</span><span class="mi">1</span><span class="o">></span><span class="p">()(</span><span class="n">x</span><span class="p">).</span><span class="n">tail</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span> <span class="o"><></span> <span class="k">struct</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="mi">0</span><span class="o">></span> <span class="p">{</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="k">struct</span> <span class="n">result_</span> <span class="p">{</span> <span class="k">typedef</span> <span class="n">Tuple</span> <span class="n">type</span><span class="p">;</span> <span class="p">};</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="n">Tuple</span> <span class="k">const</span><span class="o">&</span> <span class="k">operator</span><span class="p">()(</span><span class="n">Tuple</span> <span class="k">const</span><span class="o">&</span> <span class="n">x</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">x</span><span class="p">;</span> <span class="p">}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="n">Tuple</span><span class="o">&</span> <span class="k">operator</span><span class="p">()(</span><span class="n">Tuple</span><span class="o">&</span> <span class="n">x</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">x</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="k">template</span> <span class="o"><</span><span class="kt">unsigned</span> <span class="n">N</span><span class="p">,</span> <span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="k">typename</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">>::</span><span class="k">template</span> <span class="n">result_</span><span class="o"><</span><span class="n">Tuple</span><span class="o">>::</span><span class="n">type</span><span class="o">::</span><span class="n">head_type</span><span class="o">&</span> <span class="n">get</span><span class="p">(</span><span class="n">Tuple</span><span class="o">&</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">></span><span class="p">()(</span><span class="n">t</span><span class="p">).</span><span class="n">head</span><span class="p">;</span> <span class="p">}</span> <span class="k">template</span> <span class="o"><</span><span class="kt">unsigned</span> <span class="n">N</span><span class="p">,</span> <span class="k">class</span> <span class="nc">Tuple</span><span class="o">></span> <span class="k">typename</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">>::</span><span class="k">template</span> <span class="n">result_</span><span class="o"><</span><span class="n">Tuple</span><span class="o">>::</span><span class="n">type</span><span class="o">::</span><span class="n">head_type</span> <span class="k">const</span><span class="o">&</span> <span class="n">get</span><span class="p">(</span><span class="n">Tuple</span> <span class="k">const</span><span class="o">&</span> <span class="n">t</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">tuple_drop_front</span><span class="o"><</span><span class="n">N</span><span class="o">></span><span class="p">()(</span><span class="n">t</span><span class="p">).</span><span class="n">head</span><span class="p">;</span> <span class="p">}</span> <span class="k">struct</span> <span class="n">null_type</span> <span class="p">{};</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">HT</span><span class="p">,</span> <span class="k">class</span> <span class="nc">TT</span> <span class="o">=</span> <span class="n">null_type</span><span class="o">></span> <span class="k">struct</span> <span class="n">cons</span> <span class="p">{</span> <span class="n">cons</span><span class="p">()</span> <span class="o">:</span> <span class="n">head</span><span class="p">(),</span> <span class="n">tail</span><span class="p">()</span> <span class="p">{}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">T</span><span class="p">,</span> <span class="k">class</span> <span class="nc">U</span><span class="o">></span> <span class="n">cons</span><span class="p">(</span><span class="n">T</span> <span class="k">const</span><span class="o">&</span> <span class="n">x</span><span class="p">,</span> <span class="n">U</span> <span class="k">const</span><span class="o">&</span> <span class="n">y</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">tail</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="p">{}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">T</span><span class="p">,</span> <span class="k">class</span> <span class="nc">U</span><span class="o">></span> <span class="n">cons</span><span class="p">(</span><span class="n">T</span><span class="o">&</span> <span class="n">x</span><span class="p">,</span> <span class="n">U</span><span class="o">&</span> <span class="n">y</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">tail</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="p">{}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">T</span><span class="p">,</span> <span class="k">class</span> <span class="nc">U</span><span class="o">></span> <span class="n">cons</span><span class="p">(</span><span class="n">T</span> <span class="k">const</span><span class="o">&</span> <span class="n">x</span><span class="p">,</span> <span class="n">U</span><span class="o">&</span> <span class="n">y</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">tail</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="p">{}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">T</span><span class="p">,</span> <span class="k">class</span> <span class="nc">U</span><span class="o">></span> <span class="n">cons</span><span class="p">(</span><span class="n">T</span><span class="o">&</span> <span class="n">x</span><span class="p">,</span> <span class="n">U</span> <span class="k">const</span><span class="o">&</span> <span class="n">y</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">tail</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="p">{}</span> <span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">T</span><span class="o">></span> <span class="n">cons</span><span class="p">(</span><span class="n">T</span> <span class="k">const</span><span class="o">&</span> <span class="n">x</span><span class="p">)</span> <span class="o">:</span> <span class="n">head</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">tail</span><span class="p">()</span> <span class="p">{}</span> <span class="k">typedef</span> <span class="n">HT</span> <span class="n">head_type</span><span class="p">;</span> <span class="n">HT</span> <span class="n">head</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">TT</span> <span class="n">tail_type</span><span class="p">;</span> <span class="n">TT</span> <span class="n">tail</span><span class="p">;</span> <span class="p">};</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">0</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">42</span> <span class="p">);</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">0</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">long</span><span class="o">></span> <span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">42</span> <span class="p">);</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">1</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">long</span><span class="o">></span> <span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">10</span> <span class="p">);</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">0</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">long</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">char</span><span class="o">></span> <span class="o">></span> <span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">42</span> <span class="p">);</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">1</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">long</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">char</span><span class="o">></span> <span class="o">></span> <span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">3</span> <span class="p">);</span> <span class="n">assert</span><span class="p">(</span> <span class="n">get</span><span class="o"><</span><span class="mi">2</span><span class="o">></span><span class="p">(</span> <span class="n">cons</span><span class="o"><</span><span class="kt">int</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">long</span><span class="p">,</span> <span class="n">cons</span><span class="o"><</span><span class="kt">char</span><span class="o">></span> <span class="o">></span> <span class="o">></span><span class="p">(</span><span class="mi">42</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="p">)</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">);</span> <span class="p">}</span> </pre></div></div> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/2130 Trac 1.4.3 Dave Abrahams Sat, 19 Jul 2008 23:56:41 GMT description changed https://svn.boost.org/trac10/ticket/2130#comment:1 https://svn.boost.org/trac10/ticket/2130#comment:1 <ul> <li><strong>description</strong> modified (<a href="/trac10/ticket/2130?action=diff&version=1">diff</a>) </li> </ul> Ticket Steven Watanabe Wed, 09 Jun 2010 18:28:19 GMT status changed; resolution set https://svn.boost.org/trac10/ticket/2130#comment:2 https://svn.boost.org/trac10/ticket/2130#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/62683" title="Reimplement boost::tuples::element and boost::tuples::get to make ...">[62683]</a>) Reimplement boost::tuples::element and boost::tuples::get to make better use of memoization. Fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/2130" title="#2130: Bugs: De-pessimize compilation complexity for get<N> et. al. (closed: fixed)">#2130</a> </p> Ticket