Re: [boost] [shifted_ptr] STL support: 99%

From: Phil Bouchard (philippe_at_[hidden])
Date: 2008-08-11 06:07:10

"Gordon Woodhull" <gordon_at_[hidden]> wrote in message 
news:A671761D-B76D-4C0C-86A6-592023FCFABC_at_woodhull.com...

[...]

> I think that the principles of ownership and the lifetime management 
> system you are proposing could probably be applied to systems of 
> intrusive containers, more quickly than a change to the c++ standard 
> (perhaps via the metagraph library I'm working on ;).

Intrusive containers are very useful and shifted_ptr itself uses its own 
version of intrusive_list and intrusive_stack (which isn't present in 
Boost.Intrusive BTW).  But even if ownership support isn't impossible adding 
for intrusive containers, the latter was not made for this (can refer to 
objects on the stack) and so are generic smart pointers not made for 
differenciating objects living on the stack or data segments with heap 
blocks.

[...]

>> Here the vector will have to support index fragmentation if we start
>> inserting objects between consecutive ones:
>> (l.begin() ++ ++)->insert('h');
>>
> By "index fragmentation," do you mean std::vector should remap indices  to 
> accommodate any changes?  That sounds really neat, but does that  logic 
> really belong there and not in some other class with different 
> performance guarantees?

It cannot belong to std::vector only, but to the main supercontainer class 
linking all of them and supporting it if necessary.  But I haven't 
implemented anything as such yet but the index fragmentation I'm talking 
about consists of mapping indices to range of iterators so that an insertion 
in the middle of a vector by the list handler is transparent to the vector 
and random access to the nodes still is a constant time operation in the 
average case scenario.  For example I got:

node elements[] = (node *) {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' 
', 't', 'e', 's', 't'};

elist<node> l(element, element + sizeof(elements) / sizeof(* elements));
evector<node> v(element, element + sizeof(elements) / sizeof(* elements));

// Insert operation using the elist
(-- l.end())->insert('.');

// The evector::operator [] (size_t p) would map ranges as such:
if 15 -> return node '.'
if 0 - 16 -> return node 'T' to 't'

I think a huge container inside an application will always suffer from 
imperfections and this could be a decent alternative to the problem.  A map 
mixed with a list, a vector mixed with a set or all four together offers an 
infinite set of properties.

[...]

> But at the same time I am really eager to see your redesign - it is  such 
> a dramatically different approach, and STL could surely be  generalized 
> better.

Well we now have exclusive problems we want to fix.  We have:
- Smart pointer support for STL (pointer wrappers are useful for some 
allocators)
- Supercontainer with shared access to nodes

The latter here would be reused code from the STL all mixed together.  There 
is no C++ standard redesign here, simply a Gnu Libstdc++ code extension.

[...]

Thanks,
-Phil