Proposal: Extended Allocators (was Montonic Containers)
It is my belief (but I'm happy to shown wrong) that the idea of 'Monotonic Containers' to provide a new allocator for vector to support a small block of memory is fundamentally not going to work, due to 2 limitations of allocators: 1) There is no support for in-line expansion (effectively, realloc which doesn't move if it can't realloc) 2) There is no support for an allocator to say "No, you can't have X memory, but I could give you Y", so it's hard to "exactly fill" a limited memory buffer. I have been working around this by implementing new special containers, which know about the size of a fixed buffer and therefore can make use of the space. I now think I'm probably going about this the wrong way, a much better way would be to implement: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html , or a variant thereof. The big problem with doing this "within boost" is that it would pull in a basically complete implementation of std::allocator and the containers into boost. In an ideal world, such a small and in my opinion useful extension would have been added to C++0x, but it's far too late for that now. tl;dr : Seeing as we are having a "what would boost accept" couple of days, would adding an (extended) implementation of a substantial part of the standard library be acceptable, or would I be better off trying to get this picked up by one of the existing standard libraries to pick this up (my worry being they may not want, quite sensibly, want to accept code which is not standardised). Chris
Hi Christopher, My idea of a "monotonic allocator" is too strong to be halted by merely STL ;) The idea is sound, either we can make it work with STL or I have to write new containers. But as mentioned, I think we can still do it via allocators. Obviously my initial implementation is not sufficient. I didnt't think it would be; but the idea and semantics are sound, I think we just need to find a way to make it work on all targets. Regards, Christian On Wed, Jun 10, 2009 at 1:49 AM, Christopher Jefferson < chris@bubblescope.net> wrote:
It is my belief (but I'm happy to shown wrong) that the idea of 'Monotonic Containers' to provide a new allocator for vector to support a small block of memory is fundamentally not going to work, due to 2 limitations of allocators:
1) There is no support for in-line expansion (effectively, realloc which doesn't move if it can't realloc) 2) There is no support for an allocator to say "No, you can't have X memory, but I could give you Y", so it's hard to "exactly fill" a limited memory buffer.
I have been working around this by implementing new special containers, which know about the size of a fixed buffer and therefore can make use of the space. I now think I'm probably going about this the wrong way, a much better way would be to implement: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html , or a variant thereof.
The big problem with doing this "within boost" is that it would pull in a basically complete implementation of std::allocator and the containers into boost.
In an ideal world, such a small and in my opinion useful extension would have been added to C++0x, but it's far too late for that now.
tl;dr : Seeing as we are having a "what would boost accept" couple of days, would adding an (extended) implementation of a substantial part of the standard library be acceptable, or would I be better off trying to get this picked up by one of the existing standard libraries to pick this up (my worry being they may not want, quite sensibly, want to accept code which is not standardised).
Chris _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
2009/6/9 Christopher Jefferson <chris@bubblescope.net>:
I have been working around this by implementing new special containers, which know about the size of a fixed buffer and therefore can make use of the space. I now think I'm probably going about this the wrong way, a much better way would be to implement: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html , or a variant thereof.
The big problem with doing this "within boost" is that it would pull in a basically complete implementation of std::allocator and the containers into boost.
Are you sure that you're not just trying to make something like an intrusive::vector? The analogy is obviously imperfect, as the existing intrusive containers are all node-based, but the advantages you mention fit very will with those described here: http://www.boost.org/doc/html/intrusive/intrusive_vs_nontrusive.html Intrusive, is, in a way, the "complete implementation" of containers that you mention, and fits very nicely with the idea of a less convenient interface for particularly space-/performance-sensitive users.
participants (3)
-
Christian Schladetsch -
Christopher Jefferson -
Scott McMurray