Re: [boost] huge container types?

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-11-20 19:08:19

At 12:05 PM 11/20/2001, Carl Daniel wrote:

 >Funny you should ask...
 >
 >I have implemented a B+Tree class which (mostly) emulates the std::map
 >interface, and which supports huge content with easily constrained use
 >of memory.

I have used a B+Tree implementation very effectively for years.  It's 
cursor based rather than iterator based.

An STL-like version with iterators seemed like a natural for Boost, so I 
put together an initial implementation.  But I ran into several worrisome 
issues which sidetracked me.  The worst was the question of validity of 
pointers and references after iterator destruction.  See 
http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#198  This has 
finally been resolved, but until library suppliers change their reverse 
iterator implementations, use of a reverse iterator on a B-tree will be 
unreliable.

The POD requirement was also a problem; before the current Boost type 
traits I didn't know of any way to assert that the requirement was being 
met, and was scared of the fallout from that.

To sum up, I think a B+Tree would be wonderful, but am worried if it 
deviates from associative container requirements in too many subtle ways, 
particularly if any of its unique requirements could result in errors 
undetectable at compile time.

--Beman