Commits

Tim Day committed 8569d19

Add processed article to repository

  • Participants
  • Parent commits 497822a

Comments (0)

Files changed (3)

article/README.md

+LRU cache implementation in C++
+===============================
+
+This is the HTML and PDF versions of the article text
+(processed from LaTeX sources), provided for convenience.
+
+The source license does not apply to this content: Copyright 2010-2011 T Day.
+ 
+/* start css.sty */
+.cmr-10x-x-109{}
+.pncr7t-x-x-109{font-weight: bold;}
+.pncr7t-x-x-109{font-weight: bold;}
+.pncr7t-x-x-109{font-weight: bold;}
+.pncr7t-x-x-109{font-weight: bold;}
+.pncr7t-x-x-172{font-size:156%;font-weight: bold;}
+.pncr7t-x-x-172{font-weight: bold;}
+.pncr7t-x-x-172{font-weight: bold;}
+.pncr7t-x-x-172{font-weight: bold;}
+.pncr7t-x-x-120{font-size:109%;font-weight: bold;}
+.pncr7t-x-x-120{font-weight: bold;}
+.pncr7t-x-x-120{font-weight: bold;}
+.pncr7t-x-x-120{font-weight: bold;}
+.cmsy-10x-x-120{font-size:109%;}
+.pncr7t-{font-size:90%;font-weight: bold;}
+.pncr7t-{font-weight: bold;}
+.pncr7t-{font-weight: bold;}
+.pncr7t-{font-weight: bold;}
+.pncb7t-{font-size:90%; font-weight: bold;}
+.pcrr7t-x-x-109{font-family: monospace;}
+.pcrr7t-x-x-80{font-size:72%;font-family: monospace;}
+.cmmi-10x-x-109{font-style: italic;}
+.pcrr7t-{font-size:90%;font-family: monospace;}
+.pncri7t-x-x-109{font-style: italic;}
+.pcrb7t-{font-size:90%; font-family: monospace; font-weight: bold;}
+.pcrro7t-{font-size:90%;font-family: monospace;    font-style: oblique;}
+p.noindent { text-indent: 0em }
+td p.noindent { text-indent: 0em; margin-top:0em; }
+p.nopar { text-indent: 0em; }
+p.indent{ text-indent: 1.5em }
+@media print {div.crosslinks {visibility:hidden;}}
+a img { border-top: 0; border-left: 0; border-right: 0; }
+center { margin-top:1em; margin-bottom:1em; }
+td center { margin-top:0em; margin-bottom:0em; }
+.Canvas { position:relative; }
+img.math{vertical-align:middle;}
+li p.indent { text-indent: 0em }
+li p:first-child{ margin-top:0em; }
+li p:last-child, li div:last-child { margin-bottom:0.5em; }
+li p~ul:last-child, li p~ol:last-child{ margin-bottom:0.5em; }
+.enumerate1 {list-style-type:decimal;}
+.enumerate2 {list-style-type:lower-alpha;}
+.enumerate3 {list-style-type:lower-roman;}
+.enumerate4 {list-style-type:upper-alpha;}
+div.newtheorem { margin-bottom: 2em; margin-top: 2em;}
+.obeylines-h,.obeylines-v {white-space: nowrap; }
+div.obeylines-v p { margin-top:0; margin-bottom:0; }
+.overline{ text-decoration:overline; }
+.overline img{ border-top: 1px solid black; }
+td.displaylines {text-align:center; white-space:nowrap;}
+.centerline {text-align:center;}
+.rightline {text-align:right;}
+div.verbatim {font-family: monospace; white-space: nowrap; text-align:left; clear:both; }
+.fbox {padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }
+div.fbox {display:table}
+div.center div.fbox {text-align:center; clear:both; padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }
+div.minipage{width:100%;}
+div.center, div.center div.center {text-align: center; margin-left:1em; margin-right:1em;}
+div.center div {text-align: left;}
+div.flushright, div.flushright div.flushright {text-align: right;}
+div.flushright div {text-align: left;}
+div.flushleft {text-align: left;}
+.underline{ text-decoration:underline; }
+.underline img{ border-bottom: 1px solid black; margin-bottom:1pt; }
+.framebox-c, .framebox-l, .framebox-r { padding-left:3.0pt; padding-right:3.0pt; text-indent:0pt; border:solid black 0.4pt; }
+.framebox-c {text-align:center;}
+.framebox-l {text-align:left;}
+.framebox-r {text-align:right;}
+span.thank-mark{ vertical-align: super }
+span.footnote-mark sup.textsuperscript, span.footnote-mark a sup.textsuperscript{ font-size:80%; }
+div.tabular, div.center div.tabular {text-align: center; margin-top:0.5em; margin-bottom:0.5em; }
+table.tabular td p{margin-top:0em;}
+table.tabular {margin-left: auto; margin-right: auto;}
+td p:first-child{ margin-top:0em; }
+td p:last-child{ margin-bottom:0em; }
+div.td00{ margin-left:0pt; margin-right:0pt; }
+div.td01{ margin-left:0pt; margin-right:5pt; }
+div.td10{ margin-left:5pt; margin-right:0pt; }
+div.td11{ margin-left:5pt; margin-right:5pt; }
+table[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }
+td.td00{ padding-left:0pt; padding-right:0pt; }
+td.td01{ padding-left:0pt; padding-right:5pt; }
+td.td10{ padding-left:5pt; padding-right:0pt; }
+td.td11{ padding-left:5pt; padding-right:5pt; }
+table[rules] {border-left:solid black 0.4pt; border-right:solid black 0.4pt; }
+.hline hr, .cline hr{ height : 1px; margin:0px; }
+.tabbing-right {text-align:right;}
+span.TEX {letter-spacing: -0.125em; }
+span.TEX span.E{ position:relative;top:0.5ex;left:-0.0417em;}
+a span.TEX span.E {text-decoration: none; }
+span.LATEX span.A{ position:relative; top:-0.5ex; left:-0.4em; font-size:85%;}
+span.LATEX span.TEX{ position:relative; left: -0.4em; }
+div.float, div.figure {margin-left: auto; margin-right: auto;}
+div.float img {text-align:center;}
+div.figure img {text-align:center;}
+.marginpar {width:20%; float:right; text-align:left; margin-left:auto; margin-top:0.5em; font-size:85%; text-decoration:underline;}
+.marginpar p{margin-top:0.4em; margin-bottom:0.4em;}
+table.equation {width:100%;}
+.equation td{text-align:center; }
+td.equation { margin-top:1em; margin-bottom:1em; } 
+td.equation-label { width:5%; text-align:center; }
+td.eqnarray4 { width:5%; white-space: normal; }
+td.eqnarray2 { width:5%; }
+table.eqnarray-star, table.eqnarray {width:100%;}
+div.eqnarray{text-align:center;}
+div.array {text-align:center;}
+div.pmatrix {text-align:center;}
+table.pmatrix {width:100%;}
+span.pmatrix img{vertical-align:middle;}
+div.pmatrix {text-align:center;}
+table.pmatrix {width:100%;}
+span.bar-css {text-decoration:overline;}
+img.cdots{vertical-align:middle;}
+.partToc a, .partToc, .likepartToc a, .likepartToc {line-height: 200%; font-weight:bold; font-size:110%;}
+.index-item, .index-subitem, .index-subsubitem {display:block}
+div.caption {text-indent:-2em; margin-left:3em; margin-right:1em; text-align:left;}
+div.caption span.id{font-weight: bold; white-space: nowrap; }
+h1.partHead{text-align: center}
+p.bibitem { text-indent: -2em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }
+p.bibitem-p { text-indent: 0em; margin-left: 2em; margin-top:0.6em; margin-bottom:0.6em; }
+.paragraphHead, .likeparagraphHead { margin-top:2em; font-weight: bold;}
+.subparagraphHead, .likesubparagraphHead { font-weight: bold;}
+.quote {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; margin-right:1em; text-align:justify;}
+.verse{white-space:nowrap; margin-left:2em}
+div.maketitle {text-align:center;}
+h2.titleHead{text-align:center;}
+div.maketitle{ margin-bottom: 2em; }
+div.author, div.date {text-align:center;}
+div.thanks{text-align:left; margin-left:10%; font-size:85%; font-style:italic; }
+div.author{white-space: nowrap;}
+.quotation {margin-bottom:0.25em; margin-top:0.25em; margin-left:1em; }
+.abstract p {margin-left:5%; margin-right:5%;}
+div.abstract {width:100%;}
+.lstlisting .label{margin-right:0.5em; }
+div.lstlisting{font-family: monospace; white-space: nowrap; margin-top:0.5em; margin-bottom:0.5em; }
+div.lstinputlisting{ font-family: monospace; white-space: nowrap; }
+.lstinputlisting .label{margin-right:0.5em;}
+ body {font-family: sans-serif} 
+ div.lstlisting {margin-left: 0;background: rgb(224,255,224);border-style: solid;border-left-width: 1em;border-top-width: 0.5em;border-bottom-width: 0.5em;border-color: rgb(224,255,224);} 
+ div.lstinputlisting {margin-left: 0;background: rgb(224,255,224);border-style: solid;border-left-width: 1em;border-top-width: 0;border-bottom-width: 0.5em;border-color: rgb(224,255,224);} 
+ div.lstinputlisting .pcrro7t- {color: red} 
+ div.lstinputlisting table.caption {background: rgb(64,128,64);color: white;font-family: sans-serif;margin-left: 0;padding-right: 50%} 
+td#TBL-2-1-2{border-right:solid black 0.4pt;}
+td#TBL-2-2-2{border-right:solid black 0.4pt;}
+td#TBL-3-1-2{border-right:solid black 0.4pt;}
+td#TBL-3-2-2{border-right:solid black 0.4pt;}
+/* end css.sty */
+
+<?xml version="1.0" encoding="iso-8859-1" ?> 
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 
+  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  
+<!--http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd-->  
+<html xmlns="http://www.w3.org/1999/xhtml"  
+> 
+<head>      <title>LRU cache implementation in C++</title> 
+<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> 
+<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" /> 
+<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" /> 
+<!-- html,xhtml --> 
+<meta name="src" content="lru.tex" /> 
+<meta name="date" content="2011-10-03 14:30:00" /> 
+<link rel="stylesheet" type="text/css" href="lru.css" /> 
+</head><body 
+>
+   <div class="maketitle">
+                                                                     
+
+                                                                     
+                                                                     
+
+                                                                     
+
+<h2 class="titleHead">LRU cache implementation in C++</h2>
+<div class="author" ><span 
+class="cmsy-10x-x-120">�</span><span 
+class="pncr7t-x-x-120">2010-2011 Tim Day</span>
+<br /> <span 
+class="pncr7t-x-x-120">timday@timday.com</span>
+<br />  <a 
+href="http://www.timday.com" ><span 
+class="pncr7t-x-x-120">www.timday.com</span></a></div><br />
+<div class="date" ></div>
+   </div><div 
+class="abstract" 
+>
+<div class="center" 
+>
+<!--l. 41--><p class="noindent" >
+</p><!--l. 41--><p class="noindent" ><span 
+class="pncb7t-">Abstract</span></p></div>
+     <!--l. 42--><p class="indent" >     <span 
+class="pncr7t-">A          key-value          container          providing          caching</span>
+     <span 
+class="pncr7t-">with  a  least-recently-used  replacement  strategy  is  a  useful  tool</span>
+     <span 
+class="pncr7t-">in  any  programmer&#8217;s  performance  optimisation  toolkit;  however,</span>
+     <span 
+class="pncr7t-">with  no  ready-to-use  implementations  provided  in  the  standard</span>
+     <span 
+class="pncr7t-">library or the widely used boost libraries, C++ developers are likely</span>
+     <span 
+class="pncr7t-">resort to inefficient or incorrect approximations to the logic. This</span>
+     <span 
+class="pncr7t-">document describes a couple of simple implementations built on</span>
+     <span 
+class="pncr7t-">top  of  the  C++  standard  library&#8217;s  map  types  and  on  the  boost</span>
+     <span 
+class="pncr7t-">library&#8217;s &#8220;bimap&#8221; types in the hope of making this useful pattern</span>
+     <span 
+class="pncr7t-">more accessible to coders not already familiar with it.</span>
+</p>
+</div>
+   <h3 class="likesectionHead"><a 
+ id="x1-1000"></a>Contents</h3>
+   <div class="tableofcontents">
+   <span class="sectionToc" >1 <a 
+href="#x1-20001" id="QQ2-1-2">Document history</a></span>
+<br />   <span class="sectionToc" >2 <a 
+href="#x1-30002" id="QQ2-1-3">Source code licensing</a></span>
+<br />   <span class="sectionToc" >3 <a 
+href="#x1-40003" id="QQ2-1-4">The problem</a></span>
+<br />   <span class="sectionToc" >4 <a 
+href="#x1-50004" id="QQ2-1-5">Implementations</a></span>
+                                                                     
+
+                                                                     
+<br />   <span class="sectionToc" >5 <a 
+href="#x1-60005" id="QQ2-1-6">Standard Library based LRU-cache</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >5.1 <a 
+href="#x1-70005.1" id="QQ2-1-7">Design</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >5.2 <a 
+href="#x1-80005.2" id="QQ2-1-8">Implementation</a></span>
+<br />   <span class="sectionToc" >6 <a 
+href="#x1-90006" id="QQ2-1-10">Boost bimap-based LRU-cache</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >6.1 <a 
+href="#x1-100006.1" id="QQ2-1-11">Design</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >6.2 <a 
+href="#x1-110006.2" id="QQ2-1-12">Implementation</a></span>
+<br />   <span class="sectionToc" >7 <a 
+href="#x1-120007" id="QQ2-1-14">Testing</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >7.1 <a 
+href="#x1-130007.1" id="QQ2-1-16">Unit test</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >7.2 <a 
+href="#x1-140007.2" id="QQ2-1-18">Performance testing</a></span>
+<br />   <span class="sectionToc" >8 <a 
+href="#x1-150008" id="QQ2-1-22">Variations</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >8.1 <a 
+href="#x1-160008.1" id="QQ2-1-23">Definition of &#8220;capacity&#8221;</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >8.2 <a 
+href="#x1-170008.2" id="QQ2-1-24">Thread safety</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >8.3 <a 
+href="#x1-180008.3" id="QQ2-1-25">Compressed stored values</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >8.4 <a 
+href="#x1-190008.4" id="QQ2-1-26">Alternative strategies to LRU</a></span>
+<br />   &#x00A0;<span class="subsectionToc" >8.5 <a 
+href="#x1-200008.5" id="QQ2-1-27">Pooling</a></span>
+<br />   <span class="sectionToc" >A <a 
+href="#x1-21000A" id="QQ2-1-28">Timer utility class</a></span>
+   </div>
+<!--l. 55--><p class="noindent" >
+</p>
+   <h3 class="sectionHead"><span class="titlemark">1    </span> <a 
+ id="x1-20001"></a>Document history</h3>
+     <ul class="itemize1">
+     <li class="itemize">October 2011: Updated for C++0x; added templating to permit use
+     of both hash-based &#8220;unordered&#8221; maps and conventional tree-based
+     maps. Updated performance results.
+     </li>
+     <li class="itemize">September  2011:  Bug  fixed  in  std-based  code  (in  operator(),
+     erroneous  and  unnecessary  iterator  assignment  after  splice  -
+     special  thanks  to  Marek  Fort  to  drawing  this  to  the  author&#8217;s
+     attention).
+     </li>
+     <li class="itemize">March 2011: Source code licensing clarified.
+     </li>
+     <li class="itemize">December 2010: Initial version.</li></ul>
+                                                                     
+
+                                                                     
+<!--l. 65--><p class="noindent" >
+</p>
+   <h3 class="sectionHead"><span class="titlemark">2    </span> <a 
+ id="x1-30002"></a>Source code licensing</h3>
+<!--l. 67--><p class="noindent" >While the general aim of this document is to provide its audience with
+enough information to implement their own LRU-caching classes, readers
+are welcome to cut-and-paste the code listings in this document under the
+terms of the Internet Systems Consortium (ISC) license (an OSI-approved
+BSD-alike license). The following text should be considered to apply to all
+code in this document, and added as a comment in any code copied directly
+from it:
+</p>
+   <!--l. 74-->
+<div class="lstlisting" id="listing-1"><span class="label"><a 
+ id="x1-3001r1"></a></span><span 
+class="pcrr7t-x-x-80">Copyright</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">(</span><span 
+class="pcrr7t-x-x-80">c</span><span 
+class="pcrr7t-x-x-80">)</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">2010-2011,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">Tim</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">Day</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">&#x003C;</span><span 
+class="pcrr7t-x-x-80">timday@timday</span><span 
+class="pcrr7t-x-x-80">.</span><span 
+class="pcrr7t-x-x-80">com</span><span 
+class="pcrr7t-x-x-80">&#x003E;</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3002r2"></a></span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3003r3"></a></span><span 
+class="pcrr7t-x-x-80">Permission</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">to</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">use</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">copy</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">modify</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">and</span><span 
+class="pcrr7t-x-x-80">/</span><span 
+class="pcrr7t-x-x-80">or</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">distribute</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">this</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">software</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">for</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">any</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3004r4"></a></span><span 
+class="pcrr7t-x-x-80">purpose</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">with</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">or</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">without</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">fee</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">is</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">hereby</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">granted</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">provided</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">that</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">the</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">above</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3005r5"></a></span><span 
+class="pcrr7t-x-x-80">copyright</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">notice</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">and</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">this</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">permission</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">notice</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">appear</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">in</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">all</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">copies</span><span 
+class="pcrr7t-x-x-80">.</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3006r6"></a></span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3007r7"></a></span><span 
+class="pcrr7t-x-x-80">THE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">SOFTWARE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">PROVIDED</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">"</span><span 
+class="pcrr7t-x-x-80">AS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IS</span><span 
+class="pcrr7t-x-x-80">"</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">AND</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">THE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">AUTHOR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">DISCLAIMS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">ALL</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">WARRANTIES</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3008r8"></a></span><span 
+class="pcrr7t-x-x-80">WITH</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">REGARD</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">TO</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">THIS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">SOFTWARE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">INCLUDING</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">ALL</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IMPLIED</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">WARRANTIES</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OF</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3009r9"></a></span><span 
+class="pcrr7t-x-x-80">MERCHANTABILITY</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">AND</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">FITNESS</span><span 
+class="pcrr7t-x-x-80">.</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IN</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">NO</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">EVENT</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">SHALL</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">THE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">AUTHOR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">BE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">LIABLE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">FOR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3010r10"></a></span><span 
+class="pcrr7t-x-x-80">ANY</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">SPECIAL</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">DIRECT</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">INDIRECT</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">CONSEQUENTIAL</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">DAMAGES</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">ANY</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">DAMAGES</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3011r11"></a></span><span 
+class="pcrr7t-x-x-80">WHATSOEVER</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">RESULTING</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">FROM</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">LOSS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OF</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">USE</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">DATA</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">PROFITS</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">WHETHER</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IN</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">AN</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3012r12"></a></span><span 
+class="pcrr7t-x-x-80">ACTION</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OF</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">CONTRACT</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">NEGLIGENCE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OTHER</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">TORTIOUS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">ACTION</span><span 
+class="pcrr7t-x-x-80">,</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">ARISING</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OUT</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OF</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-3013r13"></a></span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">IN</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">CONNECTION</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">WITH</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">THE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">USE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OR</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">PERFORMANCE</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">OF</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">THIS</span><span 
+class="pcrr7t-x-x-80">&#x00A0;</span><span 
+class="pcrr7t-x-x-80">SOFTWARE</span><span 
+class="pcrr7t-x-x-80">.</span>
+   </div>
+<!--l. 90--><p class="indent" >   Readers simply looking for templated LRU cache code for instant usage
+may wish to turn straight to <a 
+href="#x1-8007r1">Listing&#x00A0;1</a> and the comments immediately
+preceding it.
+</p><!--l. 93--><p class="indent" >   The sources are also available from a Bitbucket-hosted <a 
+href="http://bitbucket.org/timday/lru_cache" >Mercurial
+repository</a>.
+</p><!--l. 95--><p class="noindent" >
+</p>
+   <h3 class="sectionHead"><span class="titlemark">3    </span> <a 
+ id="x1-40003"></a>The problem</h3>
+<!--l. 97--><p class="noindent" >The need for caching behaviour sometimes arises during system development.
+Generally the desire is to preserve some expensive-to-obtain results so they
+can be reused &#8220;for free&#8221; without repeating the expensive operation in future.
+Typically the expense arises because a complex calculation is needed to
+obtain the result, or because it must be obtained via a time consuming I/O
+operation. If the total number of such results dealt with over the
+lifetime of the system does not consume excessive memory, it may
+suffice to store them in a simple key-value container (for example, a
+<span 
+class="pcrr7t-x-x-109">std::map</span>), with the key being the input to the expensive function and the
+value being the result. This is often referred to as &#8220;memoisation&#8221; of a
+function.
+</p><!--l. 108--><p class="indent" >   However, for most applications, this approach would quickly consume too
+much memory to be of any practical value. The memory consumption issue
+can be addressed by limiting the maximum number of items stored in the
+cache or, if the items have a variable size, limiting the aggregate total stored.
+Initially the cache is empty and records (key-value pairs) can be stored
+in it freely. After some further usage, it will fill up. Once full, the
+question arises of what to do with subsequent additional records which it
+                                                                     
+
+                                                                     
+seems desirable to cache, but for which there is no space (given the
+limited capacity constraint) without taking action to remove some other
+records from the store. Assuming the records most recently added to the
+cache are those most likely to be accessed again (ie assuming some
+temporal coherence in the access sequence), a good general strategy is
+to make way for a new record by deleting the record in the cache
+which was &#8220;least recently used&#8221;. This is called an LRU replacement
+strategy.
+</p><!--l. 123--><p class="indent" >   Despite the general utility of a LRU-replacement cache component, one is
+not provided as such in C++&#8217;s Standard Library or in the well known Boost
+libraries. However, it is reasonably easy logic to construct using either library
+as a basis.
+</p><!--l. 127--><p class="noindent" >
+</p>
+   <h3 class="sectionHead"><span class="titlemark">4    </span> <a 
+ id="x1-50004"></a>Implementations</h3>
+<!--l. 129--><p class="noindent" >The following two sections describe possible implementations, both of them
+providing caching up to a limited number of records of a function with
+signature <span 
+class="pcrr7t-x-x-109">V f(K)</span>), where <span 
+class="pcrr7t-x-x-109">K </span>and <span 
+class="pcrr7t-x-x-109">V </span>are the &#8220;key type&#8221; and the &#8220;value type&#8221;.
+The only real difference in the API to either implementation is that the
+boost-based one passes the cached function as a <span 
+class="pcrr7t-x-x-109">boost::function </span>rather
+than a function pointer, providing slightly more flexibility through
+compatibility with <span 
+class="pcrr7t-x-x-109">boost::bind</span>.
+</p><!--l. 138--><p class="indent" >   The code presented has been tested on g++ 4.4.5. The <span 
+class="pcrr7t-x-x-109">-std=c++0x </span>option
+is required in order to use the <span 
+class="pcrr7t-x-x-109">std::unordered</span><span 
+class="pcrr7t-x-x-109">_map </span>hash-based map
+container which appeared with the TR1 additions to the C++ Standard
+Library, and variadic template arguments are also used to bypass some
+templated-template issues associated with the different type arguments to
+the tree-based and hash-based container types.
+</p><!--l. 144--><p class="indent" >   For brevity the code explanations below will generally refer to the
+<span 
+class="pcrr7t-x-x-109">std::map </span>and <span 
+class="pcrr7t-x-x-109">boost::bimaps::set</span><span 
+class="pcrr7t-x-x-109">_of </span>versions of the code; however both
+cache implementations work equally well (or better; see <a 
+href="#x1-140007.2">subsection&#x00A0;7.2</a>) with
+<span 
+class="pcrr7t-x-x-109">std::unordered</span><span 
+class="pcrr7t-x-x-109">_map </span>and <span 
+class="pcrr7t-x-x-109">boost::bimaps::unordered</span><span 
+class="pcrr7t-x-x-109">_set</span><span 
+class="pcrr7t-x-x-109">_of</span>
+containers and the code presented is fully intended to support both, subject
+to the key type supporting the necessary concepts (ordered comparison in the
+case of <span 
+class="pcrr7t-x-x-109">std::map </span>and <span 
+class="pcrr7t-x-x-109">boost::bimaps::set</span><span 
+class="pcrr7t-x-x-109">_of</span>, hashability and equality
+testing in the case of the unordered variants).
+</p><!--l. 151--><p class="noindent" >
+</p>
+                                                                     
+
+                                                                     
+   <h3 class="sectionHead"><span class="titlemark">5    </span> <a 
+ id="x1-60005"></a>Standard Library based LRU-cache</h3>
+<!--l. 154--><p class="noindent" >
+</p>
+   <h4 class="subsectionHead"><span class="titlemark">5.1    </span> <a 
+ id="x1-70005.1"></a>Design</h4>
+<!--l. 155--><p class="noindent" >Users of the C++ Standard Library needing an LRU-replacement cache
+generally gravitate towards <span 
+class="pcrr7t-x-x-109">std::map </span>or <span 
+class="pcrr7t-x-x-109">std::unordered</span><span 
+class="pcrr7t-x-x-109">_map</span>, because
+of their support for efficient keyed value accesses (<span 
+class="cmmi-10x-x-109">O</span><span 
+class="cmr-10x-x-109">(</span><span 
+class="cmr-10x-x-109">log</span> <span 
+class="cmmi-10x-x-109">n</span><span 
+class="cmr-10x-x-109">) </span>or <span 
+class="cmmi-10x-x-109">O</span><span 
+class="cmr-10x-x-109">(1)</span>
+access complexity). The problem then is how to implement the eviction
+strategy.
+</p><!--l. 159--><p class="indent" >   The most obvious naive solution is to use an </p><!--l. 160-->
+<div class="lstlisting" id="listing-2"><span class="label"><a 
+ id="x1-7001r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">timestamp_type</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span>
+   </div>
+<!--l. 164--><p class="indent" >   The <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_t </span>holds a scalar quantity, the ordering of which indicates
+when the value was last accessed relative to other values; typically some sort
+of incrementing serial number is used rather than an actual clock-derived
+time, to ensure a one-to-one mapping from timestamps to records. Keys
+then give efficient access to values and timestamps, and timestamps
+can be updated without the need to adjust the map&#8217;s tree-structure
+(as this depends entirely on the key values). However, to determine
+the minimum timestamp in order to evict a record, it is necessary to
+perform a <span 
+class="cmmi-10x-x-109">O</span><span 
+class="cmr-10x-x-109">(</span><span 
+class="cmmi-10x-x-109">n</span><span 
+class="cmr-10x-x-109">) </span>search over all the records to determine the oldest
+one.
+</p><!--l. 172--><p class="indent" >   As a solution to eviction being expensive, it might be tempting to
+implement the cache as a </p><!--l. 173-->
+<div class="lstlisting" id="listing-3"><span class="label"><a 
+ id="x1-7002r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">list</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span>
+   </div>
+<!--l. 176--><p class="indent" >   Moving any item accessed to the tail of the list (a cheap operation for
+lists), ensures the least-recently-used item can trivially be obtained (for
+erasure) at the list head by <span 
+class="pcrr7t-x-x-109">begin()</span>. However, this just moves the problem
+elsewhere as it is now necessary to resort to an <span 
+class="cmmi-10x-x-109">O</span><span 
+class="cmr-10x-x-109">(</span><span 
+class="cmmi-10x-x-109">n</span><span 
+class="cmr-10x-x-109">) </span>search simply to look up
+a key in the cache.
+</p><!--l. 181--><p class="indent" >   While either naive solution can be got to work (and may well be a
+simple pragmatic solution to caching a few tens of items) certainly
+neither can be considered scalable or efficient due to the <span 
+class="cmmi-10x-x-109">O</span><span 
+class="cmr-10x-x-109">(</span><span 
+class="cmmi-10x-x-109">n</span><span 
+class="cmr-10x-x-109">) </span>behaviour
+associated with either identifying eviction targets or accessing values by
+key.
+</p><!--l. 185--><p class="indent" >   However, it is possible to implement an LRU-replacement cache with
+efficient eviction <span 
+class="pncri7t-x-x-109">and </span>access using a pair of maps: </p><!--l. 187-->
+                                                                     
+
+                                                                     
+<div class="lstlisting" id="listing-4"><span class="label"><a 
+ id="x1-7003r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">timestamp_type</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">timestamp_to_key_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7004r2"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7005r3"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7006r4"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">timestamp_type</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7007r5"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_to_value_type</span><span 
+class="pcrr7t-">;</span>
+   </div>
+<!--l. 194--><p class="indent" >   On accessing <span 
+class="pcrr7t-x-x-109">key</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_value </span>by a key, we obtain access to both the value
+required and the timestamp, which can be updated in both the accessed
+record and, by lookup, <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_key</span>. When an eviction is required,
+the lowest timestamp in <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_key </span>provides the key to the record
+which must be erased.
+</p><!--l. 199--><p class="indent" >   However, this can actually be optimised slightly: </p><!--l. 200-->
+<div class="lstlisting" id="listing-5"><span class="label"><a 
+ id="x1-7008r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">timestamp_type</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">timestamp_to_key_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7009r2"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7010r3"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7011r4"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">timestamp_to_key_type</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">iterator</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-7012r5"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_to_value_type</span><span 
+class="pcrr7t-">;</span>
+   </div>
+<!--l. 207--><p class="indent" >   This has the slight advantage that updating the timestamp on a record
+access avoids an keyed lookup into <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_key</span>, replacing it with a
+(presumably more efficient) direct iterator access.
+</p><!--l. 210--><p class="indent" >   Pedants will observe that further slight improvement would also have
+the <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_key</span><span 
+class="pcrr7t-x-x-109">_type </span>map&#8217;s value be an iterator into the
+<span 
+class="pcrr7t-x-x-109">key</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_value</span><span 
+class="pcrr7t-x-x-109">_type </span>but this introduces a circular type definition. It might
+be tempting to try to break the dependency by using <span 
+class="pcrr7t-x-x-109">void&#x22C6; </span>in place of the
+iterator, but iterators cannot portably be cast to pointers. In any case, the
+first iterator optimisation mentioned benefits the updating of timestamps
+needed during cache hits whereas this second iterator optimisation benefits
+the eviction associated with cache misses. Since in a well functioning cached
+system cache hits should be far more common than misses, this second
+optimisation is likely of much less value than the first. Another consideration
+is that whatever expensive operation is required to generate a new result
+following a cache miss is likely to be hugely more expensive than any
+keyed access. Therefore this second optimisation is not considered
+further.
+</p><!--l. 222--><p class="indent" >   In fact there <span 
+class="pncri7t-x-x-109">is </span>one final powerful optimisation possible. The only
+operations actually done on <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_to</span><span 
+class="pcrr7t-x-x-109">_key </span>are to access its head
+(lowest timestamp, least recently used) element, or to move elements to the
+(most recently used) tail. Therefore it can be replaced by a <span 
+class="pcrr7t-x-x-109">std::list</span>; this
+also eliminates the need for any actual instances of <span 
+class="pcrr7t-x-x-109">timestamp</span><span 
+class="pcrr7t-x-x-109">_type </span>(and
+therefore any concerns about the timestamp possibly overflowing). In
+previous testing the author has found list-and-map implementations
+to be almost twice as fast as a version (not shown) using a pair of
+maps.
+</p><!--l. 231--><p class="indent" >   Finally, before showing the complete implementation, there is one
+other detail to consider: it would seem to be desirable to template the
+cache class code on the underlying container type used (<span 
+class="pcrr7t-x-x-109">std::map </span>or
+<span 
+class="pcrr7t-x-x-109">std::unordered</span><span 
+class="pcrr7t-x-x-109">_map</span>) rather than provide two completely separate
+implementations which actually only differ in minor details. This is slightly
+                                                                     
+
+                                                                     
+complicated by the different type argument signatures of the container types
+own templates (providing the optional capability to override default
+comparator or hasher/equality predicate logic as appropriate), but a simple
+workround is to declare the map type as templated on variadic type
+arguments <span 
+class="pcrr7t-x-x-109">template&#x003C;typename...&#x003E; class MAP </span>and then the actual
+container instance required can simply be instantiated on the necessary key
+and value types. Generalising the code to support overriding of the default
+comparator (or the unordered map type equivalent) or allocators is left as an
+exercise for the reader.
+</p><!--l. 243--><p class="noindent" >
+</p>
+   <h4 class="subsectionHead"><span class="titlemark">5.2    </span> <a 
+ id="x1-80005.2"></a>Implementation</h4>
+<!--l. 245--><p class="noindent" >See <a 
+href="#x1-8007r1">Listing&#x00A0;1</a> for a complete example using the pair of containers
+</p><!--l. 246-->
+<div class="lstlisting" id="listing-6"><span class="label"><a 
+ id="x1-8001r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">list</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_tracker_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8002r2"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">MAP</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8003r3"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_tracker_type</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">iterator</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8004r4"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_to_value_type</span><span 
+class="pcrr7t-">;</span>
+   </div>
+<!--l. 252--><p class="indent" >   where MAP is expected to be one of <span 
+class="pcrr7t-x-x-109">std::map </span>or <span 
+class="pcrr7t-x-x-109">std::unordered</span><span 
+class="pcrr7t-x-x-109">_map</span>;
+for example an LRU cache from <span 
+class="pcrr7t-x-x-109">std::string </span>to <span 
+class="pcrr7t-x-x-109">std::string </span>using
+hashing would be declared as </p><!--l. 254-->
+<div class="lstlisting" id="listing-7"><span class="label"><a 
+ id="x1-8005r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">lru_cache_using_std</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">string</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">string</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">unordered_map</span><span 
+class="pcrr7t-">&#x003E;</span>
+   </div>
+<!--l. 257--><p class="indent" >   while an int-keyed cache of Foo objects using the &#8220;classic&#8221; <span 
+class="pcrr7t-x-x-109">std::map</span>
+would be declared as </p><!--l. 258-->
+<div class="lstlisting" id="listing-8"><span class="label"><a 
+ id="x1-8006r1"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">lru_cache_using_std</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrb7t-">int</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">shared_ptr</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">Foo</span><span 
+class="pcrr7t-">&#x003E;,</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">map</span><span 
+class="pcrr7t-">&#x003E;</span>
+   </div>
+<!--l. 261--><p class="indent" >   Note that use of a reference counted smart-pointer for heap-allocated
+value types is strongly advised as the very nature of caches easily leads to
+situations where value object ownership must be considered shared
+between the cache and a client which has retrieved the value from the
+cache.
+</p>
+   <!--l. 265--><div class="lstinputlisting">
+<a 
+ id="x1-8007r1"></a>
+<a 
+ id="x1-8008"></a>
+<br />
+    <div class="caption" 
+><span class="id">Listing&#x00A0;1:
+    </span><span  
+class="content">lru_cache_using_std.h</span></div><!--tex4ht:label?: x1-8007r5 --><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8009r1"></a></span><span 
+class="pcrb7t-">#</span><span 
+class="pcrb7t-">ifndef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">_lru_cache_using_std_</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8010r2"></a></span><span 
+class="pcrb7t-">#</span><span 
+class="pcrb7t-">define</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">_lru_cache_using_std_</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8011r3"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8012r4"></a></span><span 
+class="pcrb7t-">#</span><span 
+class="pcrb7t-">include</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">cassert</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8013r5"></a></span><span 
+class="pcrb7t-">#</span><span 
+class="pcrb7t-">include</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">list</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8014r6"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8015r7"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Class</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">providing</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">fixed</span><span 
+class="pcrro7t-">-</span><span 
+class="pcrro7t-">size</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">(</span><span 
+class="pcrro7t-">by</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">number</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">records</span><span 
+class="pcrro7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8016r8"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">LRU</span><span 
+class="pcrro7t-">-</span><span 
+class="pcrro7t-">replacement</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">cache</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">a</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">function</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">with</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">signature</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8017r9"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">V</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">f</span><span 
+class="pcrro7t-">(</span><span 
+class="pcrro7t-">K</span><span 
+class="pcrro7t-">)</span><span 
+class="pcrro7t-">.</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8018r10"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">MAP</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">should</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">be</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">one</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">std</span><span 
+class="pcrro7t-">::</span><span 
+class="pcrro7t-">map</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">or</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">std</span><span 
+class="pcrro7t-">::</span><span 
+class="pcrro7t-">unordered_map</span><span 
+class="pcrro7t-">.</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8019r11"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Variadic</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">template</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">args</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">used</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">deal</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">with</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8020r12"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">different</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">type</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">argument</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">signatures</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">those</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8021r13"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">containers</span><span 
+class="pcrro7t-">;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">default</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">comparator</span><span 
+class="pcrro7t-">/</span><span 
+class="pcrro7t-">hash</span><span 
+class="pcrro7t-">/</span><span 
+class="pcrro7t-">allocator</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8022r14"></a></span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">will</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">be</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">used</span><span 
+class="pcrro7t-">.</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8023r15"></a></span><span 
+class="pcrb7t-">template</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8024r16"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8025r17"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8026r18"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">template</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">...&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">class</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">MAP</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8027r19"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">class</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">lru_cache_using_std</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8028r20"></a></span><span 
+class="pcrr7t-">{</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8029r21"></a></span><span 
+class="pcrb7t-">public</span><span 
+class="pcrr7t-">:</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8030r22"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8031r23"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">K</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8032r24"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">V</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">value_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8033r25"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8034r26"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Key</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">access</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">history</span><span 
+class="pcrro7t-">,</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">most</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">recent</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">at</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">back</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8035r27"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">list</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">key_type</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_tracker_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8036r28"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8037r29"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Key</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">value</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">and</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">key</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">history</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">iterator</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8038r30"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typedef</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">MAP</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8039r31"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_type</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8040r32"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">std</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">pair</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8041r33"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">value_type</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8042r34"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_tracker_type</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">iterator</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8043r35"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8044r36"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003E;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_to_value_type</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8045r37"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8046r38"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Constuctor</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">specifies</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">cached</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">function</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">and</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8047r39"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">maximum</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">number</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">records</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">be</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">stored</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8048r40"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">lru_cache_using_std</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8049r41"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">value_type</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">(&#x22C6;</span><span 
+class="pcrr7t-">f</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrb7t-">const</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_type</span><span 
+class="pcrr7t-">&amp;)</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8050r42"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">size_t</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">c</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8051r43"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8052r44"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">:</span><span 
+class="pcrr7t-">_fn</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">f</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8053r45"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">_capacity</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">c</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8054r46"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">{</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8055r47"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">assert</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">_capacity</span><span 
+class="pcrr7t-">!=0)</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8056r48"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">}</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8057r49"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8058r50"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Obtain</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">value</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">cached</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">function</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">for</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">k</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8059r51"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">value_type</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">operator</span><span 
+class="pcrr7t-">()</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrb7t-">const</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_type</span><span 
+class="pcrr7t-">&amp;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">k</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">{</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8060r52"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8061r53"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Attempt</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">find</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">existing</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">record</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8062r54"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">const</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">key_to_value_type</span><span 
+class="pcrr7t-">::</span><span 
+class="pcrr7t-">iterator</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">it</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8063r55"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">=</span><span 
+class="pcrr7t-">_key_to_value</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">find</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">k</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8064r56"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8065r57"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">if</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">it</span><span 
+class="pcrr7t-">==</span><span 
+class="pcrr7t-">_key_to_value</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">end</span><span 
+class="pcrr7t-">()</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">{</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8066r58"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8067r59"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">We</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">don</span><span 
+class="pcrro7t-">'</span><span 
+class="pcrro7t-">t</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">have</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">it</span><span 
+class="pcrro7t-">:</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8068r60"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8069r61"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Evaluate</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">function</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">and</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">create</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">new</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">record</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8070r62"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">const</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">value_type</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">v</span><span 
+class="pcrr7t-">=</span><span 
+class="pcrr7t-">_fn</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">k</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8071r63"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">insert</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">k</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">v</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8072r64"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8073r65"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Return</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">freshly</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">computed</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">value</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8074r66"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">return</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">v</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8075r67"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8076r68"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">}</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">else</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">{</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8077r69"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8078r70"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">We</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">do</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">have</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">it</span><span 
+class="pcrro7t-">:</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8079r71"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8080r72"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Update</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">access</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">record</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">by</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">moving</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8081r73"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">accessed</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">key</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">back</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">of</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">list</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8082r74"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">_key_tracker</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">splice</span><span 
+class="pcrr7t-">(</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8083r75"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">_key_tracker</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">end</span><span 
+class="pcrr7t-">()</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8084r76"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">_key_tracker</span><span 
+class="pcrr7t-">,</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8085r77"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">(&#x22C6;</span><span 
+class="pcrr7t-">it</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">second</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">second</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8086r78"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8087r79"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8088r80"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Return</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">retrieved</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">value</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8089r81"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">return</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">(&#x22C6;</span><span 
+class="pcrr7t-">it</span><span 
+class="pcrr7t-">)</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">second</span><span 
+class="pcrr7t-">.</span><span 
+class="pcrr7t-">first</span><span 
+class="pcrr7t-">;</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8090r82"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">}</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8091r83"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">}</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8092r84"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8093r85"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">Obtain</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">the</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">cached</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">keys</span><span 
+class="pcrro7t-">,</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">most</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">recently</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">used</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">element</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8094r86"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">at</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">head</span><span 
+class="pcrro7t-">,</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">least</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">recently</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">used</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">at</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">tail</span><span 
+class="pcrro7t-">.</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8095r87"></a></span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">//</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">This</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">method</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">is</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">provided</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">purely</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">to</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">support</span><span 
+class="pcrro7t-">&#x00A0;</span><span 
+class="pcrro7t-">testing</span><span 
+class="pcrro7t-">.</span><span 
+class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
+ id="x1-8096r88"></a></span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrb7t-">template</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">&#x003C;</span><span 
+class="pcrb7t-">typename</span><span 
+class="pcrr7t-">&#x00A0;</span><span 
+class="pcrr7t-">IT</span><span 
+class="pcrr7t-">&#x003E;</span><span