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...
> > On the subject of building a huge-vector with just a custom
> allocator, doesn't the (proposed?) guarantee that &v
> > 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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk