<br><br><div class="gmail_quote">On Tue, Aug 30, 2011 at 12:52, Jos Koot <span dir="ltr"><<a href="mailto:jos.koot@telefonica.net">jos.koot@telefonica.net</a>></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 "theoretical" properties, so I don'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>