Tim Day avatar Tim Day committed 04389f1

Remove surplus .htm version.

Comments (0)

Files changed (1)

article/lru.htm

-<?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 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrb7t-">void</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">get_keys</span><span 
-class="pcrr7t-">(</span><span 
-class="pcrr7t-">IT</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">dst</span><span 
-class="pcrr7t-">)</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrb7t-">const</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">{</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8097r89"></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-">typename</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">key_tracker_type</span><span 
-class="pcrr7t-">::</span><span 
-class="pcrr7t-">const_reverse_iterator</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">src</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8098r90"></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-">=</span><span 
-class="pcrr7t-">_key_tracker</span><span 
-class="pcrr7t-">.</span><span 
-class="pcrr7t-">rbegin</span><span 
-class="pcrr7t-">()</span><span 
-class="pcrr7t-">;</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8099r91"></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-">while</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">(</span><span 
-class="pcrr7t-">src</span><span 
-class="pcrr7t-">!=</span><span 
-class="pcrr7t-">_key_tracker</span><span 
-class="pcrr7t-">.</span><span 
-class="pcrr7t-">rend</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-8100r92"></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-">&#x22C6;</span><span 
-class="pcrr7t-">dst</span><span 
-class="pcrr7t-">++</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">=</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">&#x22C6;</span><span 
-class="pcrr7t-">src</span><span 
-class="pcrr7t-">++;</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8101r93"></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-8102r94"></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-8103r95"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8104r96"></a></span><span 
-class="pcrb7t-">private</span><span 
-class="pcrr7t-">:</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8105r97"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8106r98"></a></span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">//</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">Record</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">a</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">fresh</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">key</span><span 
-class="pcrro7t-">-</span><span 
-class="pcrro7t-">value</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">pair</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">in</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">the</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">cache</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8107r99"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrb7t-">void</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">insert</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="pcrb7t-">const</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">value_type</span><span 
-class="pcrr7t-">&amp;</span><span 
-class="pcrr7t-">&#x00A0;</span><span 
-class="pcrr7t-">v</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-8108r100"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8109r101"></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-">Method</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">is</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">only</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">called</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">on</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">cache</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">misses</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8110r102"></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-">_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-">_key_to_value</span><span 
-class="pcrr7t-">.</span><span 
-class="pcrr7t-">end</span><span 
-class="pcrr7t-">()</span><span 
-class="pcrr7t-">)</span><span 
-class="pcrr7t-">;</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8111r103"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8112r104"></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-">Make</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">space</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">if</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">necessary</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8113r105"></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-">_key_to_value</span><span 
-class="pcrr7t-">.</span><span 
-class="pcrr7t-">size</span><span 
-class="pcrr7t-">()</span><span 
-class="pcrr7t-">==</span><span 
-class="pcrr7t-">_capacity</span><span 
-class="pcrr7t-">)</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8114r106"></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-">evict</span><span 
-class="pcrr7t-">()</span><span 
-class="pcrr7t-">;</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8115r107"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8116r108"></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-">Record</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">k</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">as</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">most</span><span 
-class="pcrro7t-">-</span><span 
-class="pcrro7t-">recently</span><span 
-class="pcrro7t-">-</span><span 
-class="pcrro7t-">used</span><span 
-class="pcrro7t-">&#x00A0;</span><span 
-class="pcrro7t-">key</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8117r109"></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-">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><span 
-class="pcrr7t-">it</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8118r110"></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_tracker</span><span 
-class="pcrr7t-">.</span><span 
-class="pcrr7t-">insert</span><span 
-class="pcrr7t-">(</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-">k</span><span 
-class="pcrr7t-">)</span><span 
-class="pcrr7t-">;</span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a 
- id="x1-8119r111"></a></span><span 
-class="pcrr7t-">&#x00A0;</span><br /><span class="label"><a