Topic: Library proposal: STL with custom pointer objects


Author: cppljevans@cox-internet.com (Larry Evans)
Date: Mon, 27 Jun 2005 18:31:56 GMT
Raw View
On 05/20/2005 05:01 PM, Larry Evans wrote:
> On 05/16/2005 01:09 PM, P.J. Plauger wrote:
> [snip]
>
>> No and yes. The C++ Standard encourages, but does not require, a
>> library implementation to accommodate allocators with funny
>> pointer types. (In other words, for the type T the pointer type
>> is not necessarily T*.) The Dinkumware implementation is the only
>> one I know of that actually does so -- each of our STL containers
[snip]
> I've needed a specialized smart pointer for use in stl containers
> to allow precise garbage collection.  A prototype created several
> years ago is at:
>
> http://boost-sandbox.sourceforge.net/vault/index.php?&direction=0&order=&directory=cppljevans/policy_ptr
>
>
> I'm currently working on a newer version of the precise gc which
> I hope to upload soon to:
>
> http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/boost/policy_ptr/

The newer version is currently at:

http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/boost/fields_visitor/container_intern/#dirlist

It's use in an stl-like container is shown in vector.hpp in the same
directory.  The specialization for allowing traversal of the elements
is in:

   prox_indirect_registrar_heirarchy.hpp

Actual use in precise garbage collection is demonstrated by:


http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/libs/policy_ptr/test/std_ptr_binary_node_test.cpp

when the Jamfile.v2 in that director is used (or when macro
USE_CONTAINER_INTERN is defined).

Adapting Dinkumware's stl library to use this type of pointer, i.e.
prox_indirect, wouldn't pose any problems, would it?
adapting

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: "Samee Zahur" <samee.zahur@gmail.com>
Date: Mon, 16 May 2005 11:19:36 CST
Raw View
I'd like to know everyone's opinion about adding (yet) another template
parameter to the STL container classes - one which will determine the
kind of pointer objects the classes will use for handling contained
objects. Something like this will change the vector class from
template< class T,class A=allocator<T> > class vector;
to this:

template< class T,class A=allocator<T>,class P=ordinary_ptr<T> > class
vector

  Why?

Whenever I go for writing an allocator class of my own,
I feel like I should have something to do about the memory pool getting
fragmented. A defrag attempt, however, will make all existing pointers
invalid, and there will be no way for me to change the value of each
and every pointer pointing to a certain place. That can be made
possible if I could somehow instruct STL to use my own pointer objects
to handle all the data they contain.

And not just that, things like copy-on-write would be much simpler to
code if it was implemented. With the different kinds of pointer objects
now emerging out of libraries like boost, this can largely increase the
choice of users of STL.

But the question is, would we *all* like something like this? Or is it
already there or something?

Samee

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: pjp@dinkumware.com ("P.J. Plauger")
Date: Mon, 16 May 2005 18:09:40 GMT
Raw View
"Samee Zahur" <samee.zahur@gmail.com> wrote in message
news:1115893047.429623.201420@g49g2000cwa.googlegroups.com...

> I'd like to know everyone's opinion about adding (yet) another template
> parameter to the STL container classes - one which will determine the
> kind of pointer objects the classes will use for handling contained
> objects. Something like this will change the vector class from
> template< class T,class A=allocator<T> > class vector;
> to this:
>
> template< class T,class A=allocator<T>,class P=ordinary_ptr<T> > class
> vector
>
>  Why?
>
> Whenever I go for writing an allocator class of my own,
> I feel like I should have something to do about the memory pool getting
> fragmented. A defrag attempt, however, will make all existing pointers
> invalid, and there will be no way for me to change the value of each
> and every pointer pointing to a certain place. That can be made
> possible if I could somehow instruct STL to use my own pointer objects
> to handle all the data they contain.
>
> And not just that, things like copy-on-write would be much simpler to
> code if it was implemented. With the different kinds of pointer objects
> now emerging out of libraries like boost, this can largely increase the
> choice of users of STL.
>
> But the question is, would we *all* like something like this? Or is it
> already there or something?

No and yes. The C++ Standard encourages, but does not require, a
library implementation to accommodate allocators with funny
pointer types. (In other words, for the type T the pointer type
is not necessarily T*.) The Dinkumware implementation is the only
one I know of that actually does so -- each of our STL containers
uses the supplied allocator template to allocate, construct, and
destroy pointers as needed.

