libs/mp11/doc/html/simple_cxx11_metaprogramming_2.html

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta charset="UTF-8">
   5 <!--[if IE]><meta http-equiv="X-UA-Compatible" content="IE=edge"><![endif]-->
   6 <meta name="viewport" content="width=device-width, initial-scale=1.0">
   7 <meta name="generator" content="Asciidoctor 1.5.8">
   8 <meta name="author" content="Peter Dimov">
   9 <title>Simple C&#43;&#43;11 metaprogramming, part 2</title>
  10 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700">
  11 <style>
  12 /* Asciidoctor default stylesheet | MIT License | http://asciidoctor.org */
  13 /* Uncomment @import statement below to use as custom stylesheet */
  14 /*@import "https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700";*/
  15 article,aside,details,figcaption,figure,footer,header,hgroup,main,nav,section,summary{display:block}
  16 audio,canvas,video{display:inline-block}
  17 audio:not([controls]){display:none;height:0}
  18 script{display:none!important}
  19 html{font-family:sans-serif;-ms-text-size-adjust:100%;-webkit-text-size-adjust:100%}
  20 a{background:transparent}
  21 a:focus{outline:thin dotted}
  22 a:active,a:hover{outline:0}
  23 h1{font-size:2em;margin:.67em 0}
  24 abbr[title]{border-bottom:1px dotted}
  25 b,strong{font-weight:bold}
  26 dfn{font-style:italic}
  27 hr{-moz-box-sizing:content-box;box-sizing:content-box;height:0}
  28 mark{background:#ff0;color:#000}
  29 code,kbd,pre,samp{font-family:monospace;font-size:1em}
  30 pre{white-space:pre-wrap}
  31 q{quotes:"\201C" "\201D" "\2018" "\2019"}
  32 small{font-size:80%}
  33 sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline}
  34 sup{top:-.5em}
  35 sub{bottom:-.25em}
  36 img{border:0}
  37 svg:not(:root){overflow:hidden}
  38 figure{margin:0}
  39 fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em}
  40 legend{border:0;padding:0}
  41 button,input,select,textarea{font-family:inherit;font-size:100%;margin:0}
  42 button,input{line-height:normal}
  43 button,select{text-transform:none}
  44 button,html input[type="button"],input[type="reset"],input[type="submit"]{-webkit-appearance:button;cursor:pointer}
  45 button[disabled],html input[disabled]{cursor:default}
  46 input[type="checkbox"],input[type="radio"]{box-sizing:border-box;padding:0}
  47 button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0}
  48 textarea{overflow:auto;vertical-align:top}
  49 table{border-collapse:collapse;border-spacing:0}
  50 *,*::before,*::after{-moz-box-sizing:border-box;-webkit-box-sizing:border-box;box-sizing:border-box}
  51 html,body{font-size:100%}
  52 body{background:#fff;color:rgba(0,0,0,.8);padding:0;margin:0;font-family:"Noto Serif","DejaVu Serif",serif;font-weight:400;font-style:normal;line-height:1;position:relative;cursor:auto;tab-size:4;-moz-osx-font-smoothing:grayscale;-webkit-font-smoothing:antialiased}
  53 a:hover{cursor:pointer}
  54 img,object,embed{max-width:100%;height:auto}
  55 object,embed{height:100%}
  56 img{-ms-interpolation-mode:bicubic}
  57 .left{float:left!important}
  58 .right{float:right!important}
  59 .text-left{text-align:left!important}
  60 .text-right{text-align:right!important}
  61 .text-center{text-align:center!important}
  62 .text-justify{text-align:justify!important}
  63 .hide{display:none}
  64 img,object,svg{display:inline-block;vertical-align:middle}
  65 textarea{height:auto;min-height:50px}
  66 select{width:100%}
  67 .center{margin-left:auto;margin-right:auto}
  68 .stretch{width:100%}
  69 .subheader,.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{line-height:1.45;color:#7a2518;font-weight:400;margin-top:0;margin-bottom:.25em}
  70 div,dl,dt,dd,ul,ol,li,h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6,pre,form,p,blockquote,th,td{margin:0;padding:0;direction:ltr}
  71 a{color:#2156a5;text-decoration:underline;line-height:inherit}
  72 a:hover,a:focus{color:#1d4b8f}
  73 a img{border:none}
  74 p{font-family:inherit;font-weight:400;font-size:1em;line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility}
  75 p aside{font-size:.875em;line-height:1.35;font-style:italic}
  76 h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{font-family:"Open Sans","DejaVu Sans",sans-serif;font-weight:300;font-style:normal;color:#ba3925;text-rendering:optimizeLegibility;margin-top:1em;margin-bottom:.5em;line-height:1.0125em}
  77 h1 small,h2 small,h3 small,#toctitle small,.sidebarblock>.content>.title small,h4 small,h5 small,h6 small{font-size:60%;color:#e99b8f;line-height:0}
  78 h1{font-size:2.125em}
  79 h2{font-size:1.6875em}
  80 h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em}
  81 h4,h5{font-size:1.125em}
  82 h6{font-size:1em}
  83 hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em;height:0}
  84 em,i{font-style:italic;line-height:inherit}
  85 strong,b{font-weight:bold;line-height:inherit}
  86 small{font-size:60%;line-height:inherit}
  87 code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)}
  88 ul,ol,dl{font-size:1em;line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit}
  89 ul,ol{margin-left:1.5em}
  90 ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0;font-size:1em}
  91 ul.square li ul,ul.circle li ul,ul.disc li ul{list-style:inherit}
  92 ul.square{list-style-type:square}
  93 ul.circle{list-style-type:circle}
  94 ul.disc{list-style-type:disc}
  95 ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0}
  96 dl dt{margin-bottom:.3125em;font-weight:bold}
  97 dl dd{margin-bottom:1.25em}
  98 abbr,acronym{text-transform:uppercase;font-size:90%;color:rgba(0,0,0,.8);border-bottom:1px dotted #ddd;cursor:help}
  99 abbr{text-transform:none}
 100 blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd}
 101 blockquote cite{display:block;font-size:.9375em;color:rgba(0,0,0,.6)}
 102 blockquote cite::before{content:"\2014 \0020"}
 103 blockquote cite a,blockquote cite a:visited{color:rgba(0,0,0,.6)}
 104 blockquote,blockquote p{line-height:1.6;color:rgba(0,0,0,.85)}
 105 @media screen and (min-width:768px){h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2}
 106 h1{font-size:2.75em}
 107 h2{font-size:2.3125em}
 108 h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em}
 109 h4{font-size:1.4375em}}
 110 table{background:#fff;margin-bottom:1.25em;border:solid 1px #dedede}
 111 table thead,table tfoot{background:#f7f8f7}
 112 table thead tr th,table thead tr td,table tfoot tr th,table tfoot tr td{padding:.5em .625em .625em;font-size:inherit;color:rgba(0,0,0,.8);text-align:left}
 113 table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)}
 114 table tr.even,table tr.alt,table tr:nth-of-type(even){background:#f8f8f7}
 115 table thead tr th,table tfoot tr th,table tbody tr td,table tr td,table tfoot tr td{display:table-cell;line-height:1.6}
 116 h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em}
 117 h1 strong,h2 strong,h3 strong,#toctitle strong,.sidebarblock>.content>.title strong,h4 strong,h5 strong,h6 strong{font-weight:400}
 118 .clearfix::before,.clearfix::after,.float-group::before,.float-group::after{content:" ";display:table}
 119 .clearfix::after,.float-group::after{clear:both}
 120 *:not(pre)>code{font-size:.9375em;font-style:normal!important;letter-spacing:0;padding:.1em .5ex;word-spacing:-.15em;background-color:#f7f7f8;-webkit-border-radius:4px;border-radius:4px;line-height:1.45;text-rendering:optimizeSpeed;word-wrap:break-word}
 121 *:not(pre)>code.nobreak{word-wrap:normal}
 122 *:not(pre)>code.nowrap{white-space:nowrap}
 123 pre,pre>code{line-height:1.45;color:rgba(0,0,0,.9);font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;text-rendering:optimizeSpeed}
 124 em em{font-style:normal}
 125 strong strong{font-weight:400}
 126 .keyseq{color:rgba(51,51,51,.8)}
 127 kbd{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;display:inline-block;color:rgba(0,0,0,.8);font-size:.65em;line-height:1.45;background-color:#f7f7f7;border:1px solid #ccc;-webkit-border-radius:3px;border-radius:3px;-webkit-box-shadow:0 1px 0 rgba(0,0,0,.2),0 0 0 .1em white inset;box-shadow:0 1px 0 rgba(0,0,0,.2),0 0 0 .1em #fff inset;margin:0 .15em;padding:.2em .5em;vertical-align:middle;position:relative;top:-.1em;white-space:nowrap}
 128 .keyseq kbd:first-child{margin-left:0}
 129 .keyseq kbd:last-child{margin-right:0}
 130 .menuseq,.menuref{color:#000}
 131 .menuseq b:not(.caret),.menuref{font-weight:inherit}
 132 .menuseq{word-spacing:-.02em}
 133 .menuseq b.caret{font-size:1.25em;line-height:.8}
 134 .menuseq i.caret{font-weight:bold;text-align:center;width:.45em}
 135 b.button::before,b.button::after{position:relative;top:-1px;font-weight:400}
 136 b.button::before{content:"[";padding:0 3px 0 2px}
 137 b.button::after{content:"]";padding:0 2px 0 3px}
 138 p a>code:hover{color:rgba(0,0,0,.9)}
 139 #header,#content,#footnotes,#footer{width:100%;margin-left:auto;margin-right:auto;margin-top:0;margin-bottom:0;max-width:62.5em;*zoom:1;position:relative;padding-left:.9375em;padding-right:.9375em}
 140 #header::before,#header::after,#content::before,#content::after,#footnotes::before,#footnotes::after,#footer::before,#footer::after{content:" ";display:table}
 141 #header::after,#content::after,#footnotes::after,#footer::after{clear:both}
 142 #content{margin-top:1.25em}
 143 #content::before{content:none}
 144 #header>h1:first-child{color:rgba(0,0,0,.85);margin-top:2.25rem;margin-bottom:0}
 145 #header>h1:first-child+#toc{margin-top:8px;border-top:1px solid #dddddf}
 146 #header>h1:only-child,body.toc2 #header>h1:nth-last-child(2){border-bottom:1px solid #dddddf;padding-bottom:8px}
 147 #header .details{border-bottom:1px solid #dddddf;line-height:1.45;padding-top:.25em;padding-bottom:.25em;padding-left:.25em;color:rgba(0,0,0,.6);display:-ms-flexbox;display:-webkit-flex;display:flex;-ms-flex-flow:row wrap;-webkit-flex-flow:row wrap;flex-flow:row wrap}
 148 #header .details span:first-child{margin-left:-.125em}
 149 #header .details span.email a{color:rgba(0,0,0,.85)}
 150 #header .details br{display:none}
 151 #header .details br+span::before{content:"\00a0\2013\00a0"}
 152 #header .details br+span.author::before{content:"\00a0\22c5\00a0";color:rgba(0,0,0,.85)}
 153 #header .details br+span#revremark::before{content:"\00a0|\00a0"}
 154 #header #revnumber{text-transform:capitalize}
 155 #header #revnumber::after{content:"\00a0"}
 156 #content>h1:first-child:not([class]){color:rgba(0,0,0,.85);border-bottom:1px solid #dddddf;padding-bottom:8px;margin-top:0;padding-top:1rem;margin-bottom:1.25rem}
 157 #toc{border-bottom:1px solid #e7e7e9;padding-bottom:.5em}
 158 #toc>ul{margin-left:.125em}
 159 #toc ul.sectlevel0>li>a{font-style:italic}
 160 #toc ul.sectlevel0 ul.sectlevel1{margin:.5em 0}
 161 #toc ul{font-family:"Open Sans","DejaVu Sans",sans-serif;list-style-type:none}
 162 #toc li{line-height:1.3334;margin-top:.3334em}
 163 #toc a{text-decoration:none}
 164 #toc a:active{text-decoration:underline}
 165 #toctitle{color:#7a2518;font-size:1.2em}
 166 @media screen and (min-width:768px){#toctitle{font-size:1.375em}
 167 body.toc2{padding-left:15em;padding-right:0}
 168 #toc.toc2{margin-top:0!important;background-color:#f8f8f7;position:fixed;width:15em;left:0;top:0;border-right:1px solid #e7e7e9;border-top-width:0!important;border-bottom-width:0!important;z-index:1000;padding:1.25em 1em;height:100%;overflow:auto}
 169 #toc.toc2 #toctitle{margin-top:0;margin-bottom:.8rem;font-size:1.2em}
 170 #toc.toc2>ul{font-size:.9em;margin-bottom:0}
 171 #toc.toc2 ul ul{margin-left:0;padding-left:1em}
 172 #toc.toc2 ul.sectlevel0 ul.sectlevel1{padding-left:0;margin-top:.5em;margin-bottom:.5em}
 173 body.toc2.toc-right{padding-left:0;padding-right:15em}
 174 body.toc2.toc-right #toc.toc2{border-right-width:0;border-left:1px solid #e7e7e9;left:auto;right:0}}
 175 @media screen and (min-width:1280px){body.toc2{padding-left:20em;padding-right:0}
 176 #toc.toc2{width:20em}
 177 #toc.toc2 #toctitle{font-size:1.375em}
 178 #toc.toc2>ul{font-size:.95em}
 179 #toc.toc2 ul ul{padding-left:1.25em}
 180 body.toc2.toc-right{padding-left:0;padding-right:20em}}
 181 #content #toc{border-style:solid;border-width:1px;border-color:#e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;-webkit-border-radius:4px;border-radius:4px}
 182 #content #toc>:first-child{margin-top:0}
 183 #content #toc>:last-child{margin-bottom:0}
 184 #footer{max-width:100%;background-color:rgba(0,0,0,.8);padding:1.25em}
 185 #footer-text{color:rgba(255,255,255,.8);line-height:1.44}
 186 #content{margin-bottom:.625em}
 187 .sect1{padding-bottom:.625em}
 188 @media screen and (min-width:768px){#content{margin-bottom:1.25em}
 189 .sect1{padding-bottom:1.25em}}
 190 .sect1:last-child{padding-bottom:0}
 191 .sect1+.sect1{border-top:1px solid #e7e7e9}
 192 #content h1>a.anchor,h2>a.anchor,h3>a.anchor,#toctitle>a.anchor,.sidebarblock>.content>.title>a.anchor,h4>a.anchor,h5>a.anchor,h6>a.anchor{position:absolute;z-index:1001;width:1.5ex;margin-left:-1.5ex;display:block;text-decoration:none!important;visibility:hidden;text-align:center;font-weight:400}
 193 #content h1>a.anchor::before,h2>a.anchor::before,h3>a.anchor::before,#toctitle>a.anchor::before,.sidebarblock>.content>.title>a.anchor::before,h4>a.anchor::before,h5>a.anchor::before,h6>a.anchor::before{content:"\00A7";font-size:.85em;display:block;padding-top:.1em}
 194 #content h1:hover>a.anchor,#content h1>a.anchor:hover,h2:hover>a.anchor,h2>a.anchor:hover,h3:hover>a.anchor,#toctitle:hover>a.anchor,.sidebarblock>.content>.title:hover>a.anchor,h3>a.anchor:hover,#toctitle>a.anchor:hover,.sidebarblock>.content>.title>a.anchor:hover,h4:hover>a.anchor,h4>a.anchor:hover,h5:hover>a.anchor,h5>a.anchor:hover,h6:hover>a.anchor,h6>a.anchor:hover{visibility:visible}
 195 #content h1>a.link,h2>a.link,h3>a.link,#toctitle>a.link,.sidebarblock>.content>.title>a.link,h4>a.link,h5>a.link,h6>a.link{color:#ba3925;text-decoration:none}
 196 #content h1>a.link:hover,h2>a.link:hover,h3>a.link:hover,#toctitle>a.link:hover,.sidebarblock>.content>.title>a.link:hover,h4>a.link:hover,h5>a.link:hover,h6>a.link:hover{color:#a53221}
 197 .audioblock,.imageblock,.literalblock,.listingblock,.stemblock,.videoblock{margin-bottom:1.25em}
 198 .admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{text-rendering:optimizeLegibility;text-align:left;font-family:"Noto Serif","DejaVu Serif",serif;font-size:1rem;font-style:italic}
 199 table.tableblock.fit-content>caption.title{white-space:nowrap;width:0}
 200 .paragraph.lead>p,#preamble>.sectionbody>[class="paragraph"]:first-of-type p{font-size:1.21875em;line-height:1.6;color:rgba(0,0,0,.85)}
 201 table.tableblock #preamble>.sectionbody>[class="paragraph"]:first-of-type p{font-size:inherit}
 202 .admonitionblock>table{border-collapse:separate;border:0;background:none;width:100%}
 203 .admonitionblock>table td.icon{text-align:center;width:80px}
 204 .admonitionblock>table td.icon img{max-width:none}
 205 .admonitionblock>table td.icon .title{font-weight:bold;font-family:"Open Sans","DejaVu Sans",sans-serif;text-transform:uppercase}
 206 .admonitionblock>table td.content{padding-left:1.125em;padding-right:1.25em;border-left:1px solid #dddddf;color:rgba(0,0,0,.6)}
 207 .admonitionblock>table td.content>:last-child>:last-child{margin-bottom:0}
 208 .exampleblock>.content{border-style:solid;border-width:1px;border-color:#e6e6e6;margin-bottom:1.25em;padding:1.25em;background:#fff;-webkit-border-radius:4px;border-radius:4px}
 209 .exampleblock>.content>:first-child{margin-top:0}
 210 .exampleblock>.content>:last-child{margin-bottom:0}
 211 .sidebarblock{border-style:solid;border-width:1px;border-color:#e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;-webkit-border-radius:4px;border-radius:4px}
 212 .sidebarblock>:first-child{margin-top:0}
 213 .sidebarblock>:last-child{margin-bottom:0}
 214 .sidebarblock>.content>.title{color:#7a2518;margin-top:0;text-align:center}
 215 .exampleblock>.content>:last-child>:last-child,.exampleblock>.content .olist>ol>li:last-child>:last-child,.exampleblock>.content .ulist>ul>li:last-child>:last-child,.exampleblock>.content .qlist>ol>li:last-child>:last-child,.sidebarblock>.content>:last-child>:last-child,.sidebarblock>.content .olist>ol>li:last-child>:last-child,.sidebarblock>.content .ulist>ul>li:last-child>:last-child,.sidebarblock>.content .qlist>ol>li:last-child>:last-child{margin-bottom:0}
 216 .literalblock pre,.listingblock pre:not(.highlight),.listingblock pre[class="highlight"],.listingblock pre[class^="highlight "],.listingblock pre.CodeRay,.listingblock pre.prettyprint{background:#f7f7f8}
 217 .sidebarblock .literalblock pre,.sidebarblock .listingblock pre:not(.highlight),.sidebarblock .listingblock pre[class="highlight"],.sidebarblock .listingblock pre[class^="highlight "],.sidebarblock .listingblock pre.CodeRay,.sidebarblock .listingblock pre.prettyprint{background:#f2f1f1}
 218 .literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{-webkit-border-radius:4px;border-radius:4px;word-wrap:break-word;overflow-x:auto;padding:1em;font-size:.8125em}
 219 @media screen and (min-width:768px){.literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{font-size:.90625em}}
 220 @media screen and (min-width:1280px){.literalblock pre,.literalblock pre[class],.listingblock pre,.listingblock pre[class]{font-size:1em}}
 221 .literalblock pre.nowrap,.literalblock pre.nowrap pre,.listingblock pre.nowrap,.listingblock pre.nowrap pre{white-space:pre;word-wrap:normal}
 222 .literalblock.output pre{color:#f7f7f8;background-color:rgba(0,0,0,.9)}
 223 .listingblock pre.highlightjs{padding:0}
 224 .listingblock pre.highlightjs>code{padding:1em;-webkit-border-radius:4px;border-radius:4px}
 225 .listingblock pre.prettyprint{border-width:0}
 226 .listingblock>.content{position:relative}
 227 .listingblock code[data-lang]::before{display:none;content:attr(data-lang);position:absolute;font-size:.75em;top:.425rem;right:.5rem;line-height:1;text-transform:uppercase;color:#999}
 228 .listingblock:hover code[data-lang]::before{display:block}
 229 .listingblock.terminal pre .command::before{content:attr(data-prompt);padding-right:.5em;color:#999}
 230 .listingblock.terminal pre .command:not([data-prompt])::before{content:"$"}
 231 table.pyhltable{border-collapse:separate;border:0;margin-bottom:0;background:none}
 232 table.pyhltable td{vertical-align:top;padding-top:0;padding-bottom:0;line-height:1.45}
 233 table.pyhltable td.code{padding-left:.75em;padding-right:0}
 234 pre.pygments .lineno,table.pyhltable td:not(.code){color:#999;padding-left:0;padding-right:.5em;border-right:1px solid #dddddf}
 235 pre.pygments .lineno{display:inline-block;margin-right:.25em}
 236 table.pyhltable .linenodiv{background:none!important;padding-right:0!important}
 237 .quoteblock{margin:0 1em 1.25em 1.5em;display:table}
 238 .quoteblock>.title{margin-left:-1.5em;margin-bottom:.75em}
 239 .quoteblock blockquote,.quoteblock p{color:rgba(0,0,0,.85);font-size:1.15rem;line-height:1.75;word-spacing:.1em;letter-spacing:0;font-style:italic;text-align:justify}
 240 .quoteblock blockquote{margin:0;padding:0;border:0}
 241 .quoteblock blockquote::before{content:"\201c";float:left;font-size:2.75em;font-weight:bold;line-height:.6em;margin-left:-.6em;color:#7a2518;text-shadow:0 1px 2px rgba(0,0,0,.1)}
 242 .quoteblock blockquote>.paragraph:last-child p{margin-bottom:0}
 243 .quoteblock .attribution{margin-top:.75em;margin-right:.5ex;text-align:right}
 244 .verseblock{margin:0 1em 1.25em}
 245 .verseblock pre{font-family:"Open Sans","DejaVu Sans",sans;font-size:1.15rem;color:rgba(0,0,0,.85);font-weight:300;text-rendering:optimizeLegibility}
 246 .verseblock pre strong{font-weight:400}
 247 .verseblock .attribution{margin-top:1.25rem;margin-left:.5ex}
 248 .quoteblock .attribution,.verseblock .attribution{font-size:.9375em;line-height:1.45;font-style:italic}
 249 .quoteblock .attribution br,.verseblock .attribution br{display:none}
 250 .quoteblock .attribution cite,.verseblock .attribution cite{display:block;letter-spacing:-.025em;color:rgba(0,0,0,.6)}
 251 .quoteblock.abstract blockquote::before,.quoteblock.excerpt blockquote::before,.quoteblock .quoteblock blockquote::before{display:none}
 252 .quoteblock.abstract blockquote,.quoteblock.abstract p,.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{line-height:1.6;word-spacing:0}
 253 .quoteblock.abstract{margin:0 1em 1.25em;display:block}
 254 .quoteblock.abstract>.title{margin:0 0 .375em;font-size:1.15em;text-align:center}
 255 .quoteblock.excerpt,.quoteblock .quoteblock{margin:0 0 1.25em;padding:0 0 .25em 1em;border-left:.25em solid #dddddf}
 256 .quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{color:inherit;font-size:1.0625rem}
 257 .quoteblock.excerpt .attribution,.quoteblock .quoteblock .attribution{color:inherit;text-align:left;margin-right:0}
 258 table.tableblock{max-width:100%;border-collapse:separate}
 259 p.tableblock:last-child{margin-bottom:0}
 260 td.tableblock>.content{margin-bottom:-1.25em}
 261 table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede}
 262 table.grid-all>thead>tr>.tableblock,table.grid-all>tbody>tr>.tableblock{border-width:0 1px 1px 0}
 263 table.grid-all>tfoot>tr>.tableblock{border-width:1px 1px 0 0}
 264 table.grid-cols>*>tr>.tableblock{border-width:0 1px 0 0}
 265 table.grid-rows>thead>tr>.tableblock,table.grid-rows>tbody>tr>.tableblock{border-width:0 0 1px}
 266 table.grid-rows>tfoot>tr>.tableblock{border-width:1px 0 0}
 267 table.grid-all>*>tr>.tableblock:last-child,table.grid-cols>*>tr>.tableblock:last-child{border-right-width:0}
 268 table.grid-all>tbody>tr:last-child>.tableblock,table.grid-all>thead:last-child>tr>.tableblock,table.grid-rows>tbody>tr:last-child>.tableblock,table.grid-rows>thead:last-child>tr>.tableblock{border-bottom-width:0}
 269 table.frame-all{border-width:1px}
 270 table.frame-sides{border-width:0 1px}
 271 table.frame-topbot,table.frame-ends{border-width:1px 0}
 272 table.stripes-all tr,table.stripes-odd tr:nth-of-type(odd){background:#f8f8f7}
 273 table.stripes-none tr,table.stripes-odd tr:nth-of-type(even){background:none}
 274 th.halign-left,td.halign-left{text-align:left}
 275 th.halign-right,td.halign-right{text-align:right}
 276 th.halign-center,td.halign-center{text-align:center}
 277 th.valign-top,td.valign-top{vertical-align:top}
 278 th.valign-bottom,td.valign-bottom{vertical-align:bottom}
 279 th.valign-middle,td.valign-middle{vertical-align:middle}
 280 table thead th,table tfoot th{font-weight:bold}
 281 tbody tr th{display:table-cell;line-height:1.6;background:#f7f8f7}
 282 tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold}
 283 p.tableblock>code:only-child{background:none;padding:0}
 284 p.tableblock{font-size:1em}
 285 td>div.verse{white-space:pre}
 286 ol{margin-left:1.75em}
 287 ul li ol{margin-left:1.5em}
 288 dl dd{margin-left:1.125em}
 289 dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0}
 290 ol>li p,ul>li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em}
 291 ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none}
 292 ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em}
 293 ul.unstyled,ol.unstyled{margin-left:0}
 294 ul.checklist{margin-left:.625em}
 295 ul.checklist li>p:first-child>.fa-square-o:first-child,ul.checklist li>p:first-child>.fa-check-square-o:first-child{width:1.25em;font-size:.8em;position:relative;bottom:.125em}
 296 ul.checklist li>p:first-child>input[type="checkbox"]:first-child{margin-right:.25em}
 297 ul.inline{display:-ms-flexbox;display:-webkit-box;display:flex;-ms-flex-flow:row wrap;-webkit-flex-flow:row wrap;flex-flow:row wrap;list-style:none;margin:0 0 .625em -1.25em}
 298 ul.inline>li{margin-left:1.25em}
 299 .unstyled dl dt{font-weight:400;font-style:normal}
 300 ol.arabic{list-style-type:decimal}
 301 ol.decimal{list-style-type:decimal-leading-zero}
 302 ol.loweralpha{list-style-type:lower-alpha}
 303 ol.upperalpha{list-style-type:upper-alpha}
 304 ol.lowerroman{list-style-type:lower-roman}
 305 ol.upperroman{list-style-type:upper-roman}
 306 ol.lowergreek{list-style-type:lower-greek}
 307 .hdlist>table,.colist>table{border:0;background:none}
 308 .hdlist>table>tbody>tr,.colist>table>tbody>tr{background:none}
 309 td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em}
 310 td.hdlist1{font-weight:bold;padding-bottom:1.25em}
 311 .literalblock+.colist,.listingblock+.colist{margin-top:-.5em}
 312 .colist td:not([class]):first-child{padding:.4em .75em 0;line-height:1;vertical-align:top}
 313 .colist td:not([class]):first-child img{max-width:none}
 314 .colist td:not([class]):last-child{padding:.25em 0}
 315 .thumb,.th{line-height:0;display:inline-block;border:solid 4px #fff;-webkit-box-shadow:0 0 0 1px #ddd;box-shadow:0 0 0 1px #ddd}
 316 .imageblock.left{margin:.25em .625em 1.25em 0}
 317 .imageblock.right{margin:.25em 0 1.25em .625em}
 318 .imageblock>.title{margin-bottom:0}
 319 .imageblock.thumb,.imageblock.th{border-width:6px}
 320 .imageblock.thumb>.title,.imageblock.th>.title{padding:0 .125em}
 321 .image.left,.image.right{margin-top:.25em;margin-bottom:.25em;display:inline-block;line-height:0}
 322 .image.left{margin-right:.625em}
 323 .image.right{margin-left:.625em}
 324 a.image{text-decoration:none;display:inline-block}
 325 a.image object{pointer-events:none}
 326 sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super}
 327 sup.footnote a,sup.footnoteref a{text-decoration:none}
 328 sup.footnote a:active,sup.footnoteref a:active{text-decoration:underline}
 329 #footnotes{padding-top:.75em;padding-bottom:.75em;margin-bottom:.625em}
 330 #footnotes hr{width:20%;min-width:6.25em;margin:-.25em 0 .75em;border-width:1px 0 0}
 331 #footnotes .footnote{padding:0 .375em 0 .225em;line-height:1.3334;font-size:.875em;margin-left:1.2em;margin-bottom:.2em}
 332 #footnotes .footnote a:first-of-type{font-weight:bold;text-decoration:none;margin-left:-1.05em}
 333 #footnotes .footnote:last-of-type{margin-bottom:0}
 334 #content #footnotes{margin-top:-.625em;margin-bottom:0;padding:.75em 0}
 335 .gist .file-data>table{border:0;background:#fff;width:100%;margin-bottom:0}
 336 .gist .file-data>table td.line-data{width:99%}
 337 div.unbreakable{page-break-inside:avoid}
 338 .big{font-size:larger}
 339 .small{font-size:smaller}
 340 .underline{text-decoration:underline}
 341 .overline{text-decoration:overline}
 342 .line-through{text-decoration:line-through}
 343 .aqua{color:#00bfbf}
 344 .aqua-background{background-color:#00fafa}
 345 .black{color:#000}
 346 .black-background{background-color:#000}
 347 .blue{color:#0000bf}
 348 .blue-background{background-color:#0000fa}
 349 .fuchsia{color:#bf00bf}
 350 .fuchsia-background{background-color:#fa00fa}
 351 .gray{color:#606060}
 352 .gray-background{background-color:#7d7d7d}
 353 .green{color:#006000}
 354 .green-background{background-color:#007d00}
 355 .lime{color:#00bf00}
 356 .lime-background{background-color:#00fa00}
 357 .maroon{color:#600000}
 358 .maroon-background{background-color:#7d0000}
 359 .navy{color:#000060}
 360 .navy-background{background-color:#00007d}
 361 .olive{color:#606000}
 362 .olive-background{background-color:#7d7d00}
 363 .purple{color:#600060}
 364 .purple-background{background-color:#7d007d}
 365 .red{color:#bf0000}
 366 .red-background{background-color:#fa0000}
 367 .silver{color:#909090}
 368 .silver-background{background-color:#bcbcbc}
 369 .teal{color:#006060}
 370 .teal-background{background-color:#007d7d}
 371 .white{color:#bfbfbf}
 372 .white-background{background-color:#fafafa}
 373 .yellow{color:#bfbf00}
 374 .yellow-background{background-color:#fafa00}
 375 span.icon>.fa{cursor:default}
 376 a span.icon>.fa{cursor:inherit}
 377 .admonitionblock td.icon [class^="fa icon-"]{font-size:2.5em;text-shadow:1px 1px 2px rgba(0,0,0,.5);cursor:default}
 378 .admonitionblock td.icon .icon-note::before{content:"\f05a";color:#19407c}
 379 .admonitionblock td.icon .icon-tip::before{content:"\f0eb";text-shadow:1px 1px 2px rgba(155,155,0,.8);color:#111}
 380 .admonitionblock td.icon .icon-warning::before{content:"\f071";color:#bf6900}
 381 .admonitionblock td.icon .icon-caution::before{content:"\f06d";color:#bf3400}
 382 .admonitionblock td.icon .icon-important::before{content:"\f06a";color:#bf0000}
 383 .conum[data-value]{display:inline-block;color:#fff!important;background-color:rgba(0,0,0,.8);-webkit-border-radius:100px;border-radius:100px;text-align:center;font-size:.75em;width:1.67em;height:1.67em;line-height:1.67em;font-family:"Open Sans","DejaVu Sans",sans-serif;font-style:normal;font-weight:bold}
 384 .conum[data-value] *{color:#fff!important}
 385 .conum[data-value]+b{display:none}
 386 .conum[data-value]::after{content:attr(data-value)}
 387 pre .conum[data-value]{position:relative;top:-.125em}
 388 b.conum *{color:inherit!important}
 389 .conum:not([data-value]):empty{display:none}
 390 dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility}
 391 h1,h2,p,td.content,span.alt{letter-spacing:-.01em}
 392 p strong,td.content strong,div.footnote strong{letter-spacing:-.005em}
 393 p,blockquote,dt,td.content,span.alt{font-size:1.0625rem}
 394 p{margin-bottom:1.25rem}
 395 .sidebarblock p,.sidebarblock dt,.sidebarblock td.content,p.tableblock{font-size:1em}
 396 .exampleblock>.content{background-color:#fffef7;border-color:#e0e0dc;-webkit-box-shadow:0 1px 4px #e0e0dc;box-shadow:0 1px 4px #e0e0dc}
 397 .print-only{display:none!important}
 398 @page{margin:1.25cm .75cm}
 399 @media print{*{-webkit-box-shadow:none!important;box-shadow:none!important;text-shadow:none!important}
 400 html{font-size:80%}
 401 a{color:inherit!important;text-decoration:underline!important}
 402 a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important}
 403 a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em}
 404 abbr[title]::after{content:" (" attr(title) ")"}
 405 pre,blockquote,tr,img,object,svg{page-break-inside:avoid}
 406 thead{display:table-header-group}
 407 svg{max-width:100%}
 408 p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3}
 409 h2,h3,#toctitle,.sidebarblock>.content>.title{page-break-after:avoid}
 410 #toc,.sidebarblock,.exampleblock>.content{background:none!important}
 411 #toc{border-bottom:1px solid #dddddf!important;padding-bottom:0!important}
 412 body.book #header{text-align:center}
 413 body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em}
 414 body.book #header .details{border:0!important;display:block;padding:0!important}
 415 body.book #header .details span:first-child{margin-left:0!important}
 416 body.book #header .details br{display:block}
 417 body.book #header .details br+span::before{content:none!important}
 418 body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important}
 419 body.book #toc,body.book #preamble,body.book h1.sect0,body.book .sect1>h2{page-break-before:always}
 420 .listingblock code[data-lang]::before{display:block}
 421 #footer{padding:0 .9375em}
 422 .hide-on-print{display:none!important}
 423 .print-only{display:block!important}
 424 .hide-for-print{display:none!important}
 425 .show-for-print{display:inherit!important}}
 426 @media print,amzn-kf8{#header>h1:first-child{margin-top:1.25rem}
 427 .sect1{padding:0!important}
 428 .sect1+.sect1{border:0}
 429 #footer{background:none}
 430 #footer-text{color:rgba(0,0,0,.6);font-size:.9em}}
 431 @media amzn-kf8{#header,#content,#footnotes,#footer{padding:0}}
 432 </style>
 433 </head>
 434 <body class="article toc2 toc-left">
 435 <div id="header">
 436 <h1>Simple C&#43;&#43;11 metaprogramming, part 2</h1>
 437 <div class="details">
 438 <span id="author" class="author">Peter Dimov</span><br>
 439 <span id="revdate">2015-06-20</span>
 440 </div>
 441 <div id="toc" class="toc2">
 442 <div id="toctitle">Table of Contents</div>
 443 <ul class="sectlevel1">
 444 <li><a href="#vectors_sets_and_maps">Vectors, sets, and maps</a></li>
 445 <li><a href="#mp_contains">mp_contains</a></li>
 446 <li><a href="#mp_map_find">mp_map_find</a></li>
 447 <li><a href="#mp_at">mp_at</a></li>
 448 <li><a href="#mp_drop">mp_drop</a></li>
 449 <li><a href="#mp_find_index">mp_find_index</a></li>
 450 <li><a href="#conclusion">Conclusion</a></li>
 451 </ul>
 452 </div>
 453 </div>
 454 <div id="content">
 455 <div id="preamble">
 456 <div class="sectionbody">
 457 <div class="paragraph lead">
 458 <p><em>Efficient algorithms for membership testing, random access, and retrieval by
 459 key</em></p>
 460 </div>
 461 <div class="admonitionblock note">
 462 <table>
 463 <tr>
 464 <td class="icon">
 465 <div class="title">Note</div>
 466 </td>
 467 <td class="content">
 468 Being late to the metaprogramming party, I make no claim of having
 469 invented the techniques in this article. A quick look at the implementations
 470 of, for example, Louis Dionne&#8217;s <a href="https://github.com/ldionne/mpl11">mpl11</a> and
 471 Eric Niebler&#8217;s <a href="https://github.com/ericniebler/meta">meta</a>, shows that most of
 472 these tricks are already known. Dave Abrahams
 473 <a href="https://github.com/dabrahams/mpl11">has experimented</a> along these lines in 2012.
 474 The original inventor of the multiple inheritance trick and the <code>void*</code>
 475 arguments trick is probably Richard Smith, who has posted
 476 <a href="https://llvm.org/bugs/attachment.cgi?id=8825">two</a>
 477 <a href="https://llvm.org/bugs/attachment.cgi?id=8838">examples</a> in response to
 478 <a href="https://llvm.org/bugs/show_bug.cgi?id=13263">a Clang bug report</a>.
 479 </td>
 480 </tr>
 481 </table>
 482 </div>
 483 </div>
 484 </div>
 485 <div class="sect1">
 486 <h2 id="vectors_sets_and_maps">Vectors, sets, and maps</h2>
 487 <div class="sectionbody">
 488 <div class="paragraph">
 489 <p><a href="simple_cxx11_metaprogramming.html">Last time</a>, I outlined a style of
 490 metaprogramming that operated on type lists&#8201;&#8212;&#8201;variadic class templates:</p>
 491 </div>
 492 <div class="listingblock">
 493 <div class="content">
 494 <pre class="highlight"><code>template&lt;class... T&gt; struct mp_list {};</code></pre>
 495 </div>
 496 </div>
 497 <div class="paragraph">
 498 <p>Classic Lisp uses lists as its only data structure, but operating on a list is
 499 usually linear in the number of its elements.</p>
 500 </div>
 501 <div class="paragraph">
 502 <p>In addition to <code>list</code>, the STL has <code>vector</code>, <code>set</code>, and <code>map</code>. <code>vector</code>
 503 supports random access by index; <code>set</code> has efficient test for membership; <code>map</code>
 504 associates keys with values and has efficient lookup based on key.</p>
 505 </div>
 506 <div class="paragraph">
 507 <p>Instead of introducing separate data structure such as <code>mp_vector</code>, <code>mp_set</code>,
 508 <code>mp_map</code>, we&#8217;ll keep our data in a list form, and attempt to provide efficient
 509 algorithms for random access, membership testing, and lookup.</p>
 510 </div>
 511 </div>
 512 </div>
 513 <div class="sect1">
 514 <h2 id="mp_contains">mp_contains</h2>
 515 <div class="sectionbody">
 516 <div class="paragraph">
 517 <p>Let&#8217;s starts with sets. A set is just a list with unique elements. To obtain a
 518 set from an arbitrary list, we&#8217;ll need an algorithm that removes the
 519 duplicates. Let&#8217;s call it <code>mp_unique&lt;L&gt;</code>:</p>
 520 </div>
 521 <div class="listingblock">
 522 <div class="content">
 523 <pre class="highlight"><code>// mp_if
 524
 525 template&lt;bool C, class T, class E&gt; struct mp_if_c_impl;
 526
 527 template&lt;class T, class E&gt; struct mp_if_c_impl&lt;true, T, E&gt;
 528 {
 529     using type = T;
 530 };
 531
 532 template&lt;class T, class E&gt; struct mp_if_c_impl&lt;false, T, E&gt;
 533 {
 534     using type = E;
 535 };
 536
 537 template&lt;bool C, class T, class E&gt;
 538     using mp_if_c = typename mp_if_c_impl&lt;C, T, E&gt;::type;
 539
 540 template&lt;class C, class T, class E&gt;
 541     using mp_if = typename mp_if_c_impl&lt;C::value != 0, T, E&gt;::type;
 542
 543 // mp_unique
 544
 545 template&lt;class L&gt; struct mp_unique_impl;
 546
 547 template&lt;class L&gt; using mp_unique = typename mp_unique_impl&lt;L&gt;::type;
 548
 549 template&lt;template&lt;class...&gt; class L&gt; struct mp_unique_impl&lt;L&lt;&gt;&gt;
 550 {
 551     using type = L&lt;&gt;;
 552 };
 553
 554 template&lt;template&lt;class...&gt; class L, class T1, class... T&gt;
 555     struct mp_unique_impl&lt;L&lt;T1, T...&gt;&gt;
 556 {
 557     using _rest = mp_unique&lt;L&lt;T...&gt;&gt;;
 558     using type = mp_if&lt;<strong>mp_contains</strong>&lt;_rest, T1&gt;, _rest, mp_push_front&lt;_rest, T1&gt;&gt;;
 559 };</code></pre>
 560 </div>
 561 </div>
 562 <div class="paragraph">
 563 <p>For membership testing, we&#8217;ve introduced an algorithm <code>mp_contains&lt;L, V&gt;</code> that
 564 returns <code>true</code> when <code>L</code> contains <code>V</code>. The straightforward recursive
 565 implementation of <code>mp_contains</code> is:</p>
 566 </div>
 567 <div class="listingblock">
 568 <div class="content">
 569 <pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_contains_impl;
 570
 571 template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;
 572
 573 template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_contains_impl&lt;L&lt;&gt;, V&gt;
 574 {
 575     using type = std::false_type;
 576 };
 577
 578 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
 579     struct mp_contains_impl&lt;L&lt;V, T...&gt;, V&gt;
 580 {
 581     using type = std::true_type;
 582 };
 583
 584 template&lt;template&lt;class...&gt; class L, class T1, class... T, class V&gt;
 585     struct mp_contains_impl&lt;L&lt;T1, T...&gt;, V&gt;: mp_contains_impl&lt;L&lt;T...&gt;, V&gt;
 586 {
 587 };</code></pre>
 588 </div>
 589 </div>
 590 <div class="paragraph">
 591 <p>Note that <code>mp_unique&lt;L&gt;</code> makes <code>N</code> calls to <code>mp_contains</code>, where <code>N</code> is the
 592 length of the list <code>L</code>. This means that <code>mp_contains</code> needs to be as fast as
 593 possible, which the above implementation, well, isn&#8217;t.</p>
 594 </div>
 595 <div class="paragraph">
 596 <p>Here are the compile times in seconds for invoking <code>mp_unique</code> on a list with
 597 <code>N</code> (distinct) elements:</p>
 598 </div>
 599 <table class="tableblock frame-all grid-all stretch">
 600 <colgroup>
 601 <col style="width: 11.1111%;">
 602 <col style="width: 11.1111%;">
 603 <col style="width: 11.1111%;">
 604 <col style="width: 11.1111%;">
 605 <col style="width: 11.1111%;">
 606 <col style="width: 11.1111%;">
 607 <col style="width: 11.1111%;">
 608 <col style="width: 11.1111%;">
 609 <col style="width: 11.1112%;">
 610 </colgroup>
 611 <thead>
 612 <tr>
 613 <th class="tableblock halign-left valign-top"></th>
 614 <th class="tableblock halign-left valign-top">N=100</th>
 615 <th class="tableblock halign-left valign-top">N=200</th>
 616 <th class="tableblock halign-left valign-top">N=300</th>
 617 <th class="tableblock halign-left valign-top">N=400</th>
 618 <th class="tableblock halign-left valign-top">N=500</th>
 619 <th class="tableblock halign-left valign-top">N=600</th>
 620 <th class="tableblock halign-left valign-top">N=700</th>
 621 <th class="tableblock halign-left valign-top">N=800</th>
 622 </tr>
 623 </thead>
 624 <tbody>
 625 <tr>
 626 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
 627 <td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
 628 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 629 <td class="tableblock halign-left valign-top"></td>
 630 <td class="tableblock halign-left valign-top"></td>
 631 <td class="tableblock halign-left valign-top"></td>
 632 <td class="tableblock halign-left valign-top"></td>
 633 <td class="tableblock halign-left valign-top"></td>
 634 <td class="tableblock halign-left valign-top"></td>
 635 </tr>
 636 <tr>
 637 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
 638 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
 639 <td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
 640 <td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
 641 <td class="tableblock halign-left valign-top"><p class="tableblock">30.2</p></td>
 642 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 643 <td class="tableblock halign-left valign-top"></td>
 644 <td class="tableblock halign-left valign-top"></td>
 645 <td class="tableblock halign-left valign-top"></td>
 646 </tr>
 647 <tr>
 648 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
 649 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
 650 <td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
 651 <td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
 652 <td class="tableblock halign-left valign-top"><p class="tableblock">23.2</p></td>
 653 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 654 <td class="tableblock halign-left valign-top"></td>
 655 <td class="tableblock halign-left valign-top"></td>
 656 <td class="tableblock halign-left valign-top"></td>
 657 </tr>
 658 </tbody>
 659 </table>
 660 <div class="paragraph">
 661 <p>(Tests done under Windows/Cygwin. All compilers are 32 bit. No optimizations.
 662 DNF stands for "did not finish", which usually means that the compiler ran out
 663 of heap space or crashed.)</p>
 664 </div>
 665 <div class="paragraph">
 666 <p>We clearly need a better alternative.</p>
 667 </div>
 668 <div class="paragraph">
 669 <p>I ended the previous article with an implementation of <code>mp_contains</code> that
 670 relied on <code>mp_count</code>, which in turn relied on <code>mp_plus</code>. Let&#8217;s see how it
 671 fares:</p>
 672 </div>
 673 <table class="tableblock frame-all grid-all stretch">
 674 <colgroup>
 675 <col style="width: 11.1111%;">
 676 <col style="width: 11.1111%;">
 677 <col style="width: 11.1111%;">
 678 <col style="width: 11.1111%;">
 679 <col style="width: 11.1111%;">
 680 <col style="width: 11.1111%;">
 681 <col style="width: 11.1111%;">
 682 <col style="width: 11.1111%;">
 683 <col style="width: 11.1112%;">
 684 </colgroup>
 685 <thead>
 686 <tr>
 687 <th class="tableblock halign-left valign-top"></th>
 688 <th class="tableblock halign-left valign-top">N=100</th>
 689 <th class="tableblock halign-left valign-top">N=200</th>
 690 <th class="tableblock halign-left valign-top">N=300</th>
 691 <th class="tableblock halign-left valign-top">N=400</th>
 692 <th class="tableblock halign-left valign-top">N=500</th>
 693 <th class="tableblock halign-left valign-top">N=600</th>
 694 <th class="tableblock halign-left valign-top">N=700</th>
 695 <th class="tableblock halign-left valign-top">N=800</th>
 696 </tr>
 697 </thead>
 698 <tbody>
 699 <tr>
 700 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, mp_count/mp_plus</p></td>
 701 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
 702 <td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
 703 <td class="tableblock halign-left valign-top"><p class="tableblock">50.5</p></td>
 704 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 705 <td class="tableblock halign-left valign-top"></td>
 706 <td class="tableblock halign-left valign-top"></td>
 707 <td class="tableblock halign-left valign-top"></td>
 708 <td class="tableblock halign-left valign-top"></td>
 709 </tr>
 710 <tr>
 711 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/mp_plus</p></td>
 712 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
 713 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
 714 <td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
 715 <td class="tableblock halign-left valign-top"><p class="tableblock">6.1</p></td>
 716 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 717 <td class="tableblock halign-left valign-top"></td>
 718 <td class="tableblock halign-left valign-top"></td>
 719 <td class="tableblock halign-left valign-top"></td>
 720 </tr>
 721 <tr>
 722 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/mp_plus</p></td>
 723 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
 724 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
 725 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
 726 <td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
 727 <td class="tableblock halign-left valign-top"><p class="tableblock">9.7</p></td>
 728 <td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
 729 <td class="tableblock halign-left valign-top"><p class="tableblock">22.4</p></td>
 730 <td class="tableblock halign-left valign-top"><p class="tableblock">32.3</p></td>
 731 </tr>
 732 </tbody>
 733 </table>
 734 <div class="paragraph">
 735 <p>Not <em>that</em> bad, at least if your compiler happens to be <code>g++</code>. Still, there
 736 ought to be room for improvement here.</p>
 737 </div>
 738 <div class="paragraph">
 739 <p>To do better, we have to somehow leverage the language features, such as pack
 740 expansion, to do more of the work for us. For inspiration, let&#8217;s turn to
 741 section 14.5.3 paragraph 4 of the C&#43;&#43;11 standard, which explains that pack
 742 expansions can occur in the following contexts:</p>
 743 </div>
 744 <div class="ulist">
 745 <ul>
 746 <li>
 747 <p><strong>In a function parameter pack (8.3.5); the pattern is the
 748 <em>parameter-declaration</em> without the ellipsis.</strong></p>
 749 </li>
 750 <li>
 751 <p>In a template parameter pack that is a pack expansion (14.1):</p>
 752 </li>
 753 <li>
 754 <p><strong>In an <em>initializer-list</em> (8.5); the pattern is an
 755 <em>initializer-clause</em>.</strong></p>
 756 </li>
 757 <li>
 758 <p><strong>In a <em>base-specifier-list</em> (Clause 10); the pattern is a
 759 <em>base-specifier</em>.</strong></p>
 760 </li>
 761 <li>
 762 <p>In a <em>mem-initializer-list</em> (12.6.2); the pattern is a
 763 <em>mem-initializer</em>.</p>
 764 </li>
 765 <li>
 766 <p>In a <em>template-argument-list</em> (14.3); the pattern is a
 767 <em>template-argument</em>.</p>
 768 </li>
 769 <li>
 770 <p>In a <em>dynamic-exception-specification</em> (15.4); the pattern is a
 771 <em>type-id</em>.</p>
 772 </li>
 773 <li>
 774 <p>In an <em>attribute-list</em> (7.6.1); the pattern is an <em>attribute</em>.</p>
 775 </li>
 776 <li>
 777 <p>In an <em>alignment-specifier</em> (7.6.2); the pattern is the
 778 <em>alignment-specifier</em> without the ellipsis.</p>
 779 </li>
 780 <li>
 781 <p>In a <em>capture-list</em> (5.1.2); the pattern is a <em>capture</em>.</p>
 782 </li>
 783 <li>
 784 <p>In a <code>sizeof...</code> expression (5.3.3); the pattern is an <em>identifier</em>.</p>
 785 </li>
 786 </ul>
 787 </div>
 788 <div class="paragraph">
 789 <p>The <strong>emphasis</strong> is mine and indicates possible leads.</p>
 790 </div>
 791 <div class="paragraph">
 792 <p>Our first option is to expand the parameter pack into arguments for a function
 793 call. Since we&#8217;re interested in operations that occur at compile time, calling
 794 a function may not appear useful; but C&#43;&#43;11 functions can be <code>constexpr</code>, and
 795 <code>constexpr</code> function "calls" do occur at compile time.</p>
 796 </div>
 797 <div class="paragraph">
 798 <p>Recall our <code>mp_count</code>:</p>
 799 </div>
 800 <div class="listingblock">
 801 <div class="content">
 802 <pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_count_impl;
 803
 804 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
 805     struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
 806 {
 807     using type = mp_plus&lt;std::is_same&lt;T, V&gt;...&gt;;
 808 };
 809
 810 template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
 811 </div>
 812 </div>
 813 <div class="paragraph">
 814 <p>Instead of using the template alias <code>mp_plus</code> to sum the <code>is_same</code> expressions,
 815 we can use a <code>constexpr</code> function:</p>
 816 </div>
 817 <div class="listingblock">
 818 <div class="content">
 819 <pre class="highlight"><code>constexpr std::size_t cx_plus()
 820 {
 821     return 0;
 822 }
 823
 824 template&lt;class T1, class... T&gt; constexpr std::size_t cx_plus(T1 t1, T... t)
 825 {
 826     return t1 + cx_plus(t...);
 827 }
 828
 829 // mp_size_t
 830
 831 template&lt;std::size_t N&gt; using mp_size_t = std::integral_constant&lt;std::size_t, N&gt;;
 832
 833 // mp_count
 834
 835 template&lt;class L, class V&gt; struct mp_count_impl;
 836
 837 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
 838     struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
 839 {
 840     using type = mp_size_t&lt;cx_plus(std::is_same&lt;T, V&gt;::value...)&gt;;
 841 };
 842
 843 template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
 844 </div>
 845 </div>
 846 <div class="paragraph">
 847 <p>with the following results:</p>
 848 </div>
 849 <table class="tableblock frame-all grid-all stretch">
 850 <colgroup>
 851 <col style="width: 11.1111%;">
 852 <col style="width: 11.1111%;">
 853 <col style="width: 11.1111%;">
 854 <col style="width: 11.1111%;">
 855 <col style="width: 11.1111%;">
 856 <col style="width: 11.1111%;">
 857 <col style="width: 11.1111%;">
 858 <col style="width: 11.1111%;">
 859 <col style="width: 11.1112%;">
 860 </colgroup>
 861 <thead>
 862 <tr>
 863 <th class="tableblock halign-left valign-top"></th>
 864 <th class="tableblock halign-left valign-top">N=100</th>
 865 <th class="tableblock halign-left valign-top">N=200</th>
 866 <th class="tableblock halign-left valign-top">N=300</th>
 867 <th class="tableblock halign-left valign-top">N=400</th>
 868 <th class="tableblock halign-left valign-top">N=500</th>
 869 <th class="tableblock halign-left valign-top">N=600</th>
 870 <th class="tableblock halign-left valign-top">N=700</th>
 871 <th class="tableblock halign-left valign-top">N=800</th>
 872 </tr>
 873 </thead>
 874 <tbody>
 875 <tr>
 876 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus</p></td>
 877 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
 878 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
 879 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
 880 <td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
 881 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 882 <td class="tableblock halign-left valign-top"></td>
 883 <td class="tableblock halign-left valign-top"></td>
 884 <td class="tableblock halign-left valign-top"></td>
 885 </tr>
 886 <tr>
 887 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus</p></td>
 888 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
 889 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
 890 <td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
 891 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
 892 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
 893 <td class="tableblock halign-left valign-top"><p class="tableblock">6.7</p></td>
 894 <td class="tableblock halign-left valign-top"><p class="tableblock">9.2</p></td>
 895 <td class="tableblock halign-left valign-top"><p class="tableblock">11.8</p></td>
 896 </tr>
 897 </tbody>
 898 </table>
 899 <div class="paragraph">
 900 <p>We&#8217;ve improved the times, but lost VC++ 2013 due to its not implementing
 901 <code>constexpr</code>.</p>
 902 </div>
 903 <div class="paragraph">
 904 <p>Let&#8217;s try pack expansion into an <em>initializer-list</em>. Instead of passing the
 905 <code>is_same</code> expressions to a function, we can build a constant array out of them,
 906 then sum the array with a <code>constexpr</code> function:</p>
 907 </div>
 908 <div class="listingblock">
 909 <div class="content">
 910 <pre class="highlight"><code>constexpr std::size_t cx_plus2(bool const * first, bool const * last)
 911 {
 912     return first == last? 0: *first + cx_plus2(first + 1, last);
 913 }
 914
 915 // mp_count
 916
 917 template&lt;class L, class V&gt; struct mp_count_impl;
 918
 919 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
 920     struct mp_count_impl&lt;L&lt;T...&gt;, V&gt;
 921 {
 922     static constexpr bool _v[] = { std::is_same&lt;T, V&gt;::value... };
 923     using type = mp_size_t&lt;cx_plus2(_v, _v + sizeof...(T))&gt;;
 924 };
 925
 926 template&lt;class L, class V&gt; using mp_count = typename mp_count_impl&lt;L, V&gt;::type;</code></pre>
 927 </div>
 928 </div>
 929 <div class="paragraph">
 930 <p>This is a neat trick, but is it fast?</p>
 931 </div>
 932 <table class="tableblock frame-all grid-all stretch">
 933 <colgroup>
 934 <col style="width: 11.1111%;">
 935 <col style="width: 11.1111%;">
 936 <col style="width: 11.1111%;">
 937 <col style="width: 11.1111%;">
 938 <col style="width: 11.1111%;">
 939 <col style="width: 11.1111%;">
 940 <col style="width: 11.1111%;">
 941 <col style="width: 11.1111%;">
 942 <col style="width: 11.1112%;">
 943 </colgroup>
 944 <thead>
 945 <tr>
 946 <th class="tableblock halign-left valign-top"></th>
 947 <th class="tableblock halign-left valign-top">N=100</th>
 948 <th class="tableblock halign-left valign-top">N=200</th>
 949 <th class="tableblock halign-left valign-top">N=300</th>
 950 <th class="tableblock halign-left valign-top">N=400</th>
 951 <th class="tableblock halign-left valign-top">N=500</th>
 952 <th class="tableblock halign-left valign-top">N=600</th>
 953 <th class="tableblock halign-left valign-top">N=700</th>
 954 <th class="tableblock halign-left valign-top">N=800</th>
 955 </tr>
 956 </thead>
 957 <tbody>
 958 <tr>
 959 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus2</p></td>
 960 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
 961 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
 962 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
 963 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
 964 <td class="tableblock halign-left valign-top"></td>
 965 <td class="tableblock halign-left valign-top"></td>
 966 <td class="tableblock halign-left valign-top"></td>
 967 <td class="tableblock halign-left valign-top"></td>
 968 </tr>
 969 <tr>
 970 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus2</p></td>
 971 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
 972 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
 973 <td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
 974 <td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
 975 <td class="tableblock halign-left valign-top"><p class="tableblock">5.4</p></td>
 976 <td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
 977 <td class="tableblock halign-left valign-top"><p class="tableblock">11.0</p></td>
 978 <td class="tableblock halign-left valign-top"><p class="tableblock">14.7</p></td>
 979 </tr>
 980 </tbody>
 981 </table>
 982 <div class="paragraph">
 983 <p>That&#8217;s a bit disappointing. Let&#8217;s see what can we do with expanding a parameter
 984 pack into a base-specifier-list. We would be able to define a class that
 985 derives from every element of the pack:</p>
 986 </div>
 987 <div class="listingblock">
 988 <div class="content">
 989 <pre class="highlight"><code>struct U: T... {};</code></pre>
 990 </div>
 991 </div>
 992 <div class="paragraph">
 993 <p>We can then use <code>std::is_base_of&lt;V, U&gt;</code> to test whether a type <code>V</code> is a base of
 994 <code>U</code>, that is, whether it&#8217;s one of the elements of the parameter pack. Which is
 995 exactly what we need.</p>
 996 </div>
 997 <div class="paragraph">
 998 <p>Arbitrary types such as <code>void</code>, <code>int</code>, or <code>void(int)</code> can&#8217;t be used as base
 999 classes, but we&#8217;ll wrap the types in an empty class template, which we&#8217;ll call
1000 <code>mp_identity</code>.</p>
1001 </div>
1002 <div class="listingblock">
1003 <div class="content">
1004 <pre class="highlight"><code>template&lt;class T&gt; struct mp_identity
1005 {
1006     using type = T;
1007 };
1008
1009 template&lt;class L, class V&gt; struct mp_contains_impl;
1010
1011 template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;
1012
1013 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
1014     struct mp_contains_impl&lt;L&lt;T...&gt;, V&gt;
1015 {
1016     struct U: mp_identity&lt;T&gt;... {};
1017     using type = std::is_base_of&lt;mp_identity&lt;V&gt;, U&gt;;
1018 };</code></pre>
1019 </div>
1020 </div>
1021 <div class="paragraph">
1022 <p>Performance?</p>
1023 </div>
1024 <table class="tableblock frame-all grid-all stretch">
1025 <colgroup>
1026 <col style="width: 11.1111%;">
1027 <col style="width: 11.1111%;">
1028 <col style="width: 11.1111%;">
1029 <col style="width: 11.1111%;">
1030 <col style="width: 11.1111%;">
1031 <col style="width: 11.1111%;">
1032 <col style="width: 11.1111%;">
1033 <col style="width: 11.1111%;">
1034 <col style="width: 11.1112%;">
1035 </colgroup>
1036 <thead>
1037 <tr>
1038 <th class="tableblock halign-left valign-top"></th>
1039 <th class="tableblock halign-left valign-top">N=100</th>
1040 <th class="tableblock halign-left valign-top">N=200</th>
1041 <th class="tableblock halign-left valign-top">N=300</th>
1042 <th class="tableblock halign-left valign-top">N=400</th>
1043 <th class="tableblock halign-left valign-top">N=500</th>
1044 <th class="tableblock halign-left valign-top">N=600</th>
1045 <th class="tableblock halign-left valign-top">N=700</th>
1046 <th class="tableblock halign-left valign-top">N=800</th>
1047 </tr>
1048 </thead>
1049 <tbody>
1050 <tr>
1051 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of</p></td>
1052 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1053 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1054 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1055 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
1056 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1057 <td class="tableblock halign-left valign-top"></td>
1058 <td class="tableblock halign-left valign-top"></td>
1059 <td class="tableblock halign-left valign-top"></td>
1060 </tr>
1061 <tr>
1062 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of</p></td>
1063 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1064 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1065 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1066 <td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
1067 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1068 <td class="tableblock halign-left valign-top"></td>
1069 <td class="tableblock halign-left valign-top"></td>
1070 <td class="tableblock halign-left valign-top"></td>
1071 </tr>
1072 <tr>
1073 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of</p></td>
1074 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1075 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1076 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1077 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1078 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1079 <td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
1080 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
1081 <td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
1082 </tr>
1083 </tbody>
1084 </table>
1085 <div class="paragraph">
1086 <p>This implementation is a clear winner.</p>
1087 </div>
1088 <div class="paragraph">
1089 <p>In fairness, we ought to note that the first four implementations of
1090 <code>mp_contains</code> do not rely on the list elements being unique. This makes
1091 <code>mp_contains</code> an algorithm that supports arbitrary lists, not just sets.</p>
1092 </div>
1093 <div class="paragraph">
1094 <p>The <code>is_base_of</code> implementation, however, does not support lists that contain
1095 duplicates, because it&#8217;s not possible to inherit directly from the same type
1096 twice. So it does not implement the general <code>mp_contains</code>, but something that
1097 should probably be named <code>mp_set_contains</code>.</p>
1098 </div>
1099 <div class="paragraph">
1100 <p>We can avoid the "no duplicates" requirement by modifying the implementation to
1101 inherit from <code>mp_identity&lt;T&gt;</code> indirectly, via an intermediate base class:</p>
1102 </div>
1103 <div class="listingblock">
1104 <div class="content">
1105 <pre class="highlight"><code>// indirect_inherit
1106
1107 template&lt;std::size_t I, class T&gt; struct inherit_second: T {};
1108
1109 template&lt;class L, class S&gt; struct indirect_inherit_impl;
1110
1111 template&lt;template&lt;class...&gt; class L, class... T, std::size_t... J&gt;
1112     struct indirect_inherit_impl&lt;L&lt;T...&gt;, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a>&lt;std::size_t, J...&gt;&gt;:
1113         inherit_second&lt;J, mp_identity&lt;T&gt;&gt;... {};
1114
1115 template&lt;class L&gt; using indirect_inherit =
1116     indirect_inherit_impl&lt;L, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a>&lt;mp_size&lt;L&gt;::value&gt;&gt;;
1117
1118 // mp_contains
1119
1120 template&lt;class L, class V&gt; struct mp_contains_impl
1121 {
1122     using U = indirect_inherit&lt;L&gt;;
1123     using type = std::is_base_of&lt;mp_identity&lt;V&gt;, U&gt;;
1124 };
1125
1126 template&lt;class L, class V&gt; using mp_contains = typename mp_contains_impl&lt;L, V&gt;::type;</code></pre>
1127 </div>
1128 </div>
1129 <div class="paragraph">
1130 <p>This, however, pretty much nullifies the spectacular performance gains we&#8217;ve
1131 observed with the original <code>is_base_of</code>-based implementation:</p>
1132 </div>
1133 <table class="tableblock frame-all grid-all stretch">
1134 <colgroup>
1135 <col style="width: 11.1111%;">
1136 <col style="width: 11.1111%;">
1137 <col style="width: 11.1111%;">
1138 <col style="width: 11.1111%;">
1139 <col style="width: 11.1111%;">
1140 <col style="width: 11.1111%;">
1141 <col style="width: 11.1111%;">
1142 <col style="width: 11.1111%;">
1143 <col style="width: 11.1112%;">
1144 </colgroup>
1145 <thead>
1146 <tr>
1147 <th class="tableblock halign-left valign-top"></th>
1148 <th class="tableblock halign-left valign-top">N=100</th>
1149 <th class="tableblock halign-left valign-top">N=200</th>
1150 <th class="tableblock halign-left valign-top">N=300</th>
1151 <th class="tableblock halign-left valign-top">N=400</th>
1152 <th class="tableblock halign-left valign-top">N=500</th>
1153 <th class="tableblock halign-left valign-top">N=600</th>
1154 <th class="tableblock halign-left valign-top">N=700</th>
1155 <th class="tableblock halign-left valign-top">N=800</th>
1156 </tr>
1157 </thead>
1158 <tbody>
1159 <tr>
1160 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
1161 <td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
1162 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1163 <td class="tableblock halign-left valign-top"></td>
1164 <td class="tableblock halign-left valign-top"></td>
1165 <td class="tableblock halign-left valign-top"></td>
1166 <td class="tableblock halign-left valign-top"></td>
1167 <td class="tableblock halign-left valign-top"></td>
1168 <td class="tableblock halign-left valign-top"></td>
1169 </tr>
1170 <tr>
1171 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, mp_count/mp_plus</p></td>
1172 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
1173 <td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
1174 <td class="tableblock halign-left valign-top"><p class="tableblock">50.5</p></td>
1175 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1176 <td class="tableblock halign-left valign-top"></td>
1177 <td class="tableblock halign-left valign-top"></td>
1178 <td class="tableblock halign-left valign-top"></td>
1179 <td class="tableblock halign-left valign-top"></td>
1180 </tr>
1181 <tr>
1182 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of</p></td>
1183 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1184 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1185 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1186 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
1187 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1188 <td class="tableblock halign-left valign-top"></td>
1189 <td class="tableblock halign-left valign-top"></td>
1190 <td class="tableblock halign-left valign-top"></td>
1191 </tr>
1192 <tr>
1193 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, is_base_of/indirect</p></td>
1194 <td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
1195 <td class="tableblock halign-left valign-top"><p class="tableblock">9.3</p></td>
1196 <td class="tableblock halign-left valign-top"><p class="tableblock">49.5</p></td>
1197 <td class="tableblock halign-left valign-top"><p class="tableblock">153.8</p></td>
1198 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1199 <td class="tableblock halign-left valign-top"></td>
1200 <td class="tableblock halign-left valign-top"></td>
1201 <td class="tableblock halign-left valign-top"></td>
1202 </tr>
1203 </tbody>
1204 </table>
1205 <table class="tableblock frame-all grid-all stretch">
1206 <colgroup>
1207 <col style="width: 11.1111%;">
1208 <col style="width: 11.1111%;">
1209 <col style="width: 11.1111%;">
1210 <col style="width: 11.1111%;">
1211 <col style="width: 11.1111%;">
1212 <col style="width: 11.1111%;">
1213 <col style="width: 11.1111%;">
1214 <col style="width: 11.1111%;">
1215 <col style="width: 11.1112%;">
1216 </colgroup>
1217 <thead>
1218 <tr>
1219 <th class="tableblock halign-left valign-top"></th>
1220 <th class="tableblock halign-left valign-top">N=100</th>
1221 <th class="tableblock halign-left valign-top">N=200</th>
1222 <th class="tableblock halign-left valign-top">N=300</th>
1223 <th class="tableblock halign-left valign-top">N=400</th>
1224 <th class="tableblock halign-left valign-top">N=500</th>
1225 <th class="tableblock halign-left valign-top">N=600</th>
1226 <th class="tableblock halign-left valign-top">N=700</th>
1227 <th class="tableblock halign-left valign-top">N=800</th>
1228 </tr>
1229 </thead>
1230 <tbody>
1231 <tr>
1232 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
1233 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1234 <td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
1235 <td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
1236 <td class="tableblock halign-left valign-top"><p class="tableblock">30.2</p></td>
1237 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1238 <td class="tableblock halign-left valign-top"></td>
1239 <td class="tableblock halign-left valign-top"></td>
1240 <td class="tableblock halign-left valign-top"></td>
1241 </tr>
1242 <tr>
1243 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/mp_plus</p></td>
1244 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
1245 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
1246 <td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
1247 <td class="tableblock halign-left valign-top"><p class="tableblock">6.1</p></td>
1248 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1249 <td class="tableblock halign-left valign-top"></td>
1250 <td class="tableblock halign-left valign-top"></td>
1251 <td class="tableblock halign-left valign-top"></td>
1252 </tr>
1253 <tr>
1254 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus</p></td>
1255 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1256 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
1257 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
1258 <td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
1259 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1260 <td class="tableblock halign-left valign-top"></td>
1261 <td class="tableblock halign-left valign-top"></td>
1262 <td class="tableblock halign-left valign-top"></td>
1263 </tr>
1264 <tr>
1265 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, mp_count/cx_plus2</p></td>
1266 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1267 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1268 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
1269 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1270 <td class="tableblock halign-left valign-top"></td>
1271 <td class="tableblock halign-left valign-top"></td>
1272 <td class="tableblock halign-left valign-top"></td>
1273 <td class="tableblock halign-left valign-top"></td>
1274 </tr>
1275 <tr>
1276 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of</p></td>
1277 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1278 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1279 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1280 <td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
1281 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1282 <td class="tableblock halign-left valign-top"></td>
1283 <td class="tableblock halign-left valign-top"></td>
1284 <td class="tableblock halign-left valign-top"></td>
1285 </tr>
1286 <tr>
1287 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, is_base_of/indirect</p></td>
1288 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1289 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1290 <td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
1291 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
1292 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1293 <td class="tableblock halign-left valign-top"></td>
1294 <td class="tableblock halign-left valign-top"></td>
1295 <td class="tableblock halign-left valign-top"></td>
1296 </tr>
1297 </tbody>
1298 </table>
1299 <table class="tableblock frame-all grid-all stretch">
1300 <colgroup>
1301 <col style="width: 11.1111%;">
1302 <col style="width: 11.1111%;">
1303 <col style="width: 11.1111%;">
1304 <col style="width: 11.1111%;">
1305 <col style="width: 11.1111%;">
1306 <col style="width: 11.1111%;">
1307 <col style="width: 11.1111%;">
1308 <col style="width: 11.1111%;">
1309 <col style="width: 11.1112%;">
1310 </colgroup>
1311 <thead>
1312 <tr>
1313 <th class="tableblock halign-left valign-top"></th>
1314 <th class="tableblock halign-left valign-top">N=100</th>
1315 <th class="tableblock halign-left valign-top">N=200</th>
1316 <th class="tableblock halign-left valign-top">N=300</th>
1317 <th class="tableblock halign-left valign-top">N=400</th>
1318 <th class="tableblock halign-left valign-top">N=500</th>
1319 <th class="tableblock halign-left valign-top">N=600</th>
1320 <th class="tableblock halign-left valign-top">N=700</th>
1321 <th class="tableblock halign-left valign-top">N=800</th>
1322 </tr>
1323 </thead>
1324 <tbody>
1325 <tr>
1326 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
1327 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
1328 <td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
1329 <td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
1330 <td class="tableblock halign-left valign-top"><p class="tableblock">23.2</p></td>
1331 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1332 <td class="tableblock halign-left valign-top"></td>
1333 <td class="tableblock halign-left valign-top"></td>
1334 <td class="tableblock halign-left valign-top"></td>
1335 </tr>
1336 <tr>
1337 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/mp_plus</p></td>
1338 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
1339 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1340 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
1341 <td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
1342 <td class="tableblock halign-left valign-top"><p class="tableblock">9.7</p></td>
1343 <td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
1344 <td class="tableblock halign-left valign-top"><p class="tableblock">22.4</p></td>
1345 <td class="tableblock halign-left valign-top"><p class="tableblock">32.3</p></td>
1346 </tr>
1347 <tr>
1348 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus</p></td>
1349 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1350 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1351 <td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
1352 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
1353 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
1354 <td class="tableblock halign-left valign-top"><p class="tableblock">6.7</p></td>
1355 <td class="tableblock halign-left valign-top"><p class="tableblock">9.2</p></td>
1356 <td class="tableblock halign-left valign-top"><p class="tableblock">11.8</p></td>
1357 </tr>
1358 <tr>
1359 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, mp_count/cx_plus2</p></td>
1360 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1361 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1362 <td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
1363 <td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
1364 <td class="tableblock halign-left valign-top"><p class="tableblock">5.4</p></td>
1365 <td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
1366 <td class="tableblock halign-left valign-top"><p class="tableblock">11.0</p></td>
1367 <td class="tableblock halign-left valign-top"><p class="tableblock">14.7</p></td>
1368 </tr>
1369 <tr>
1370 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of</p></td>
1371 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1372 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1373 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1374 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1375 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1376 <td class="tableblock halign-left valign-top"><p class="tableblock">1.7</p></td>
1377 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
1378 <td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
1379 </tr>
1380 <tr>
1381 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, is_base_of/indirect</p></td>
1382 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
1383 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
1384 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
1385 <td class="tableblock halign-left valign-top"><p class="tableblock">4.0</p></td>
1386 <td class="tableblock halign-left valign-top"><p class="tableblock">6.6</p></td>
1387 <td class="tableblock halign-left valign-top"><p class="tableblock">9.8</p></td>
1388 <td class="tableblock halign-left valign-top"><p class="tableblock">13.6</p></td>
1389 <td class="tableblock halign-left valign-top"><p class="tableblock">18.2</p></td>
1390 </tr>
1391 </tbody>
1392 </table>
1393 </div>
1394 </div>
1395 <div class="sect1">
1396 <h2 id="mp_map_find">mp_map_find</h2>
1397 <div class="sectionbody">
1398 <div class="paragraph">
1399 <p>A map, in the STL sense, is a data structure that associates keys with values
1400 and can efficiently retrieve, given a key, its associated value. For our
1401 purposes, a map will be any list of lists for which the inner lists have at
1402 least one element, the key; the rest of the elements we&#8217;ll consider to be the
1403 associated value. For example, the list</p>
1404 </div>
1405 <div class="listingblock">
1406 <div class="content">
1407 <pre class="highlight"><code>[[A, B], [C, D, E], [F], [G, H]]</code></pre>
1408 </div>
1409 </div>
1410 <div class="paragraph">
1411 <p>is a map with keys <code>A</code>, <code>C</code>, <code>F</code>, and <code>G</code>, with associated values <code>[B]</code>,
1412 <code>[D, E]</code>, <code>[]</code>, and <code>[H]</code>, respectively. We&#8217;ll require unique keys, for reasons
1413 that&#8217;ll become evident later.</p>
1414 </div>
1415 <div class="paragraph">
1416 <p>I&#8217;ll show two other examples of maps, this time using real C&#43;&#43; code:</p>
1417 </div>
1418 <div class="listingblock">
1419 <div class="content">
1420 <pre class="highlight"><code>using Map = mp_list&lt;mp_list&lt;int, int*&gt;, mp_list&lt;void, void*&gt;, mp_list&lt;char, char*&gt;&gt;;</code></pre>
1421 </div>
1422 </div>
1423 <div class="listingblock">
1424 <div class="content">
1425 <pre class="highlight"><code>using Map2 = std::tuple&lt;std::pair&lt;int, int[2]&gt;, std::pair&lt;char, char[2]&gt;&gt;;</code></pre>
1426 </div>
1427 </div>
1428 <div class="paragraph">
1429 <p>The Lisp name of the algorithm that performs retrieval based on key is <code>ASSOC</code>,
1430 but I&#8217;ll call it <code>mp_map_find</code>. <code>mp_map_find&lt;M, K&gt;</code> returns the element of <code>M</code>
1431 whose first element is <code>K</code>. For example, <code>mp_map_find&lt;Map2, int&gt;</code> would return
1432 <code>std::pair&lt;int, int[2]&gt;</code>. If there&#8217;s no such key, it returns <code>void</code>.</p>
1433 </div>
1434 <div class="paragraph">
1435 <p>There&#8217;s almost no need to implement and benchmark the recursive version of
1436 <code>mp_map_find</code>&#8201;&#8212;&#8201;we can be pretty sure it will perform horribly. Still,</p>
1437 </div>
1438 <div class="listingblock">
1439 <div class="content">
1440 <pre class="highlight"><code>template&lt;class M, class K&gt; struct mp_map_find_impl;
1441
1442 template&lt;class M, class K&gt; using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;
1443
1444 template&lt;template&lt;class...&gt; class M, class K&gt; struct mp_map_find_impl&lt;M&lt;&gt;, K&gt;
1445 {
1446     using type = void;
1447 };
1448
1449 template&lt;template&lt;class...&gt; class M, class T1, class... T, class K&gt;
1450     struct mp_map_find_impl&lt;M&lt;T1, T...&gt;, K&gt;
1451 {
1452     using type = mp_if&lt;std::is_same&lt;mp_front&lt;T1&gt;, K&gt;, T1, mp_map_find&lt;M&lt;T...&gt;, K&gt;&gt;;
1453 };</code></pre>
1454 </div>
1455 </div>
1456 <div class="paragraph">
1457 <p>The compile time, in seconds, for <code>N</code> lookups into a map of size <code>N</code>, is as
1458 follows:</p>
1459 </div>
1460 <table class="tableblock frame-all grid-all stretch">
1461 <colgroup>
1462 <col style="width: 11.1111%;">
1463 <col style="width: 11.1111%;">
1464 <col style="width: 11.1111%;">
1465 <col style="width: 11.1111%;">
1466 <col style="width: 11.1111%;">
1467 <col style="width: 11.1111%;">
1468 <col style="width: 11.1111%;">
1469 <col style="width: 11.1111%;">
1470 <col style="width: 11.1112%;">
1471 </colgroup>
1472 <thead>
1473 <tr>
1474 <th class="tableblock halign-left valign-top"></th>
1475 <th class="tableblock halign-left valign-top">N=100</th>
1476 <th class="tableblock halign-left valign-top">N=200</th>
1477 <th class="tableblock halign-left valign-top">N=300</th>
1478 <th class="tableblock halign-left valign-top">N=400</th>
1479 <th class="tableblock halign-left valign-top">N=500</th>
1480 <th class="tableblock halign-left valign-top">N=600</th>
1481 <th class="tableblock halign-left valign-top">N=700</th>
1482 <th class="tableblock halign-left valign-top">N=800</th>
1483 </tr>
1484 </thead>
1485 <tbody>
1486 <tr>
1487 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
1488 <td class="tableblock halign-left valign-top"><p class="tableblock">38.2</p></td>
1489 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1490 <td class="tableblock halign-left valign-top"></td>
1491 <td class="tableblock halign-left valign-top"></td>
1492 <td class="tableblock halign-left valign-top"></td>
1493 <td class="tableblock halign-left valign-top"></td>
1494 <td class="tableblock halign-left valign-top"></td>
1495 <td class="tableblock halign-left valign-top"></td>
1496 </tr>
1497 <tr>
1498 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
1499 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
1500 <td class="tableblock halign-left valign-top"><p class="tableblock">13.7</p></td>
1501 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1502 <td class="tableblock halign-left valign-top"></td>
1503 <td class="tableblock halign-left valign-top"></td>
1504 <td class="tableblock halign-left valign-top"></td>
1505 <td class="tableblock halign-left valign-top"></td>
1506 <td class="tableblock halign-left valign-top"></td>
1507 </tr>
1508 <tr>
1509 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
1510 <td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
1511 <td class="tableblock halign-left valign-top"><p class="tableblock">10.2</p></td>
1512 <td class="tableblock halign-left valign-top"><p class="tableblock">28.8</p></td>
1513 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1514 <td class="tableblock halign-left valign-top"></td>
1515 <td class="tableblock halign-left valign-top"></td>
1516 <td class="tableblock halign-left valign-top"></td>
1517 <td class="tableblock halign-left valign-top"></td>
1518 </tr>
1519 </tbody>
1520 </table>
1521 <div class="paragraph">
1522 <p>I told you there was no point.</p>
1523 </div>
1524 <div class="paragraph">
1525 <p>But, I hear some of you say, you&#8217;re evaluating the else branch even if the
1526 condition is true, and that&#8217;s horribly inefficient!</p>
1527 </div>
1528 <div class="paragraph">
1529 <p>Well, this would only improve the performance by a factor of approximately two
1530 on average, and only if the element is present, but fine, let&#8217;s try it. The
1531 element happens to be present in the benchmark, so let&#8217;s see.</p>
1532 </div>
1533 <div class="listingblock">
1534 <div class="content">
1535 <pre class="highlight"><code>// mp_eval_if
1536
1537 template&lt;bool C, class T, template&lt;class...&gt; class E, class... A&gt;
1538     struct mp_eval_if_c_impl;
1539
1540 template&lt;class T, template&lt;class...&gt; class E, class... A&gt;
1541     struct mp_eval_if_c_impl&lt;true, T, E, A...&gt;
1542 {
1543     using type = T;
1544 };
1545
1546 template&lt;class T, template&lt;class...&gt; class E, class... A&gt;
1547     struct mp_eval_if_c_impl&lt;false, T, E, A...&gt;
1548 {
1549     using type = E&lt;A...&gt;;
1550 };
1551
1552 template&lt;bool C, class T, template&lt;class...&gt; class E, class... A&gt;
1553     using mp_eval_if_c = typename mp_eval_if_c_impl&lt;C, T, E, A...&gt;::type;
1554
1555 template&lt;class C, class T, template&lt;class...&gt; class E, class... A&gt;
1556     using mp_eval_if = typename mp_eval_if_c_impl&lt;C::value != 0, T, E, A...&gt;::type;
1557
1558 // mp_map_find
1559
1560 template&lt;class M, class K&gt; struct mp_map_find_impl;
1561
1562 template&lt;class M, class K&gt; using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;
1563
1564 template&lt;template&lt;class...&gt; class M, class K&gt; struct mp_map_find_impl&lt;M&lt;&gt;, K&gt;
1565 {
1566     using type = void;
1567 };
1568
1569 template&lt;template&lt;class...&gt; class M, class T1, class... T, class K&gt;
1570     struct mp_map_find_impl&lt;M&lt;T1, T...&gt;, K&gt;
1571 {
1572     using type = mp_eval_if&lt;std::is_same&lt;mp_front&lt;T1&gt;, K&gt;, T1, mp_map_find, M&lt;T...&gt;, K&gt;;
1573 };</code></pre>
1574 </div>
1575 </div>
1576 <div class="paragraph">
1577 <p>There you go:</p>
1578 </div>
1579 <table class="tableblock frame-all grid-all stretch">
1580 <colgroup>
1581 <col style="width: 11.1111%;">
1582 <col style="width: 11.1111%;">
1583 <col style="width: 11.1111%;">
1584 <col style="width: 11.1111%;">
1585 <col style="width: 11.1111%;">
1586 <col style="width: 11.1111%;">
1587 <col style="width: 11.1111%;">
1588 <col style="width: 11.1111%;">
1589 <col style="width: 11.1112%;">
1590 </colgroup>
1591 <thead>
1592 <tr>
1593 <th class="tableblock halign-left valign-top"></th>
1594 <th class="tableblock halign-left valign-top">N=100</th>
1595 <th class="tableblock halign-left valign-top">N=200</th>
1596 <th class="tableblock halign-left valign-top">N=300</th>
1597 <th class="tableblock halign-left valign-top">N=400</th>
1598 <th class="tableblock halign-left valign-top">N=500</th>
1599 <th class="tableblock halign-left valign-top">N=600</th>
1600 <th class="tableblock halign-left valign-top">N=700</th>
1601 <th class="tableblock halign-left valign-top">N=800</th>
1602 </tr>
1603 </thead>
1604 <tbody>
1605 <tr>
1606 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
1607 <td class="tableblock halign-left valign-top"><p class="tableblock">15.6</p></td>
1608 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1609 <td class="tableblock halign-left valign-top"></td>
1610 <td class="tableblock halign-left valign-top"></td>
1611 <td class="tableblock halign-left valign-top"></td>
1612 <td class="tableblock halign-left valign-top"></td>
1613 <td class="tableblock halign-left valign-top"></td>
1614 <td class="tableblock halign-left valign-top"></td>
1615 </tr>
1616 <tr>
1617 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
1618 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
1619 <td class="tableblock halign-left valign-top"><p class="tableblock">9.5</p></td>
1620 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1621 <td class="tableblock halign-left valign-top"></td>
1622 <td class="tableblock halign-left valign-top"></td>
1623 <td class="tableblock halign-left valign-top"></td>
1624 <td class="tableblock halign-left valign-top"></td>
1625 <td class="tableblock halign-left valign-top"></td>
1626 </tr>
1627 <tr>
1628 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
1629 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
1630 <td class="tableblock halign-left valign-top"><p class="tableblock">7.0</p></td>
1631 <td class="tableblock halign-left valign-top"><p class="tableblock">19.7</p></td>
1632 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1633 <td class="tableblock halign-left valign-top"></td>
1634 <td class="tableblock halign-left valign-top"></td>
1635 <td class="tableblock halign-left valign-top"></td>
1636 <td class="tableblock halign-left valign-top"></td>
1637 </tr>
1638 </tbody>
1639 </table>
1640 <div class="paragraph">
1641 <p>I told you there was no point.</p>
1642 </div>
1643 <div class="paragraph">
1644 <p>Point or no, to establish that the recursive implementation is inefficient is
1645 not the same as to come up with an efficient one. There are two things that
1646 make the <code>mp_contains</code> techniques inapplicable to our present case: first,
1647 <code>mp_contains</code> only had to return true or false, whereas <code>mp_map_find</code> returns a
1648 type, and second, in <code>mp_contains</code> we knew the exact type of the element for
1649 which we were looking, whereas here, we only know its <code>mp_front</code>.</p>
1650 </div>
1651 <div class="paragraph">
1652 <p>Fortunately, there does exist a language feature that can solve both: C&#43;&#43; can
1653 deduce the template parameters of base classes when passed a derived class. In
1654 this example,</p>
1655 </div>
1656 <div class="listingblock">
1657 <div class="content">
1658 <pre class="highlight"><code>struct K1 {};
1659 struct V1 {};
1660
1661 struct X: std::pair&lt;K1, V1&gt; {};
1662
1663 template&lt;class A, class B&gt; void f(std::pair&lt;A, B&gt; const &amp; p);
1664
1665 int main()
1666 {
1667     f(X());
1668 }</code></pre>
1669 </div>
1670 </div>
1671 <div class="paragraph">
1672 <p>the call to <code>f(X())</code> deduces <code>A</code> as <code>K1</code> and <code>B</code> as <code>V1</code>. If we have more than
1673 one <code>std::pair</code> base class, we can fix <code>A</code> to be <code>K1</code>:</p>
1674 </div>
1675 <div class="listingblock">
1676 <div class="content">
1677 <pre class="highlight"><code>struct K1 {};
1678 struct V1 {};
1679
1680 struct K2 {};
1681 struct V2 {};
1682
1683 struct X: std::pair&lt;K1, V1&gt;, std::pair&lt;K2, V2&gt; {};
1684
1685 template&lt;class B&gt; void f(std::pair&lt;K1, B&gt; const &amp; p);
1686
1687 int main()
1688 {
1689     f(X());
1690 }</code></pre>
1691 </div>
1692 </div>
1693 <div class="paragraph">
1694 <p>and <code>B</code> will be deduced as <code>V1</code>.</p>
1695 </div>
1696 <div class="paragraph">
1697 <p>We can retrieve the results of the deduction by returning the type we want:</p>
1698 </div>
1699 <div class="listingblock">
1700 <div class="content">
1701 <pre class="highlight"><code>template&lt;class B&gt; std::pair&lt;K1, B&gt; f(std::pair&lt;K1, B&gt; const &amp; p);</code></pre>
1702 </div>
1703 </div>
1704 <div class="paragraph">
1705 <p>and then using <code>decltype(f(X()))</code> to obtain this return type.</p>
1706 </div>
1707 <div class="paragraph">
1708 <p>What if <code>X</code> doesn&#8217;t have a base of type <code>std::pair&lt;K1, B&gt;</code>? The deduction will
1709 fail and we&#8217;ll get an error that <code>f(X())</code> cannot be called. To avoid it, we can
1710 add an overload of <code>f</code> that takes anything and returns <code>void</code>. But in this
1711 case, what will happen if <code>X</code> has two bases of the form that match the first
1712 <code>f</code> overload, such as for example <code>std::pair&lt;K1, Y&gt;</code> and <code>std::pair&lt;K1, Z&gt;</code>?</p>
1713 </div>
1714 <div class="paragraph">
1715 <p>The deduction will fail, the second overload will again be chosen and we&#8217;ll get
1716 <code>void</code>. This is why we require maps to have unique keys.</p>
1717 </div>
1718 <div class="paragraph">
1719 <p>Here&#8217;s an implementation of <code>mp_map_find</code> based on this technique:</p>
1720 </div>
1721 <div class="listingblock">
1722 <div class="content">
1723 <pre class="highlight"><code>template&lt;class M, class K&gt; struct mp_map_find_impl;
1724
1725 template&lt;class M, class K&gt;
1726     using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;
1727
1728 template&lt;template&lt;class...&gt; class M, class... T, class K&gt;
1729     struct mp_map_find_impl&lt;M&lt;T...&gt;, K&gt;
1730 {
1731     struct U: mp_identity&lt;T&gt;... {};
1732
1733     template&lt;template&lt;class...&gt; class L, class... U&gt;
1734         static mp_identity&lt;L&lt;K, U...&gt;&gt;
1735         f( mp_identity&lt;L&lt;K, U...&gt;&gt;* );
1736
1737     static mp_identity&lt;void&gt; f( ... );
1738
1739     using V = decltype( f((U*)0) );
1740
1741     using type = typename V::type;
1742 };</code></pre>
1743 </div>
1744 </div>
1745 <div class="paragraph">
1746 <p>and its corresponding compile times:</p>
1747 </div>
1748 <table class="tableblock frame-all grid-all stretch">
1749 <colgroup>
1750 <col style="width: 11.1111%;">
1751 <col style="width: 11.1111%;">
1752 <col style="width: 11.1111%;">
1753 <col style="width: 11.1111%;">
1754 <col style="width: 11.1111%;">
1755 <col style="width: 11.1111%;">
1756 <col style="width: 11.1111%;">
1757 <col style="width: 11.1111%;">
1758 <col style="width: 11.1112%;">
1759 </colgroup>
1760 <thead>
1761 <tr>
1762 <th class="tableblock halign-left valign-top"></th>
1763 <th class="tableblock halign-left valign-top">N=100</th>
1764 <th class="tableblock halign-left valign-top">N=200</th>
1765 <th class="tableblock halign-left valign-top">N=300</th>
1766 <th class="tableblock halign-left valign-top">N=400</th>
1767 <th class="tableblock halign-left valign-top">N=500</th>
1768 <th class="tableblock halign-left valign-top">N=600</th>
1769 <th class="tableblock halign-left valign-top">N=700</th>
1770 <th class="tableblock halign-left valign-top">N=800</th>
1771 </tr>
1772 </thead>
1773 <tbody>
1774 <tr>
1775 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, deduction</p></td>
1776 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1777 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
1778 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
1779 <td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
1780 <td class="tableblock halign-left valign-top"><p class="tableblock">6.4</p></td>
1781 <td class="tableblock halign-left valign-top"><p class="tableblock">10.4</p></td>
1782 <td class="tableblock halign-left valign-top"><p class="tableblock">16.2</p></td>
1783 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1784 </tr>
1785 <tr>
1786 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, deduction</p></td>
1787 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1788 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1789 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1790 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1791 <td class="tableblock halign-left valign-top"><p class="tableblock">1.2</p></td>
1792 <td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
1793 <td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
1794 <td class="tableblock halign-left valign-top"><p class="tableblock">2.7</p></td>
1795 </tr>
1796 <tr>
1797 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, deduction</p></td>
1798 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1799 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
1800 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1801 <td class="tableblock halign-left valign-top"><p class="tableblock">1.6</p></td>
1802 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
1803 <td class="tableblock halign-left valign-top"><p class="tableblock">3.4</p></td>
1804 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
1805 <td class="tableblock halign-left valign-top"><p class="tableblock">6.3</p></td>
1806 </tr>
1807 </tbody>
1808 </table>
1809 <div class="paragraph">
1810 <p>This looks ready to ship.</p>
1811 </div>
1812 <div class="paragraph">
1813 <p>The implementation contains one inefficiency though. If we evaluate
1814 <code>mp_map_find&lt;M, K1&gt;</code>, then <code>mp_map_find&lt;M, K2&gt;</code>, the two nested <code>U</code> types are
1815 the same as they only depend on <code>M</code>, but the compiler doesn&#8217;t know that and
1816 will instantiate each one separately. We should move this type outside
1817 <code>mp_map_find_impl</code> so that it can be reused:</p>
1818 </div>
1819 <div class="listingblock">
1820 <div class="content">
1821 <pre class="highlight"><code>template&lt;class... T&gt; struct <strong>mp_inherit</strong>: T... {};
1822
1823 template&lt;class M, class K&gt; struct mp_map_find_impl;
1824
1825 template&lt;class M, class K&gt;
1826     using mp_map_find = typename mp_map_find_impl&lt;M, K&gt;::type;
1827
1828 template&lt;template&lt;class...&gt; class M, class... T, class K&gt;
1829     struct mp_map_find_impl&lt;M&lt;T...&gt;, K&gt;
1830 {
1831     <strong>using U = mp_inherit&lt;mp_identity&lt;T&gt;...&gt;;</strong>
1832
1833     template&lt;template&lt;class...&gt; class L, class... U&gt;
1834         static mp_identity&lt;L&lt;K, U...&gt;&gt;
1835         f( mp_identity&lt;L&lt;K, U...&gt;&gt;* );
1836
1837     static mp_identity&lt;void&gt; f( ... );
1838
1839     using V = decltype( f((U*)0) );
1840
1841     using type = typename V::type;
1842 };</code></pre>
1843 </div>
1844 </div>
1845 <div class="paragraph">
1846 <p>(This same optimization, by the way, applies to our <code>is_base_of</code> implementation
1847 of <code>mp_contains</code>.)</p>
1848 </div>
1849 <div class="paragraph">
1850 <p>The improvement in compile times on our benchmark is measurable:</p>
1851 </div>
1852 <table class="tableblock frame-all grid-all stretch">
1853 <colgroup>
1854 <col style="width: 11.1111%;">
1855 <col style="width: 11.1111%;">
1856 <col style="width: 11.1111%;">
1857 <col style="width: 11.1111%;">
1858 <col style="width: 11.1111%;">
1859 <col style="width: 11.1111%;">
1860 <col style="width: 11.1111%;">
1861 <col style="width: 11.1111%;">
1862 <col style="width: 11.1112%;">
1863 </colgroup>
1864 <thead>
1865 <tr>
1866 <th class="tableblock halign-left valign-top"></th>
1867 <th class="tableblock halign-left valign-top">N=100</th>
1868 <th class="tableblock halign-left valign-top">N=200</th>
1869 <th class="tableblock halign-left valign-top">N=300</th>
1870 <th class="tableblock halign-left valign-top">N=400</th>
1871 <th class="tableblock halign-left valign-top">N=500</th>
1872 <th class="tableblock halign-left valign-top">N=600</th>
1873 <th class="tableblock halign-left valign-top">N=700</th>
1874 <th class="tableblock halign-left valign-top">N=800</th>
1875 </tr>
1876 </thead>
1877 <tbody>
1878 <tr>
1879 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, deduction+mp_inherit</p></td>
1880 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1881 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1882 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
1883 <td class="tableblock halign-left valign-top"><p class="tableblock">2.6</p></td>
1884 <td class="tableblock halign-left valign-top"><p class="tableblock">4.5</p></td>
1885 <td class="tableblock halign-left valign-top"><p class="tableblock">7.1</p></td>
1886 <td class="tableblock halign-left valign-top"><p class="tableblock">10.7</p></td>
1887 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1888 </tr>
1889 <tr>
1890 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, deduction+mp_inherit</p></td>
1891 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1892 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1893 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1894 <td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
1895 <td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
1896 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
1897 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
1898 <td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
1899 </tr>
1900 <tr>
1901 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, deduction+mp_inherit</p></td>
1902 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
1903 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
1904 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
1905 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
1906 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
1907 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
1908 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
1909 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
1910 </tr>
1911 </tbody>
1912 </table>
1913 </div>
1914 </div>
1915 <div class="sect1">
1916 <h2 id="mp_at">mp_at</h2>
1917 <div class="sectionbody">
1918 <div class="paragraph">
1919 <p>With sets and maps covered, it&#8217;s time to tackle vectors. Vectors for us are
1920 just lists, to which we&#8217;ll need to add the ability to efficiently access an
1921 element based on its index. The customary name for this accessor is
1922 <code>mp_at&lt;L, I&gt;</code>, where <code>L</code> is a list and <code>I</code> is an <code>integral_constant</code> that
1923 represents the index. We&#8217;ll also follow the Boost.MPL convention and add
1924 <code>mp_at_c&lt;L, I&gt;</code>, where <code>I</code> is the index of type <code>size_t</code>.</p>
1925 </div>
1926 <div class="paragraph">
1927 <p>The recursive implementation of <code>mp_at</code> is:</p>
1928 </div>
1929 <div class="listingblock">
1930 <div class="content">
1931 <pre class="highlight"><code>template&lt;class L, std::size_t I&gt; struct mp_at_c_impl;
1932
1933 template&lt;class L, std::size_t I&gt; using mp_at_c = typename mp_at_c_impl&lt;L, I&gt;::type;
1934
1935 template&lt;class L, class I&gt; using mp_at = typename mp_at_c_impl&lt;L, I::value&gt;::type;
1936
1937 template&lt;template&lt;class...&gt; class L, class T1, class... T&gt;
1938     struct mp_at_c_impl&lt;L&lt;T1, T...&gt;, 0&gt;
1939 {
1940     using type = T1;
1941 };
1942
1943 template&lt;template&lt;class...&gt; class L, class T1, class... T, std::size_t I&gt;
1944     struct mp_at_c_impl&lt;L&lt;T1, T...&gt;, I&gt;
1945 {
1946     using type = mp_at_c&lt;L&lt;T...&gt;, I-1&gt;;
1947 };</code></pre>
1948 </div>
1949 </div>
1950 <div class="paragraph">
1951 <p>and the compile times for making <code>N</code> calls to <code>mp_at</code> with a list of size <code>N</code>
1952 as the first argument are:</p>
1953 </div>
1954 <table class="tableblock frame-all grid-all stretch">
1955 <colgroup>
1956 <col style="width: 11.1111%;">
1957 <col style="width: 11.1111%;">
1958 <col style="width: 11.1111%;">
1959 <col style="width: 11.1111%;">
1960 <col style="width: 11.1111%;">
1961 <col style="width: 11.1111%;">
1962 <col style="width: 11.1111%;">
1963 <col style="width: 11.1111%;">
1964 <col style="width: 11.1112%;">
1965 </colgroup>
1966 <thead>
1967 <tr>
1968 <th class="tableblock halign-left valign-top"></th>
1969 <th class="tableblock halign-left valign-top">N=100</th>
1970 <th class="tableblock halign-left valign-top">N=200</th>
1971 <th class="tableblock halign-left valign-top">N=300</th>
1972 <th class="tableblock halign-left valign-top">N=400</th>
1973 <th class="tableblock halign-left valign-top">N=500</th>
1974 <th class="tableblock halign-left valign-top">N=600</th>
1975 <th class="tableblock halign-left valign-top">N=700</th>
1976 <th class="tableblock halign-left valign-top">N=800</th>
1977 </tr>
1978 </thead>
1979 <tbody>
1980 <tr>
1981 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
1982 <td class="tableblock halign-left valign-top"><p class="tableblock">3.6</p></td>
1983 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1984 <td class="tableblock halign-left valign-top"></td>
1985 <td class="tableblock halign-left valign-top"></td>
1986 <td class="tableblock halign-left valign-top"></td>
1987 <td class="tableblock halign-left valign-top"></td>
1988 <td class="tableblock halign-left valign-top"></td>
1989 <td class="tableblock halign-left valign-top"></td>
1990 </tr>
1991 <tr>
1992 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
1993 <td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
1994 <td class="tableblock halign-left valign-top"><p class="tableblock">5.1</p></td>
1995 <td class="tableblock halign-left valign-top"><p class="tableblock">15.3</p></td>
1996 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
1997 <td class="tableblock halign-left valign-top"></td>
1998 <td class="tableblock halign-left valign-top"></td>
1999 <td class="tableblock halign-left valign-top"></td>
2000 <td class="tableblock halign-left valign-top"></td>
2001 </tr>
2002 <tr>
2003 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
2004 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
2005 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
2006 <td class="tableblock halign-left valign-top"><p class="tableblock">14.2</p></td>
2007 <td class="tableblock halign-left valign-top"><p class="tableblock">32.4</p></td>
2008 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2009 <td class="tableblock halign-left valign-top"></td>
2010 <td class="tableblock halign-left valign-top"></td>
2011 <td class="tableblock halign-left valign-top"></td>
2012 </tr>
2013 </tbody>
2014 </table>
2015 <div class="paragraph">
2016 <p>To improve upon this appalling result, we&#8217;ll again exploit pack expansion into a
2017 function call, but in a novel way. Let&#8217;s suppose that we need to access the
2018 fourth element (<code>I = 3</code>). We&#8217;ll generate the function signature</p>
2019 </div>
2020 <div class="listingblock">
2021 <div class="content">
2022 <pre class="highlight"><code>template&lt;class W&gt; W f( void*, void*, void*, W*, ... );</code></pre>
2023 </div>
2024 </div>
2025 <div class="paragraph">
2026 <p>and then, given a list <code>L&lt;T1, T2, T3, T4, T5, T6, T7&gt;</code>, we&#8217;ll evaluate the
2027 expression</p>
2028 </div>
2029 <div class="listingblock">
2030 <div class="content">
2031 <pre class="highlight"><code>decltype( f( (T1*)0, (T2*)0, (T3*)0, (T4*)0, (T5*)0, (T6*)0, (T7*)0 ) )</code></pre>
2032 </div>
2033 </div>
2034 <div class="paragraph">
2035 <p>The three <code>void*</code> parameters will eat the first three elements, <code>W</code> will be
2036 deduced as the fourth, and the ellipsis will take care of the rest.</p>
2037 </div>
2038 <div class="paragraph">
2039 <p>A working implementation based on this technique is shown below:</p>
2040 </div>
2041 <div class="listingblock">
2042 <div class="content">
2043 <pre class="highlight"><code>// mp_repeat_c
2044
2045 template&lt;std::size_t N, class... T&gt; struct mp_repeat_c_impl
2046 {
2047     using _l1 = typename mp_repeat_c_impl&lt;N/2, T...&gt;::type;
2048     using _l2 = typename mp_repeat_c_impl&lt;N%2, T...&gt;::type;
2049
2050     using type = mp_append&lt;_l1, _l1, _l2&gt;;
2051 };
2052
2053 template&lt;class... T&gt; struct mp_repeat_c_impl&lt;0, T...&gt;
2054 {
2055     using type = mp_list&lt;&gt;;
2056 };
2057
2058 template&lt;class... T&gt; struct mp_repeat_c_impl&lt;1, T...&gt;
2059 {
2060     using type = mp_list&lt;T...&gt;;
2061 };
2062
2063 template&lt;std::size_t N, class... T&gt; using mp_repeat_c =
2064     typename mp_repeat_c_impl&lt;N, T...&gt;::type;
2065
2066 // mp_at
2067
2068 template&lt;class L, class L2&gt; struct mp_at_c_impl;
2069
2070 template&lt;template&lt;class...&gt; class L, class... T,
2071     template&lt;class...&gt; class L2, class... U&gt;
2072     struct mp_at_c_impl&lt;L&lt;T...&gt;, L2&lt;U...&gt;&gt;
2073 {
2074     template&lt;class W&gt; static W f( U*..., W*, ... );
2075
2076     using R = decltype( f( (mp_identity&lt;T&gt;*)0 ... ) );
2077
2078     using type = typename R::type;
2079 };
2080
2081 template&lt;class L, std::size_t I&gt; using mp_at_c =
2082     typename mp_at_c_impl&lt;L, mp_repeat_c&lt;I, void&gt;&gt;::type;
2083
2084 template&lt;class L, class I&gt; using mp_at = mp_at_c&lt;L, I::value&gt;;</code></pre>
2085 </div>
2086 </div>
2087 <div class="paragraph">
2088 <p>and the compile times in the following table show it to be good enough for most
2089 practical purposes.</p>
2090 </div>
2091 <table class="tableblock frame-all grid-all stretch">
2092 <colgroup>
2093 <col style="width: 11.1111%;">
2094 <col style="width: 11.1111%;">
2095 <col style="width: 11.1111%;">
2096 <col style="width: 11.1111%;">
2097 <col style="width: 11.1111%;">
2098 <col style="width: 11.1111%;">
2099 <col style="width: 11.1111%;">
2100 <col style="width: 11.1111%;">
2101 <col style="width: 11.1112%;">
2102 </colgroup>
2103 <thead>
2104 <tr>
2105 <th class="tableblock halign-left valign-top"></th>
2106 <th class="tableblock halign-left valign-top">N=100</th>
2107 <th class="tableblock halign-left valign-top">N=200</th>
2108 <th class="tableblock halign-left valign-top">N=300</th>
2109 <th class="tableblock halign-left valign-top">N=400</th>
2110 <th class="tableblock halign-left valign-top">N=500</th>
2111 <th class="tableblock halign-left valign-top">N=600</th>
2112 <th class="tableblock halign-left valign-top">N=700</th>
2113 <th class="tableblock halign-left valign-top">N=800</th>
2114 </tr>
2115 </thead>
2116 <tbody>
2117 <tr>
2118 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, void*</p></td>
2119 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
2120 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
2121 <td class="tableblock halign-left valign-top"><p class="tableblock">2.4</p></td>
2122 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
2123 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2124 <td class="tableblock halign-left valign-top"></td>
2125 <td class="tableblock halign-left valign-top"></td>
2126 <td class="tableblock halign-left valign-top"></td>
2127 </tr>
2128 <tr>
2129 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, void*</p></td>
2130 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
2131 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
2132 <td class="tableblock halign-left valign-top"><p class="tableblock">1.2</p></td>
2133 <td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
2134 <td class="tableblock halign-left valign-top"><p class="tableblock">2.7</p></td>
2135 <td class="tableblock halign-left valign-top"><p class="tableblock">3.8</p></td>
2136 <td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
2137 <td class="tableblock halign-left valign-top"><p class="tableblock">6.6</p></td>
2138 </tr>
2139 <tr>
2140 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, void*</p></td>
2141 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
2142 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
2143 <td class="tableblock halign-left valign-top"><p class="tableblock">0.9</p></td>
2144 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
2145 <td class="tableblock halign-left valign-top"><p class="tableblock">2.1</p></td>
2146 <td class="tableblock halign-left valign-top"><p class="tableblock">3.0</p></td>
2147 <td class="tableblock halign-left valign-top"><p class="tableblock">4.2</p></td>
2148 <td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
2149 </tr>
2150 </tbody>
2151 </table>
2152 <div class="paragraph">
2153 <p>Are we done with <code>mp_at</code>, then?</p>
2154 </div>
2155 <div class="paragraph">
2156 <p>Let&#8217;s try something else&#8201;&#8212;&#8201;transform the input list <code>[T1, T2, T3]</code> into a map
2157 <code>[[0, T1], [1, T2], [2, T3]]</code>, then use <code>mp_map_find</code> for the lookup:</p>
2158 </div>
2159 <div class="listingblock">
2160 <div class="content">
2161 <pre class="highlight"><code>// mp_map_from_list
2162
2163 template&lt;class L, class S&gt; struct mp_map_from_list_impl;
2164
2165 template&lt;template&lt;class...&gt; class L, class... T, std::size_t... J&gt;
2166     struct mp_map_from_list_impl&lt;L&lt;T...&gt;, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a>&lt;std::size_t, J...&gt;&gt;
2167 {
2168     using type = mp_list&lt;mp_list&lt;mp_size_t&lt;J&gt;, T&gt;...&gt;;
2169 };
2170
2171 template&lt;class L&gt; using mp_map_from_list = typename mp_map_from_list_impl&lt;L,
2172     <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a>&lt;mp_size&lt;L&gt;::value&gt;&gt;::type;
2173
2174 // mp_at
2175
2176 template&lt;class L, std::size_t I&gt; struct mp_at_c_impl
2177 {
2178     using map = mp_map_from_list&lt;L&gt;;
2179     using type = mp_second&lt;mp_map_find&lt;map, mp_size_t&lt;I&gt;&gt;&gt;;
2180 };
2181
2182 template&lt;class L, std::size_t I&gt; using mp_at_c = typename mp_at_c_impl&lt;L, I&gt;::type;
2183
2184 template&lt;class L, class I&gt; using mp_at = typename mp_at_c_impl&lt;L, I::value&gt;::type;</code></pre>
2185 </div>
2186 </div>
2187 <div class="paragraph">
2188 <p>At first sight, this looks ridiculous, but metaprogramming has its own rules.
2189 Let&#8217;s measure:</p>
2190 </div>
2191 <table class="tableblock frame-all grid-all stretch">
2192 <colgroup>
2193 <col style="width: 11.1111%;">
2194 <col style="width: 11.1111%;">
2195 <col style="width: 11.1111%;">
2196 <col style="width: 11.1111%;">
2197 <col style="width: 11.1111%;">
2198 <col style="width: 11.1111%;">
2199 <col style="width: 11.1111%;">
2200 <col style="width: 11.1111%;">
2201 <col style="width: 11.1112%;">
2202 </colgroup>
2203 <thead>
2204 <tr>
2205 <th class="tableblock halign-left valign-top"></th>
2206 <th class="tableblock halign-left valign-top">N=100</th>
2207 <th class="tableblock halign-left valign-top">N=200</th>
2208 <th class="tableblock halign-left valign-top">N=300</th>
2209 <th class="tableblock halign-left valign-top">N=400</th>
2210 <th class="tableblock halign-left valign-top">N=500</th>
2211 <th class="tableblock halign-left valign-top">N=600</th>
2212 <th class="tableblock halign-left valign-top">N=700</th>
2213 <th class="tableblock halign-left valign-top">N=800</th>
2214 </tr>
2215 </thead>
2216 <tbody>
2217 <tr>
2218 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, map</p></td>
2219 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
2220 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
2221 <td class="tableblock halign-left valign-top"><p class="tableblock">1.5</p></td>
2222 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
2223 <td class="tableblock halign-left valign-top"><p class="tableblock">5.0</p></td>
2224 <td class="tableblock halign-left valign-top"><p class="tableblock">7.8</p></td>
2225 <td class="tableblock halign-left valign-top"><p class="tableblock">11.9</p></td>
2226 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2227 </tr>
2228 <tr>
2229 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, map</p></td>
2230 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
2231 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
2232 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
2233 <td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
2234 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
2235 <td class="tableblock halign-left valign-top"><p class="tableblock">1.5</p></td>
2236 <td class="tableblock halign-left valign-top"><p class="tableblock">1.8</p></td>
2237 <td class="tableblock halign-left valign-top"><p class="tableblock">2.3</p></td>
2238 </tr>
2239 <tr>
2240 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, map</p></td>
2241 <td class="tableblock halign-left valign-top"><p class="tableblock">0.3</p></td>
2242 <td class="tableblock halign-left valign-top"><p class="tableblock">0.4</p></td>
2243 <td class="tableblock halign-left valign-top"><p class="tableblock">0.7</p></td>
2244 <td class="tableblock halign-left valign-top"><p class="tableblock">1.0</p></td>
2245 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
2246 <td class="tableblock halign-left valign-top"><p class="tableblock">1.9</p></td>
2247 <td class="tableblock halign-left valign-top"><p class="tableblock">2.5</p></td>
2248 <td class="tableblock halign-left valign-top"><p class="tableblock">3.2</p></td>
2249 </tr>
2250 </tbody>
2251 </table>
2252 <div class="paragraph">
2253 <p>Surprise, this is the best implementation.</p>
2254 </div>
2255 </div>
2256 </div>
2257 <div class="sect1">
2258 <h2 id="mp_drop">mp_drop</h2>
2259 <div class="sectionbody">
2260 <div class="paragraph">
2261 <p>It turned out that we didn&#8217;t need the <code>void*</code> trick for <code>mp_at</code>, but I&#8217;ll show
2262 an example where we do: <code>mp_drop</code>. <code>mp_drop&lt;L, N&gt;</code> returns the list <code>L</code> without
2263 its first <code>N</code> elements; or, in other words, it drops the first <code>N</code> elements
2264 (presumably on the cutting room floor) and returns what&#8217;s left.</p>
2265 </div>
2266 <div class="paragraph">
2267 <p>To implement <code>mp_drop</code>, we just need to change</p>
2268 </div>
2269 <div class="listingblock">
2270 <div class="content">
2271 <pre class="highlight"><code>template&lt;class W&gt; W f( void*, void*, void*, W*, ... );</code></pre>
2272 </div>
2273 </div>
2274 <div class="paragraph">
2275 <p>from above to return the rest of the elements, rather than just one:</p>
2276 </div>
2277 <div class="listingblock">
2278 <div class="content">
2279 <pre class="highlight"><code>template&lt;class... W&gt; mp_list&lt;W&gt; f( void*, void*, void*, W*... );</code></pre>
2280 </div>
2281 </div>
2282 <div class="paragraph">
2283 <p>Adding the necessary <code>mp_identity</code> seasoning produces the following working
2284 implementation:</p>
2285 </div>
2286 <div class="listingblock">
2287 <div class="content">
2288 <pre class="highlight"><code>template&lt;class L, class L2&gt; struct mp_drop_c_impl;
2289
2290 template&lt;template&lt;class...&gt; class L, class... T,
2291     template&lt;class...&gt; class L2, class... U&gt;
2292     struct mp_drop_c_impl&lt;L&lt;T...&gt;, L2&lt;U...&gt;&gt;
2293 {
2294     template&lt;class... W&gt; static mp_identity&lt;L&lt;W...&gt;&gt; f( U*..., mp_identity&lt;W&gt;*... );
2295
2296     using R = decltype( f( (mp_identity&lt;T&gt;*)0 ... ) );
2297
2298     using type = typename R::type;
2299 };
2300
2301 template&lt;class L, std::size_t N&gt; using mp_drop_c =
2302     typename mp_drop_c_impl&lt;L, mp_repeat_c&lt;N, void&gt;&gt;::type;
2303
2304 template&lt;class L, class N&gt; using mp_drop = mp_drop_c&lt;L, N::value&gt;;</code></pre>
2305 </div>
2306 </div>
2307 <div class="paragraph">
2308 <p>I&#8217;ll skip the recursive implementation and the performance comparison for this
2309 one. We can pretty much tell who&#8217;s going to win, and by how much.</p>
2310 </div>
2311 </div>
2312 </div>
2313 <div class="sect1">
2314 <h2 id="mp_find_index">mp_find_index</h2>
2315 <div class="sectionbody">
2316 <div class="paragraph">
2317 <p>The final algorithm that I&#8217;ll bring to your attention is <code>mp_find_index</code>.
2318 <code>mp_find_index&lt;L, V&gt;</code> returns an integral constant of type <code>size_t</code> with a
2319 value that is the index of the first occurrence of <code>V</code> in <code>L</code>. If <code>V</code> is not in
2320 <code>L</code>, the return value is the size of <code>L</code>.</p>
2321 </div>
2322 <div class="paragraph">
2323 <p>We&#8217;ll start with the recursive implementation, as usual:</p>
2324 </div>
2325 <div class="listingblock">
2326 <div class="content">
2327 <pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;
2328
2329 template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;
2330
2331 template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
2332 {
2333     using type = mp_size_t&lt;0&gt;;
2334 };
2335
2336 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
2337     struct mp_find_index_impl&lt;L&lt;V, T...&gt;, V&gt;
2338 {
2339     using type = mp_size_t&lt;0&gt;;
2340 };
2341
2342 template&lt;template&lt;class...&gt; class L, class T1, class... T, class V&gt;
2343     struct mp_find_index_impl&lt;L&lt;T1, T...&gt;, V&gt;
2344 {
2345     using type = mp_size_t&lt;1 + mp_find_index&lt;L&lt;T...&gt;, V&gt;::value&gt;;
2346 };</code></pre>
2347 </div>
2348 </div>
2349 <div class="paragraph">
2350 <p>and will continue with the compile times for <code>N</code> calls to <code>mp_find_index</code> on a
2351 list with <code>N</code> elements, as usual:</p>
2352 </div>
2353 <table class="tableblock frame-all grid-all stretch">
2354 <colgroup>
2355 <col style="width: 11.1111%;">
2356 <col style="width: 11.1111%;">
2357 <col style="width: 11.1111%;">
2358 <col style="width: 11.1111%;">
2359 <col style="width: 11.1111%;">
2360 <col style="width: 11.1111%;">
2361 <col style="width: 11.1111%;">
2362 <col style="width: 11.1111%;">
2363 <col style="width: 11.1112%;">
2364 </colgroup>
2365 <thead>
2366 <tr>
2367 <th class="tableblock halign-left valign-top"></th>
2368 <th class="tableblock halign-left valign-top">N=100</th>
2369 <th class="tableblock halign-left valign-top">N=200</th>
2370 <th class="tableblock halign-left valign-top">N=300</th>
2371 <th class="tableblock halign-left valign-top">N=400</th>
2372 <th class="tableblock halign-left valign-top">N=500</th>
2373 <th class="tableblock halign-left valign-top">N=600</th>
2374 <th class="tableblock halign-left valign-top">N=700</th>
2375 <th class="tableblock halign-left valign-top">N=800</th>
2376 </tr>
2377 </thead>
2378 <tbody>
2379 <tr>
2380 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, recursive</p></td>
2381 <td class="tableblock halign-left valign-top"><p class="tableblock">3.5</p></td>
2382 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2383 <td class="tableblock halign-left valign-top"></td>
2384 <td class="tableblock halign-left valign-top"></td>
2385 <td class="tableblock halign-left valign-top"></td>
2386 <td class="tableblock halign-left valign-top"></td>
2387 <td class="tableblock halign-left valign-top"></td>
2388 <td class="tableblock halign-left valign-top"></td>
2389 </tr>
2390 <tr>
2391 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, recursive</p></td>
2392 <td class="tableblock halign-left valign-top"><p class="tableblock">1.1</p></td>
2393 <td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
2394 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2395 <td class="tableblock halign-left valign-top"></td>
2396 <td class="tableblock halign-left valign-top"></td>
2397 <td class="tableblock halign-left valign-top"></td>
2398 <td class="tableblock halign-left valign-top"></td>
2399 <td class="tableblock halign-left valign-top"></td>
2400 </tr>
2401 <tr>
2402 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, recursive</p></td>
2403 <td class="tableblock halign-left valign-top"><p class="tableblock">0.8</p></td>
2404 <td class="tableblock halign-left valign-top"><p class="tableblock">4.6</p></td>
2405 <td class="tableblock halign-left valign-top"><p class="tableblock">13.6</p></td>
2406 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2407 <td class="tableblock halign-left valign-top"></td>
2408 <td class="tableblock halign-left valign-top"></td>
2409 <td class="tableblock halign-left valign-top"></td>
2410 <td class="tableblock halign-left valign-top"></td>
2411 </tr>
2412 </tbody>
2413 </table>
2414 <div class="paragraph">
2415 <p>What can we do here?</p>
2416 </div>
2417 <div class="paragraph">
2418 <p>Let&#8217;s go back to <code>mp_contains</code> and look at the "mp_count/cx_plus2"
2419 implementation which we rejected in favor of the inheritance-based one. It
2420 built a <code>constexpr</code> array of booleans and summed them in a <code>constexpr</code>
2421 function. We can do the same here, except instead of summing the array, we can
2422 find the index of the first true value:</p>
2423 </div>
2424 <div class="listingblock">
2425 <div class="content">
2426 <pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;
2427
2428 template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;
2429
2430 template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
2431 {
2432     using type = mp_size_t&lt;0&gt;;
2433 };
2434
2435 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
2436 {
2437     return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
2438 }
2439
2440 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
2441     struct mp_find_index_impl&lt;L&lt;T...&gt;, V&gt;
2442 {
2443     static constexpr bool _v[] = { std::is_same&lt;T, V&gt;::value... };
2444
2445     using type = mp_size_t&lt; cx_find_index( _v, _v + sizeof...(T) ) &gt;;
2446 };</code></pre>
2447 </div>
2448 </div>
2449 <div class="paragraph">
2450 <p>The performance of this version is:</p>
2451 </div>
2452 <table class="tableblock frame-all grid-all stretch">
2453 <colgroup>
2454 <col style="width: 11.1111%;">
2455 <col style="width: 11.1111%;">
2456 <col style="width: 11.1111%;">
2457 <col style="width: 11.1111%;">
2458 <col style="width: 11.1111%;">
2459 <col style="width: 11.1111%;">
2460 <col style="width: 11.1111%;">
2461 <col style="width: 11.1111%;">
2462 <col style="width: 11.1112%;">
2463 </colgroup>
2464 <thead>
2465 <tr>
2466 <th class="tableblock halign-left valign-top"></th>
2467 <th class="tableblock halign-left valign-top">N=100</th>
2468 <th class="tableblock halign-left valign-top">N=200</th>
2469 <th class="tableblock halign-left valign-top">N=300</th>
2470 <th class="tableblock halign-left valign-top">N=400</th>
2471 <th class="tableblock halign-left valign-top">N=500</th>
2472 <th class="tableblock halign-left valign-top">N=600</th>
2473 <th class="tableblock halign-left valign-top">N=700</th>
2474 <th class="tableblock halign-left valign-top">N=800</th>
2475 </tr>
2476 </thead>
2477 <tbody>
2478 <tr>
2479 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, constexpr</p></td>
2480 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
2481 <td class="tableblock halign-left valign-top"><p class="tableblock">1.3</p></td>
2482 <td class="tableblock halign-left valign-top"><p class="tableblock">2.9</p></td>
2483 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2484 <td class="tableblock halign-left valign-top"></td>
2485 <td class="tableblock halign-left valign-top"></td>
2486 <td class="tableblock halign-left valign-top"></td>
2487 <td class="tableblock halign-left valign-top"></td>
2488 </tr>
2489 <tr>
2490 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, constexpr</p></td>
2491 <td class="tableblock halign-left valign-top"><p class="tableblock">0.5</p></td>
2492 <td class="tableblock halign-left valign-top"><p class="tableblock">1.4</p></td>
2493 <td class="tableblock halign-left valign-top"><p class="tableblock">3.1</p></td>
2494 <td class="tableblock halign-left valign-top"><p class="tableblock">5.5</p></td>
2495 <td class="tableblock halign-left valign-top"><p class="tableblock">8.7</p></td>
2496 <td class="tableblock halign-left valign-top"><p class="tableblock">13.0</p></td>
2497 <td class="tableblock halign-left valign-top"><p class="tableblock">18.0</p></td>
2498 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2499 </tr>
2500 </tbody>
2501 </table>
2502 <div class="paragraph">
2503 <p>which, while not ideal, is significantly better than our recursive punching
2504 bag. But if our compiler of choice is VC++ 2013, we can&#8217;t use <code>constexpr</code>.</p>
2505 </div>
2506 <div class="paragraph">
2507 <p>We may attempt an implementation along the same lines, but with the <code>constexpr</code>
2508 function replaced with ordinary metaprogramming:</p>
2509 </div>
2510 <div class="listingblock">
2511 <div class="content">
2512 <pre class="highlight"><code>template&lt;class L, class V&gt; struct mp_find_index_impl;
2513
2514 template&lt;class L, class V&gt; using mp_find_index = typename mp_find_index_impl&lt;L, V&gt;::type;
2515
2516 template&lt;template&lt;class...&gt; class L, class V&gt; struct mp_find_index_impl&lt;L&lt;&gt;, V&gt;
2517 {
2518     using type = mp_size_t&lt;0&gt;;
2519 };
2520
2521 template&lt;bool...&gt; struct find_index_impl_;
2522
2523 template&lt;&gt; struct find_index_impl_&lt;&gt;
2524 {
2525     static const std::size_t value = 0;
2526 };
2527
2528 template&lt;bool B1, bool... R&gt; struct find_index_impl_&lt;B1, R...&gt;
2529 {
2530     static const std::size_t value = B1? 0: 1 + find_index_impl_&lt;R...&gt;::value;
2531 };
2532
2533 template&lt;bool B1, bool B2, bool B3, bool B4, bool B5,
2534     bool B6, bool B7, bool B8, bool B9, bool B10, bool... R&gt;
2535     struct find_index_impl_&lt;B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, R...&gt;
2536 {
2537     static const std::size_t value = B1? 0: B2? 1: B3? 2: B4? 3: B5? 4:
2538         B6? 5: B7? 6: B8? 7: B9? 8: B10? 9: 10 + find_index_impl_&lt;R...&gt;::value;
2539 };
2540
2541 template&lt;template&lt;class...&gt; class L, class... T, class V&gt;
2542     struct mp_find_index_impl&lt;L&lt;T...&gt;, V&gt;
2543 {
2544     using type = mp_size_t&lt;find_index_impl_&lt;std::is_same&lt;T, V&gt;::value...&gt;::value&gt;;
2545 };</code></pre>
2546 </div>
2547 </div>
2548 <div class="paragraph">
2549 <p>This is still recursive, so we don&#8217;t expect miracles, but it wouldn&#8217;t hurt to
2550 measure:</p>
2551 </div>
2552 <table class="tableblock frame-all grid-all stretch">
2553 <colgroup>
2554 <col style="width: 11.1111%;">
2555 <col style="width: 11.1111%;">
2556 <col style="width: 11.1111%;">
2557 <col style="width: 11.1111%;">
2558 <col style="width: 11.1111%;">
2559 <col style="width: 11.1111%;">
2560 <col style="width: 11.1111%;">
2561 <col style="width: 11.1111%;">
2562 <col style="width: 11.1112%;">
2563 </colgroup>
2564 <thead>
2565 <tr>
2566 <th class="tableblock halign-left valign-top"></th>
2567 <th class="tableblock halign-left valign-top">N=100</th>
2568 <th class="tableblock halign-left valign-top">N=200</th>
2569 <th class="tableblock halign-left valign-top">N=300</th>
2570 <th class="tableblock halign-left valign-top">N=400</th>
2571 <th class="tableblock halign-left valign-top">N=500</th>
2572 <th class="tableblock halign-left valign-top">N=600</th>
2573 <th class="tableblock halign-left valign-top">N=700</th>
2574 <th class="tableblock halign-left valign-top">N=800</th>
2575 </tr>
2576 </thead>
2577 <tbody>
2578 <tr>
2579 <td class="tableblock halign-left valign-top"><p class="tableblock">VC++ 2013, bool&#8230;&#8203;</p></td>
2580 <td class="tableblock halign-left valign-top"><p class="tableblock">4.7</p></td>
2581 <td class="tableblock halign-left valign-top"><p class="tableblock">94.5</p></td>
2582 <td class="tableblock halign-left valign-top"><p class="tableblock">488.3</p></td>
2583 <td class="tableblock halign-left valign-top"><p class="tableblock">XFA</p></td>
2584 <td class="tableblock halign-left valign-top"></td>
2585 <td class="tableblock halign-left valign-top"></td>
2586 <td class="tableblock halign-left valign-top"></td>
2587 <td class="tableblock halign-left valign-top"></td>
2588 </tr>
2589 <tr>
2590 <td class="tableblock halign-left valign-top"><p class="tableblock">clang++ 3.5.1, bool&#8230;&#8203;</p></td>
2591 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
2592 <td class="tableblock halign-left valign-top"><p class="tableblock">2.2</p></td>
2593 <td class="tableblock halign-left valign-top"><p class="tableblock">5.8</p></td>
2594 <td class="tableblock halign-left valign-top"><p class="tableblock">12.0</p></td>
2595 <td class="tableblock halign-left valign-top"><p class="tableblock">21.7</p></td>
2596 <td class="tableblock halign-left valign-top"><p class="tableblock">35.2</p></td>
2597 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2598 <td class="tableblock halign-left valign-top"></td>
2599 </tr>
2600 <tr>
2601 <td class="tableblock halign-left valign-top"><p class="tableblock">g++ 4.9.2, bool&#8230;&#8203;</p></td>
2602 <td class="tableblock halign-left valign-top"><p class="tableblock">0.6</p></td>
2603 <td class="tableblock halign-left valign-top"><p class="tableblock">2.4</p></td>
2604 <td class="tableblock halign-left valign-top"><p class="tableblock">6.5</p></td>
2605 <td class="tableblock halign-left valign-top"><p class="tableblock">13.2</p></td>
2606 <td class="tableblock halign-left valign-top"><p class="tableblock">23.8</p></td>
2607 <td class="tableblock halign-left valign-top"><p class="tableblock">39.1</p></td>
2608 <td class="tableblock halign-left valign-top"><p class="tableblock">59.0</p></td>
2609 <td class="tableblock halign-left valign-top"><p class="tableblock">DNF</p></td>
2610 </tr>
2611 </tbody>
2612 </table>
2613 <div class="paragraph">
2614 <p>(where XFA stands for "experimenter fell asleep".)</p>
2615 </div>
2616 <div class="paragraph">
2617 <p>This is an interesting tradeoff for VC++ 2013 and Clang. On the one hand,
2618 this implementation is slower; on the other, it doesn&#8217;t crash the compiler as
2619 easily. Which to prefer is a matter of taste and of stern evaluation of one&#8217;s
2620 needs to manipulate type lists of length 300.</p>
2621 </div>
2622 <div class="paragraph">
2623 <p>Note that once we have <code>mp_drop</code> and <code>mp_find_index</code>, we can derive the
2624 <code>mp_find&lt;L, V&gt;</code> algorithm, which returns the suffix of <code>L</code> starting with the
2625 first occurrence of <code>V</code>, if any, and an empty list otherwise, by using
2626 <code>mp_drop&lt;L, mp_find_index&lt;L, V&gt;&gt;</code>.</p>
2627 </div>
2628 </div>
2629 </div>
2630 <div class="sect1">
2631 <h2 id="conclusion">Conclusion</h2>
2632 <div class="sectionbody">
2633 <div class="paragraph">
2634 <p>In this article, I have shown efficient algorithms that allow us to treat type
2635 lists as sets, maps and vectors, demonstrating various C&#43;&#43;11 implementation
2636 techniques in the process.</p>
2637 </div>
2638 </div>
2639 </div>
2640 </div>
2641 <div id="footer">
2642 <div id="footer-text">
2643 Last updated 2019-12-10 00:19:27 UTC
2644 </div>
2645 </div>
2646 <style>
2647
2648 *:not(pre)>code { background: none; color: #600000; }
2649 /* table tr.even, table tr.alt, table tr:nth-of-type(even) { background: none; } */
2650
2651 </style>
2652 </body>
2653 </html>