<br><br><div class="gmail_quote">On Tue, Aug 30, 2011 at 12:52, Jos Koot <span dir="ltr">&lt;<a href="mailto:jos.koot@telefonica.net">jos.koot@telefonica.net</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<u></u>



<div>
<div dir="ltr" align="left"><span><font face="Arial"><font size="2" color="#0000ff">You are stating: hash with bounded 
memory</font></font></span></div>
<div dir="ltr" align="left"><span><font face="Arial" size="2" color="#0000ff">Does that mean you will have a limit on the number of 
entries?</font></span></div></div></blockquote><div><br>Not necessarily. It might grow, although I might limit it to logarithmic growth.<br>Or the bound may be very large but unknown, and little memory should be used most of the time.<br>

 </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div>
<div dir="ltr" align="left"><span><font face="Arial" size="2" color="#0000ff">In that case a vector plus a current index might do, I 
think.</font></span></div>
<div dir="ltr" align="left"><span><font face="Arial" size="2" color="#0000ff">Gives you O(1) access to every element.</font></span></div>
<div dir="ltr" align="left"><span><font face="Arial" size="2" color="#0000ff">If the required number of elements may vary very much, a 
vector probably is not a good idea, unless using resizable vectors, but that 
makes some operations O(n).</font></span></div></div></blockquote><div><br>A hash+vector would nearly do it, but in the end it might not get any simpler than a doubly linked list.<br>I also need to move items at the end of the list too.<br>

<br>I should add that this is not for production purpose, but for more &quot;theoretical&quot; properties, so I don&#39;t care much about a potential constant overhead per operation, but I care about how it would behave with an increasing number of items.<br>

<br>Laurent<br></div></div>