Re: huge container types?

From: dylan_at_[hidden]
Date: 2001-11-20 22:46:20

--- In boost_at_y..., dylan_at_m... wrote:
> --- In boost_at_y..., Carl Daniel <cpdaniel_at_p...> wrote:
> > Funny you should ask...
> > 
> <snip>
> 
> > On the subject of building a huge-vector with just a custom 
> allocator, doesn't the (proposed?) guarantee that &v[0]
> > yields a pointer to contiguous memory pretty much eliminate the 
> custom allocator solution?
> > 
> Yes I realise that.  As it is, that clause is not in the standard 
yet 
> anyway.  Maybe there's still time to suggest that the clause should 
> not rule out the possibility of allocators that do not provide this 
> guarantee (that is, it only exists when using std::allocator<>).
> I'm not even sure if it's possible to do using just a custom 
> allocator, but it would seem the ideal use for such a thing.
> 

Having set myself the challenge I figured I should give it a go.
It turns out that using a custom allocator _almost_ works quite 
nicely.  I say almost because the one problem with vector (and 
presumably deque) is that elements need to be relocated, and the 
method by which common implementations of vector do this leaves a 
little to be desired (ie allocating the new amount of memory 
required, constructing all the new objects using the copy 
constructor, deleting the old ones then freeing the old memory).
This behaviour really needs to be overridden to make using the type  
of storage scheme I had in mind viable.
In actual fact because it uses a file, you can safely keep allocating 
more and more storage without needing to 'relocate' anything - the 
filesystem handles this for you.
It seems a little odd that given how much everything is templated in 
the standard library, nothing in the vector definition that I can see 
makes it possible to override this behaviour.  I guess I could 
specialise all the functions in vector that _might_ possibly cause 
element relocation (reserve and insert would presumably normally be 
the only two, but is this guaranteed by the standard?), but given the 
fact that certain rather popular compilers don't support partial 
specialisation I don't see this being an option.

So the upshot of all that is my "paged_allocator" class (as I called 
it) is only much use if you ensure that the vector never needs to 
grow from its initial size.  I guess to get around it I would have to 
write a 'paged_vector' substitute, which has the added benefit of the 
avoiding the necessarily ugly syntax for using paged_allocator with a 
standard vector (due to the lack of template typedefs).

The other thing I would need to do is decide whether a more 
sophisticated paging scheme would be necessary - my current one 
simple swaps in fixed-sized block when any part of it is required 
(hence swapping out any previously accessed block - it is assumed to 
be dirty if a non-const pointer is requested).  Ideally of course the 
paging scheme should replaceable, which is not particularly difficult 
with my current design.

Dylan