So what you want is already there, kinda.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: cppljevans@cox-internet.com (Larry Evans)
Date: Tue, 17 May 2005 23:32:56 GMT
Raw View
On 05/16/2005 12:19 PM, Samee Zahur wrote:
> I'd like to know everyone's opinion about adding (yet) another template
> parameter to the STL container classes - one which will determine the
> kind of pointer objects the classes will use for handling contained
> objects. Something like this will change the vector class from
> template< class T,class A=allocator<T> > class vector;
> to this:
>
> template< class T,class A=allocator<T>,class P=ordinary_ptr<T> > class
> vector
>
>   Why?
>
> Whenever I go for writing an allocator class of my own,
> I feel like I should have something to do about the memory pool getting
> fragmented. A defrag attempt, however, will make all existing pointers
> invalid, and there will be no way for me to change the value of each
> and every pointer pointing to a certain place. That can be made
> possible if I could somehow instruct STL to use my own pointer objects
> to handle all the data they contain.

AFAICT, it would also enable refcounted pointers to be garbage collected
even when cycles are present.  The existing boost shared_ptr has a
proposed garbage collector for collecting cycles in the pointer graph:

http://cvs.sourceforge.net/viewcvs.py/boost/boost/libs/smart_ptr/src/sp_collector.cpp?rev=1.4&view=auto

however, IIUC, it cannot collect cycles when the smart pointers are in
something like an stl collection, e.g. vector<shared_ptr<T> >, because
the "root" pointer of the vector (i.e. that returned by begin() ) is not
registered as a pointer by the function:

   boost::sp_scalar_constructor_hook

WARNING:  The above reasoning is just a guess, but I remember
discussing this somewhere either here or on the boost new group.
Hopefully Peter Dimov will give a more definite answer.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: yecril@bluebottle.com ("Krzysztof elechowski")
Date: Tue, 17 May 2005 23:30:49 GMT
Raw View
Uzytkownik "Samee Zahur" <samee.zahur@gmail.com> napisal w wiadomosci
news:1115893047.429623.201420@g49g2000cwa.googlegroups.com...
> Whenever I go for writing an allocator class of my own,
> I feel like I should have something to do about the memory pool getting
> fragmented. A defrag attempt, however, will make all existing pointers

Heap fragmentation is only an issue when you cannot fit a large objects
between two small ones.  How can you get this effect with standard template
data structures?  I thought all your objects should be of equal size.
Chris



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: "Samee Zahur" <samee.zahur@gmail.com>
Date: Wed, 18 May 2005 21:13:09 CST
Raw View
Krzysztof    elechowski wrote:
> Heap fragmentation is only an issue when you cannot fit a large
objects
> between two small ones.  How can you get this effect with standard
template
> data structures?  I thought all your objects should be of equal size.

> Chris

Well, if everyone is using the same heap, different map<int> and
map<bigclass> can easily keep on allocating/deallocating elements to
create fragmentation ... and many many other classes totally unrelated
to STL!

P.J. Plauger wrote
> The Dinkumware implementation is the only
> one I know of that actually does so -- each of our STL containers
> uses the supplied allocator template to allocate, construct, and
> destroy pointers as needed.
>
> So what you want is already there, kinda.
So the only thing that's not there is the 'manditory' part ... so if I
write a code here, it might not be acceptable everywhere ... hmm ...
but I think I can live with that!

Thanks!

Sanee


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]





Author: cppljevans@cox-internet.com (Larry Evans)
Date: Fri, 20 May 2005 22:01:34 GMT
Raw View
On 05/16/2005 01:09 PM, P.J. Plauger wrote:
[snip]
> No and yes. The C++ Standard encourages, but does not require, a
> library implementation to accommodate allocators with funny
> pointer types. (In other words, for the type T the pointer type
> is not necessarily T*.) The Dinkumware implementation is the only
> one I know of that actually does so -- each of our STL containers
> uses the supplied allocator template to allocate, construct, and
> destroy pointers as needed.

I've needed a specialized smart pointer for use in stl containers
to allow precise garbage collection.  A prototype created several
years ago is at:

http://boost-sandbox.sourceforge.net/vault/index.php?&direction=0&order=&directory=cppljevans/policy_ptr

I'm currently working on a newer version of the precise gc which
I hope to upload soon to:

http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/boost/policy_ptr/

Does the Dinkumware implementation allow something that shown in
the vault file referenced above?  IOW, does it allow something like:

   allocator_type::root_pointer

where root_pointer is a pointer as described in the above file as:

             typedef
           prox_children::prox_indirect_typed<Value>
         root_pointer
          /**@variable root_pointer
           * @brief
           *  The proxy from which all elements of
           *  the container may be reached.
           */
           ;

For the existing stl containers, instead of:

           prox_children::prox_indirect_typed<Value>

this would simply be:

           Value*

-regards
Larry

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]