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++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";*/ 15article,aside,details,figcaption,figure,footer,header,hgroup,main,nav,section,summary{display:block} 16audio,canvas,video{display:inline-block} 17audio:not([controls]){display:none;height:0} 18script{display:none!important} 19html{font-family:sans-serif;-ms-text-size-adjust:100%;-webkit-text-size-adjust:100%} 20a{background:transparent} 21a:focus{outline:thin dotted} 22a:active,a:hover{outline:0} 23h1{font-size:2em;margin:.67em 0} 24abbr[title]{border-bottom:1px dotted} 25b,strong{font-weight:bold} 26dfn{font-style:italic} 27hr{-moz-box-sizing:content-box;box-sizing:content-box;height:0} 28mark{background:#ff0;color:#000} 29code,kbd,pre,samp{font-family:monospace;font-size:1em} 30pre{white-space:pre-wrap} 31q{quotes:"\201C" "\201D" "\2018" "\2019"} 32small{font-size:80%} 33sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline} 34sup{top:-.5em} 35sub{bottom:-.25em} 36img{border:0} 37svg:not(:root){overflow:hidden} 38figure{margin:0} 39fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em} 40legend{border:0;padding:0} 41button,input,select,textarea{font-family:inherit;font-size:100%;margin:0} 42button,input{line-height:normal} 43button,select{text-transform:none} 44button,html input[type="button"],input[type="reset"],input[type="submit"]{-webkit-appearance:button;cursor:pointer} 45button[disabled],html input[disabled]{cursor:default} 46input[type="checkbox"],input[type="radio"]{box-sizing:border-box;padding:0} 47button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0} 48textarea{overflow:auto;vertical-align:top} 49table{border-collapse:collapse;border-spacing:0} 50*,*::before,*::after{-moz-box-sizing:border-box;-webkit-box-sizing:border-box;box-sizing:border-box} 51html,body{font-size:100%} 52body{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} 53a:hover{cursor:pointer} 54img,object,embed{max-width:100%;height:auto} 55object,embed{height:100%} 56img{-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} 64img,object,svg{display:inline-block;vertical-align:middle} 65textarea{height:auto;min-height:50px} 66select{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} 70div,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} 71a{color:#2156a5;text-decoration:underline;line-height:inherit} 72a:hover,a:focus{color:#1d4b8f} 73a img{border:none} 74p{font-family:inherit;font-weight:400;font-size:1em;line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility} 75p aside{font-size:.875em;line-height:1.35;font-style:italic} 76h1,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} 77h1 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} 78h1{font-size:2.125em} 79h2{font-size:1.6875em} 80h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em} 81h4,h5{font-size:1.125em} 82h6{font-size:1em} 83hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em;height:0} 84em,i{font-style:italic;line-height:inherit} 85strong,b{font-weight:bold;line-height:inherit} 86small{font-size:60%;line-height:inherit} 87code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)} 88ul,ol,dl{font-size:1em;line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit} 89ul,ol{margin-left:1.5em} 90ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0;font-size:1em} 91ul.square li ul,ul.circle li ul,ul.disc li ul{list-style:inherit} 92ul.square{list-style-type:square} 93ul.circle{list-style-type:circle} 94ul.disc{list-style-type:disc} 95ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0} 96dl dt{margin-bottom:.3125em;font-weight:bold} 97dl dd{margin-bottom:1.25em} 98abbr,acronym{text-transform:uppercase;font-size:90%;color:rgba(0,0,0,.8);border-bottom:1px dotted #ddd;cursor:help} 99abbr{text-transform:none} 100blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd} 101blockquote cite{display:block;font-size:.9375em;color:rgba(0,0,0,.6)} 102blockquote cite::before{content:"\2014 \0020"} 103blockquote cite a,blockquote cite a:visited{color:rgba(0,0,0,.6)} 104blockquote,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} 106h1{font-size:2.75em} 107h2{font-size:2.3125em} 108h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em} 109h4{font-size:1.4375em}} 110table{background:#fff;margin-bottom:1.25em;border:solid 1px #dedede} 111table thead,table tfoot{background:#f7f8f7} 112table 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} 113table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)} 114table tr.even,table tr.alt,table tr:nth-of-type(even){background:#f8f8f7} 115table 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} 116h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em} 117h1 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} 123pre,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} 124em em{font-style:normal} 125strong strong{font-weight:400} 126.keyseq{color:rgba(51,51,51,.8)} 127kbd{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} 135b.button::before,b.button::after{position:relative;top:-1px;font-weight:400} 136b.button::before{content:"[";padding:0 3px 0 2px} 137b.button::after{content:"]";padding:0 2px 0 3px} 138p 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} 167body.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} 173body.toc2.toc-right{padding-left:0;padding-right:15em} 174body.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} 180body.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} 199table.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)} 201table.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:"$"} 231table.pyhltable{border-collapse:separate;border:0;margin-bottom:0;background:none} 232table.pyhltable td{vertical-align:top;padding-top:0;padding-bottom:0;line-height:1.45} 233table.pyhltable td.code{padding-left:.75em;padding-right:0} 234pre.pygments .lineno,table.pyhltable td:not(.code){color:#999;padding-left:0;padding-right:.5em;border-right:1px solid #dddddf} 235pre.pygments .lineno{display:inline-block;margin-right:.25em} 236table.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} 258table.tableblock{max-width:100%;border-collapse:separate} 259p.tableblock:last-child{margin-bottom:0} 260td.tableblock>.content{margin-bottom:-1.25em} 261table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede} 262table.grid-all>thead>tr>.tableblock,table.grid-all>tbody>tr>.tableblock{border-width:0 1px 1px 0} 263table.grid-all>tfoot>tr>.tableblock{border-width:1px 1px 0 0} 264table.grid-cols>*>tr>.tableblock{border-width:0 1px 0 0} 265table.grid-rows>thead>tr>.tableblock,table.grid-rows>tbody>tr>.tableblock{border-width:0 0 1px} 266table.grid-rows>tfoot>tr>.tableblock{border-width:1px 0 0} 267table.grid-all>*>tr>.tableblock:last-child,table.grid-cols>*>tr>.tableblock:last-child{border-right-width:0} 268table.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} 269table.frame-all{border-width:1px} 270table.frame-sides{border-width:0 1px} 271table.frame-topbot,table.frame-ends{border-width:1px 0} 272table.stripes-all tr,table.stripes-odd tr:nth-of-type(odd){background:#f8f8f7} 273table.stripes-none tr,table.stripes-odd tr:nth-of-type(even){background:none} 274th.halign-left,td.halign-left{text-align:left} 275th.halign-right,td.halign-right{text-align:right} 276th.halign-center,td.halign-center{text-align:center} 277th.valign-top,td.valign-top{vertical-align:top} 278th.valign-bottom,td.valign-bottom{vertical-align:bottom} 279th.valign-middle,td.valign-middle{vertical-align:middle} 280table thead th,table tfoot th{font-weight:bold} 281tbody tr th{display:table-cell;line-height:1.6;background:#f7f8f7} 282tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold} 283p.tableblock>code:only-child{background:none;padding:0} 284p.tableblock{font-size:1em} 285td>div.verse{white-space:pre} 286ol{margin-left:1.75em} 287ul li ol{margin-left:1.5em} 288dl dd{margin-left:1.125em} 289dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0} 290ol>li p,ul>li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em} 291ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none} 292ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em} 293ul.unstyled,ol.unstyled{margin-left:0} 294ul.checklist{margin-left:.625em} 295ul.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} 296ul.checklist li>p:first-child>input[type="checkbox"]:first-child{margin-right:.25em} 297ul.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} 298ul.inline>li{margin-left:1.25em} 299.unstyled dl dt{font-weight:400;font-style:normal} 300ol.arabic{list-style-type:decimal} 301ol.decimal{list-style-type:decimal-leading-zero} 302ol.loweralpha{list-style-type:lower-alpha} 303ol.upperalpha{list-style-type:upper-alpha} 304ol.lowerroman{list-style-type:lower-roman} 305ol.upperroman{list-style-type:upper-roman} 306ol.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} 309td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em} 310td.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} 324a.image{text-decoration:none;display:inline-block} 325a.image object{pointer-events:none} 326sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super} 327sup.footnote a,sup.footnoteref a{text-decoration:none} 328sup.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%} 337div.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} 375span.icon>.fa{cursor:default} 376a 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)} 387pre .conum[data-value]{position:relative;top:-.125em} 388b.conum *{color:inherit!important} 389.conum:not([data-value]):empty{display:none} 390dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility} 391h1,h2,p,td.content,span.alt{letter-spacing:-.01em} 392p strong,td.content strong,div.footnote strong{letter-spacing:-.005em} 393p,blockquote,dt,td.content,span.alt{font-size:1.0625rem} 394p{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} 400html{font-size:80%} 401a{color:inherit!important;text-decoration:underline!important} 402a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important} 403a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em} 404abbr[title]::after{content:" (" attr(title) ")"} 405pre,blockquote,tr,img,object,svg{page-break-inside:avoid} 406thead{display:table-header-group} 407svg{max-width:100%} 408p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3} 409h2,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} 412body.book #header{text-align:center} 413body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em} 414body.book #header .details{border:0!important;display:block;padding:0!important} 415body.book #header .details span:first-child{margin-left:0!important} 416body.book #header .details br{display:block} 417body.book #header .details br+span::before{content:none!important} 418body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important} 419body.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++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 459key</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"> 468Being late to the metaprogramming party, I make no claim of having 469invented the techniques in this article. A quick look at the implementations 470of, for example, Louis Dionne’s <a href="https://github.com/ldionne/mpl11">mpl11</a> and 471Eric Niebler’s <a href="https://github.com/ericniebler/meta">meta</a>, shows that most of 472these tricks are already known. Dave Abrahams 473<a href="https://github.com/dabrahams/mpl11">has experimented</a> along these lines in 2012. 474The original inventor of the multiple inheritance trick and the <code>void*</code> 475arguments 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 490metaprogramming that operated on type lists — variadic class templates:</p> 491</div> 492<div class="listingblock"> 493<div class="content"> 494<pre class="highlight"><code>template<class... T> 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 499usually 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> 503supports random access by index; <code>set</code> has efficient test for membership; <code>map</code> 504associates 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’ll keep our data in a list form, and attempt to provide efficient 509algorithms 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’s starts with sets. A set is just a list with unique elements. To obtain a 518set from an arbitrary list, we’ll need an algorithm that removes the 519duplicates. Let’s call it <code>mp_unique<L></code>:</p> 520</div> 521<div class="listingblock"> 522<div class="content"> 523<pre class="highlight"><code>// mp_if 524 525template<bool C, class T, class E> struct mp_if_c_impl; 526 527template<class T, class E> struct mp_if_c_impl<true, T, E> 528{ 529 using type = T; 530}; 531 532template<class T, class E> struct mp_if_c_impl<false, T, E> 533{ 534 using type = E; 535}; 536 537template<bool C, class T, class E> 538 using mp_if_c = typename mp_if_c_impl<C, T, E>::type; 539 540template<class C, class T, class E> 541 using mp_if = typename mp_if_c_impl<C::value != 0, T, E>::type; 542 543// mp_unique 544 545template<class L> struct mp_unique_impl; 546 547template<class L> using mp_unique = typename mp_unique_impl<L>::type; 548 549template<template<class...> class L> struct mp_unique_impl<L<>> 550{ 551 using type = L<>; 552}; 553 554template<template<class...> class L, class T1, class... T> 555 struct mp_unique_impl<L<T1, T...>> 556{ 557 using _rest = mp_unique<L<T...>>; 558 using type = mp_if<<strong>mp_contains</strong><_rest, T1>, _rest, mp_push_front<_rest, T1>>; 559};</code></pre> 560</div> 561</div> 562<div class="paragraph"> 563<p>For membership testing, we’ve introduced an algorithm <code>mp_contains<L, V></code> that 564returns <code>true</code> when <code>L</code> contains <code>V</code>. The straightforward recursive 565implementation of <code>mp_contains</code> is:</p> 566</div> 567<div class="listingblock"> 568<div class="content"> 569<pre class="highlight"><code>template<class L, class V> struct mp_contains_impl; 570 571template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type; 572 573template<template<class...> class L, class V> struct mp_contains_impl<L<>, V> 574{ 575 using type = std::false_type; 576}; 577 578template<template<class...> class L, class... T, class V> 579 struct mp_contains_impl<L<V, T...>, V> 580{ 581 using type = std::true_type; 582}; 583 584template<template<class...> class L, class T1, class... T, class V> 585 struct mp_contains_impl<L<T1, T...>, V>: mp_contains_impl<L<T...>, V> 586{ 587};</code></pre> 588</div> 589</div> 590<div class="paragraph"> 591<p>Note that <code>mp_unique<L></code> makes <code>N</code> calls to <code>mp_contains</code>, where <code>N</code> is the 592length of the list <code>L</code>. This means that <code>mp_contains</code> needs to be as fast as 593possible, which the above implementation, well, isn’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. 662DNF stands for "did not finish", which usually means that the compiler ran out 663of 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 670relied on <code>mp_count</code>, which in turn relied on <code>mp_plus</code>. Let’s see how it 671fares:</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 736ought 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 740expansion, to do more of the work for us. For inspiration, let’s turn to 741section 14.5.3 paragraph 4 of the C++11 standard, which explains that pack 742expansions 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 793call. Since we’re interested in operations that occur at compile time, calling 794a function may not appear useful; but C++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<class L, class V> struct mp_count_impl; 803 804template<template<class...> class L, class... T, class V> 805 struct mp_count_impl<L<T...>, V> 806{ 807 using type = mp_plus<std::is_same<T, V>...>; 808}; 809 810template<class L, class V> using mp_count = typename mp_count_impl<L, V>::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, 815we 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 824template<class T1, class... T> constexpr std::size_t cx_plus(T1 t1, T... t) 825{ 826 return t1 + cx_plus(t...); 827} 828 829// mp_size_t 830 831template<std::size_t N> using mp_size_t = std::integral_constant<std::size_t, N>; 832 833// mp_count 834 835template<class L, class V> struct mp_count_impl; 836 837template<template<class...> class L, class... T, class V> 838 struct mp_count_impl<L<T...>, V> 839{ 840 using type = mp_size_t<cx_plus(std::is_same<T, V>::value...)>; 841}; 842 843template<class L, class V> using mp_count = typename mp_count_impl<L, V>::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’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’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, 906then 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 917template<class L, class V> struct mp_count_impl; 918 919template<template<class...> class L, class... T, class V> 920 struct mp_count_impl<L<T...>, V> 921{ 922 static constexpr bool _v[] = { std::is_same<T, V>::value... }; 923 using type = mp_size_t<cx_plus2(_v, _v + sizeof...(T))>; 924}; 925 926template<class L, class V> using mp_count = typename mp_count_impl<L, V>::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’s a bit disappointing. Let’s see what can we do with expanding a parameter 984pack into a base-specifier-list. We would be able to define a class that 985derives 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<V, U></code> to test whether a type <code>V</code> is a base of 994<code>U</code>, that is, whether it’s one of the elements of the parameter pack. Which is 995exactly 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’t be used as base 999classes, but we’ll wrap the types in an empty class template, which we’ll call 1000<code>mp_identity</code>.</p> 1001</div> 1002<div class="listingblock"> 1003<div class="content"> 1004<pre class="highlight"><code>template<class T> struct mp_identity 1005{ 1006 using type = T; 1007}; 1008 1009template<class L, class V> struct mp_contains_impl; 1010 1011template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type; 1012 1013template<template<class...> class L, class... T, class V> 1014 struct mp_contains_impl<L<T...>, V> 1015{ 1016 struct U: mp_identity<T>... {}; 1017 using type = std::is_base_of<mp_identity<V>, U>; 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 1095duplicates, because it’s not possible to inherit directly from the same type 1096twice. So it does not implement the general <code>mp_contains</code>, but something that 1097should 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 1101inherit from <code>mp_identity<T></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 1107template<std::size_t I, class T> struct inherit_second: T {}; 1108 1109template<class L, class S> struct indirect_inherit_impl; 1110 1111template<template<class...> class L, class... T, std::size_t... J> 1112 struct indirect_inherit_impl<L<T...>, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a><std::size_t, J...>>: 1113 inherit_second<J, mp_identity<T>>... {}; 1114 1115template<class L> using indirect_inherit = 1116 indirect_inherit_impl<L, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a><mp_size<L>::value>>; 1117 1118// mp_contains 1119 1120template<class L, class V> struct mp_contains_impl 1121{ 1122 using U = indirect_inherit<L>; 1123 using type = std::is_base_of<mp_identity<V>, U>; 1124}; 1125 1126template<class L, class V> using mp_contains = typename mp_contains_impl<L, V>::type;</code></pre> 1127</div> 1128</div> 1129<div class="paragraph"> 1130<p>This, however, pretty much nullifies the spectacular performance gains we’ve 1131observed 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 1400and can efficiently retrieve, given a key, its associated value. For our 1401purposes, a map will be any list of lists for which the inner lists have at 1402least one element, the key; the rest of the elements we’ll consider to be the 1403associated 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’ll require unique keys, for reasons 1413that’ll become evident later.</p> 1414</div> 1415<div class="paragraph"> 1416<p>I’ll show two other examples of maps, this time using real C++ code:</p> 1417</div> 1418<div class="listingblock"> 1419<div class="content"> 1420<pre class="highlight"><code>using Map = mp_list<mp_list<int, int*>, mp_list<void, void*>, mp_list<char, char*>>;</code></pre> 1421</div> 1422</div> 1423<div class="listingblock"> 1424<div class="content"> 1425<pre class="highlight"><code>using Map2 = std::tuple<std::pair<int, int[2]>, std::pair<char, char[2]>>;</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>, 1430but I’ll call it <code>mp_map_find</code>. <code>mp_map_find<M, K></code> returns the element of <code>M</code> 1431whose first element is <code>K</code>. For example, <code>mp_map_find<Map2, int></code> would return 1432<code>std::pair<int, int[2]></code>. If there’s no such key, it returns <code>void</code>.</p> 1433</div> 1434<div class="paragraph"> 1435<p>There’s almost no need to implement and benchmark the recursive version of 1436<code>mp_map_find</code> — 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<class M, class K> struct mp_map_find_impl; 1441 1442template<class M, class K> using mp_map_find = typename mp_map_find_impl<M, K>::type; 1443 1444template<template<class...> class M, class K> struct mp_map_find_impl<M<>, K> 1445{ 1446 using type = void; 1447}; 1448 1449template<template<class...> class M, class T1, class... T, class K> 1450 struct mp_map_find_impl<M<T1, T...>, K> 1451{ 1452 using type = mp_if<std::is_same<mp_front<T1>, K>, T1, mp_map_find<M<T...>, K>>; 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 1458follows:</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’re evaluating the else branch even if the 1526condition is true, and that’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 1530on average, and only if the element is present, but fine, let’s try it. The 1531element happens to be present in the benchmark, so let’s see.</p> 1532</div> 1533<div class="listingblock"> 1534<div class="content"> 1535<pre class="highlight"><code>// mp_eval_if 1536 1537template<bool C, class T, template<class...> class E, class... A> 1538 struct mp_eval_if_c_impl; 1539 1540template<class T, template<class...> class E, class... A> 1541 struct mp_eval_if_c_impl<true, T, E, A...> 1542{ 1543 using type = T; 1544}; 1545 1546template<class T, template<class...> class E, class... A> 1547 struct mp_eval_if_c_impl<false, T, E, A...> 1548{ 1549 using type = E<A...>; 1550}; 1551 1552template<bool C, class T, template<class...> class E, class... A> 1553 using mp_eval_if_c = typename mp_eval_if_c_impl<C, T, E, A...>::type; 1554 1555template<class C, class T, template<class...> class E, class... A> 1556 using mp_eval_if = typename mp_eval_if_c_impl<C::value != 0, T, E, A...>::type; 1557 1558// mp_map_find 1559 1560template<class M, class K> struct mp_map_find_impl; 1561 1562template<class M, class K> using mp_map_find = typename mp_map_find_impl<M, K>::type; 1563 1564template<template<class...> class M, class K> struct mp_map_find_impl<M<>, K> 1565{ 1566 using type = void; 1567}; 1568 1569template<template<class...> class M, class T1, class... T, class K> 1570 struct mp_map_find_impl<M<T1, T...>, K> 1571{ 1572 using type = mp_eval_if<std::is_same<mp_front<T1>, K>, T1, mp_map_find, M<T...>, K>; 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 1645not the same as to come up with an efficient one. There are two things that 1646make 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 1648type, and second, in <code>mp_contains</code> we knew the exact type of the element for 1649which 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++ can 1653deduce the template parameters of base classes when passed a derived class. In 1654this example,</p> 1655</div> 1656<div class="listingblock"> 1657<div class="content"> 1658<pre class="highlight"><code>struct K1 {}; 1659struct V1 {}; 1660 1661struct X: std::pair<K1, V1> {}; 1662 1663template<class A, class B> void f(std::pair<A, B> const & p); 1664 1665int 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 1673one <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 {}; 1678struct V1 {}; 1679 1680struct K2 {}; 1681struct V2 {}; 1682 1683struct X: std::pair<K1, V1>, std::pair<K2, V2> {}; 1684 1685template<class B> void f(std::pair<K1, B> const & p); 1686 1687int 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<class B> std::pair<K1, B> f(std::pair<K1, B> const & 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’t have a base of type <code>std::pair<K1, B></code>? The deduction will 1709fail and we’ll get an error that <code>f(X())</code> cannot be called. To avoid it, we can 1710add an overload of <code>f</code> that takes anything and returns <code>void</code>. But in this 1711case, 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<K1, Y></code> and <code>std::pair<K1, Z></code>?</p> 1713</div> 1714<div class="paragraph"> 1715<p>The deduction will fail, the second overload will again be chosen and we’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’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<class M, class K> struct mp_map_find_impl; 1724 1725template<class M, class K> 1726 using mp_map_find = typename mp_map_find_impl<M, K>::type; 1727 1728template<template<class...> class M, class... T, class K> 1729 struct mp_map_find_impl<M<T...>, K> 1730{ 1731 struct U: mp_identity<T>... {}; 1732 1733 template<template<class...> class L, class... U> 1734 static mp_identity<L<K, U...>> 1735 f( mp_identity<L<K, U...>>* ); 1736 1737 static mp_identity<void> 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<M, K1></code>, then <code>mp_map_find<M, K2></code>, the two nested <code>U</code> types are 1815the same as they only depend on <code>M</code>, but the compiler doesn’t know that and 1816will 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<class... T> struct <strong>mp_inherit</strong>: T... {}; 1822 1823template<class M, class K> struct mp_map_find_impl; 1824 1825template<class M, class K> 1826 using mp_map_find = typename mp_map_find_impl<M, K>::type; 1827 1828template<template<class...> class M, class... T, class K> 1829 struct mp_map_find_impl<M<T...>, K> 1830{ 1831 <strong>using U = mp_inherit<mp_identity<T>...>;</strong> 1832 1833 template<template<class...> class L, class... U> 1834 static mp_identity<L<K, U...>> 1835 f( mp_identity<L<K, U...>>* ); 1836 1837 static mp_identity<void> 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 1847of <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’s time to tackle vectors. Vectors for us are 1920just lists, to which we’ll need to add the ability to efficiently access an 1921element based on its index. The customary name for this accessor is 1922<code>mp_at<L, I></code>, where <code>L</code> is a list and <code>I</code> is an <code>integral_constant</code> that 1923represents the index. We’ll also follow the Boost.MPL convention and add 1924<code>mp_at_c<L, I></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<class L, std::size_t I> struct mp_at_c_impl; 1932 1933template<class L, std::size_t I> using mp_at_c = typename mp_at_c_impl<L, I>::type; 1934 1935template<class L, class I> using mp_at = typename mp_at_c_impl<L, I::value>::type; 1936 1937template<template<class...> class L, class T1, class... T> 1938 struct mp_at_c_impl<L<T1, T...>, 0> 1939{ 1940 using type = T1; 1941}; 1942 1943template<template<class...> class L, class T1, class... T, std::size_t I> 1944 struct mp_at_c_impl<L<T1, T...>, I> 1945{ 1946 using type = mp_at_c<L<T...>, I-1>; 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> 1952as 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’ll again exploit pack expansion into a 2017function call, but in a novel way. Let’s suppose that we need to access the 2018fourth element (<code>I = 3</code>). We’ll generate the function signature</p> 2019</div> 2020<div class="listingblock"> 2021<div class="content"> 2022<pre class="highlight"><code>template<class W> 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<T1, T2, T3, T4, T5, T6, T7></code>, we’ll evaluate the 2027expression</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 2036deduced 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 2045template<std::size_t N, class... T> struct mp_repeat_c_impl 2046{ 2047 using _l1 = typename mp_repeat_c_impl<N/2, T...>::type; 2048 using _l2 = typename mp_repeat_c_impl<N%2, T...>::type; 2049 2050 using type = mp_append<_l1, _l1, _l2>; 2051}; 2052 2053template<class... T> struct mp_repeat_c_impl<0, T...> 2054{ 2055 using type = mp_list<>; 2056}; 2057 2058template<class... T> struct mp_repeat_c_impl<1, T...> 2059{ 2060 using type = mp_list<T...>; 2061}; 2062 2063template<std::size_t N, class... T> using mp_repeat_c = 2064 typename mp_repeat_c_impl<N, T...>::type; 2065 2066// mp_at 2067 2068template<class L, class L2> struct mp_at_c_impl; 2069 2070template<template<class...> class L, class... T, 2071 template<class...> class L2, class... U> 2072 struct mp_at_c_impl<L<T...>, L2<U...>> 2073{ 2074 template<class W> static W f( U*..., W*, ... ); 2075 2076 using R = decltype( f( (mp_identity<T>*)0 ... ) ); 2077 2078 using type = typename R::type; 2079}; 2080 2081template<class L, std::size_t I> using mp_at_c = 2082 typename mp_at_c_impl<L, mp_repeat_c<I, void>>::type; 2083 2084template<class L, class I> using mp_at = mp_at_c<L, I::value>;</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 2089practical 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’s try something else — 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 2163template<class L, class S> struct mp_map_from_list_impl; 2164 2165template<template<class...> class L, class... T, std::size_t... J> 2166 struct mp_map_from_list_impl<L<T...>, <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">integer_sequence</a><std::size_t, J...>> 2167{ 2168 using type = mp_list<mp_list<mp_size_t<J>, T>...>; 2169}; 2170 2171template<class L> using mp_map_from_list = typename mp_map_from_list_impl<L, 2172 <a href="http://en.cppreference.com/w/cpp/utility/integer_sequence">make_index_sequence</a><mp_size<L>::value>>::type; 2173 2174// mp_at 2175 2176template<class L, std::size_t I> struct mp_at_c_impl 2177{ 2178 using map = mp_map_from_list<L>; 2179 using type = mp_second<mp_map_find<map, mp_size_t<I>>>; 2180}; 2181 2182template<class L, std::size_t I> using mp_at_c = typename mp_at_c_impl<L, I>::type; 2183 2184template<class L, class I> using mp_at = typename mp_at_c_impl<L, I::value>::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. 2189Let’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’t need the <code>void*</code> trick for <code>mp_at</code>, but I’ll show 2262an example where we do: <code>mp_drop</code>. <code>mp_drop<L, N></code> returns the list <code>L</code> without 2263its 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’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<class W> 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<class... W> mp_list<W> 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 2284implementation:</p> 2285</div> 2286<div class="listingblock"> 2287<div class="content"> 2288<pre class="highlight"><code>template<class L, class L2> struct mp_drop_c_impl; 2289 2290template<template<class...> class L, class... T, 2291 template<class...> class L2, class... U> 2292 struct mp_drop_c_impl<L<T...>, L2<U...>> 2293{ 2294 template<class... W> static mp_identity<L<W...>> f( U*..., mp_identity<W>*... ); 2295 2296 using R = decltype( f( (mp_identity<T>*)0 ... ) ); 2297 2298 using type = typename R::type; 2299}; 2300 2301template<class L, std::size_t N> using mp_drop_c = 2302 typename mp_drop_c_impl<L, mp_repeat_c<N, void>>::type; 2303 2304template<class L, class N> using mp_drop = mp_drop_c<L, N::value>;</code></pre> 2305</div> 2306</div> 2307<div class="paragraph"> 2308<p>I’ll skip the recursive implementation and the performance comparison for this 2309one. We can pretty much tell who’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’ll bring to your attention is <code>mp_find_index</code>. 2318<code>mp_find_index<L, V></code> returns an integral constant of type <code>size_t</code> with a 2319value 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’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<class L, class V> struct mp_find_index_impl; 2328 2329template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type; 2330 2331template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V> 2332{ 2333 using type = mp_size_t<0>; 2334}; 2335 2336template<template<class...> class L, class... T, class V> 2337 struct mp_find_index_impl<L<V, T...>, V> 2338{ 2339 using type = mp_size_t<0>; 2340}; 2341 2342template<template<class...> class L, class T1, class... T, class V> 2343 struct mp_find_index_impl<L<T1, T...>, V> 2344{ 2345 using type = mp_size_t<1 + mp_find_index<L<T...>, V>::value>; 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 2351list 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’s go back to <code>mp_contains</code> and look at the "mp_count/cx_plus2" 2419implementation which we rejected in favor of the inheritance-based one. It 2420built a <code>constexpr</code> array of booleans and summed them in a <code>constexpr</code> 2421function. We can do the same here, except instead of summing the array, we can 2422find the index of the first true value:</p> 2423</div> 2424<div class="listingblock"> 2425<div class="content"> 2426<pre class="highlight"><code>template<class L, class V> struct mp_find_index_impl; 2427 2428template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type; 2429 2430template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V> 2431{ 2432 using type = mp_size_t<0>; 2433}; 2434 2435constexpr 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 2440template<template<class...> class L, class... T, class V> 2441 struct mp_find_index_impl<L<T...>, V> 2442{ 2443 static constexpr bool _v[] = { std::is_same<T, V>::value... }; 2444 2445 using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >; 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 2504bag. But if our compiler of choice is VC++ 2013, we can’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> 2508function replaced with ordinary metaprogramming:</p> 2509</div> 2510<div class="listingblock"> 2511<div class="content"> 2512<pre class="highlight"><code>template<class L, class V> struct mp_find_index_impl; 2513 2514template<class L, class V> using mp_find_index = typename mp_find_index_impl<L, V>::type; 2515 2516template<template<class...> class L, class V> struct mp_find_index_impl<L<>, V> 2517{ 2518 using type = mp_size_t<0>; 2519}; 2520 2521template<bool...> struct find_index_impl_; 2522 2523template<> struct find_index_impl_<> 2524{ 2525 static const std::size_t value = 0; 2526}; 2527 2528template<bool B1, bool... R> struct find_index_impl_<B1, R...> 2529{ 2530 static const std::size_t value = B1? 0: 1 + find_index_impl_<R...>::value; 2531}; 2532 2533template<bool B1, bool B2, bool B3, bool B4, bool B5, 2534 bool B6, bool B7, bool B8, bool B9, bool B10, bool... R> 2535 struct find_index_impl_<B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, R...> 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_<R...>::value; 2539}; 2540 2541template<template<class...> class L, class... T, class V> 2542 struct mp_find_index_impl<L<T...>, V> 2543{ 2544 using type = mp_size_t<find_index_impl_<std::is_same<T, V>::value...>::value>; 2545};</code></pre> 2546</div> 2547</div> 2548<div class="paragraph"> 2549<p>This is still recursive, so we don’t expect miracles, but it wouldn’t hurt to 2550measure:</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…​</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…​</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…​</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, 2618this implementation is slower; on the other, it doesn’t crash the compiler as 2619easily. Which to prefer is a matter of taste and of stern evaluation of one’s 2620needs 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<L, V></code> algorithm, which returns the suffix of <code>L</code> starting with the 2625first occurrence of <code>V</code>, if any, and an empty list otherwise, by using 2626<code>mp_drop<L, mp_find_index<L, V>></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 2635lists as sets, maps and vectors, demonstrating various C++11 implementation 2636techniques in the process.</p> 2637</div> 2638</div> 2639</div> 2640</div> 2641<div id="footer"> 2642<div id="footer-text"> 2643Last updated 2020-08-11 14:56:30 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>