[container][intrusive] Treap for Boost.Container?
Dear All, I have been playing with boost::intrusive::treap, and it seems like a useful thing. I think it would be helpful to create a boost::container::treap, i.e. a non-intrusive treap container, implemented using the intrusive version. That could make this useful data structure available to users who wouldn't otherwise need to learn how to use Boost.Intrusive. (While I'm here.... does anyone know about a list-like container that has lower memory overhead when the data type is small, i.e. ints or chars? I was considering something using chunks like a std::list< std::vector<T> >, but insertion would invalidate other iterators in the same chunk, which is unacceptable. Any ideas?) Regards, Phil.
On Tue, Mar 19, 2013 at 4:06 AM, Phil Endecott < spam_from_boost_dev@chezphil.org> wrote: ...
(While I'm here.... does anyone know about a list-like container that has lower memory overhead when the data type is small, i.e. ints or chars? I was considering something using chunks like a std::list< std::vector<T> >, but insertion would invalidate other iterators in the same chunk, which is unacceptable. Any ideas?)
I think you can replace std::vector<T> for boost::container::stable_vector<T> http://www.boost.org/doc/libs/1_53_0/doc/html/boost/container/stable_vector.... Its advantage over as a singly linked list, for example, is that is supports random access iterators. However, to solve the problem of iterator invalidation elements are not stored contiguously in memory chunks. Regards, Vadim Stadnik
On Mar 18, 2013, at 2:06 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
(While I'm here.... does anyone know about a list-like container that has lower memory overhead when the data type is small, i.e. ints or chars? I was considering something using chunks like a std::list< std::vector<T> >, but insertion would invalidate other iterators in the same chunk, which is unacceptable. Any ideas?)
Isn't that how a deque is typically implemented, i.e., as a list of chunks?
El 18/03/2013 19:06, Phil Endecott escribió:
Dear All,
I have been playing with boost::intrusive::treap, and it seems like a useful thing.
I think it would be helpful to create a boost::container::treap, i.e. a non-intrusive treap container, implemented using the intrusive version. That could make this useful data structure available to users who wouldn't otherwise need to learn how to use Boost.Intrusive.
It shouldn't be difficult to implement. Please fill a ticket so that I can remember this idea in the future. Best, Ion
participants (4)
-
Ian Emmons -
Ion Gaztañaga -
Phil Endecott -
Vadim Stadnik