[boost] huge container types?

From: Michael D. Crawford (crawford_at_[hidden])
Date: 2001-11-20 02:07:41

While it was not C++, I once implemented a scrolling list GUI object on the Mac 
OS in ANSI C that had hundreds of thousands of items for tens of megabytes of 
list data.  This was in the days when 32 MB of RAM was a lot, and virtual memory 
was not always used on the Mac OS and didn't perform all that well.

The native Mac OS List Manager was limited to 32kb of data because it used 
signed 16 bit offsets into your data.  The usual way to get more data into the 
list was to scroll a list of pointers, which would then get you 8192 items, 
still not nearly enough for my case.

The application was text retrieval off a CDROM.  I forget what exactly went in 
the list, but the CD was called The Total Heart and in general had a lot of SGML 
text about heart medicine, anatomy and health.

What I did was write a lookalike replacement for the list manager that held at 
most a couple hundred items in memory.  Whenever you would scroll one way or 
another in the list, it would grab some records off the CD ahead of where you'd 
scrolled (or behind if you were scrolling backwards), and dump some off its list 
if the cache was more than I'd configured it to be.

If you made a large jump I just dropped the cache and fetched new records.  If 
one were to do it in a fancier way, you could keep discontinuous cache ranges so 
if you jump back and forth then you could have immediate access.

What you'd want to do is implement something like a Least Recently Used cache 
algorithm that worked like whichever of the existing STL containers fits your 
application most naturally.  Dereferencing an iterator will also move your cache 
entry to the front of the list.  Or alternatively you could  use a Least 
Frequently Used cache algorithm in which derefencing an iterator will increment 
an access count.

In any case, make a parameter to the constructor that gives the cache size.  Or 
for extra credit make sure you're exception-safe and just drop cache items when 
you run out of memory.

-- 
Michael D. Crawford
GoingWare Inc. - Expert Software Development and Consulting
http://www.goingware.com
crawford_at_[hidden]
   Tilting at Windmills for a Better Tomorrow.
     "I give you this one rule of conduct. Do what you will, but speak
      out always. Be shunned, be hated, be ridiculed, be scared,
      be in doubt, but don't be gagged."
      -- John J. Chapman, "Make a Bonfire of Your Reputations"
         http://www.goingware.com/reputation/