[boost] [Post review] Pointer Container

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2005-03-20 17:04:16

Dear all,

The Pointer Container library is very almost finished.

Since the review, the following major changes has been made

- improved docs with new tutorial and improved browsing
- new indirect functions
- new Cloneable and Clone Allocator concepts
- support for null values
- refactored template interface off all classes
- implementation guarantees to only instantiate std::container<void*>
- rewritten iterators
- improved tests

The new docs, and code can be downloaded from the files section:

http://groups.yahoo.com/group/boost/files/pointer%20container/ptr_container.zip

The test runs with vc7.1 and gcc.3.3.3.

Comments, suggestions and portability fixes are welcome.

There are one major issue and one minor I need to have resolved during the 
post-review.

Minor issue: allocation in map:operator[]
----------------------------------------
should a default allocated object use operator new
or heap_clone_allocator::allocate_default(); ?

This happens in

ptr_map<string,int> m;
m["foo"] = 5; // will allocate an int with new

Normally the use can control all allocations because he always
add objects manually or via cloninin (which he also controls).
But the default object is just allocated with operator new inside
ptr_map::operator[]. Should some hook be provided in
a new allocator concept, map_heap_allocator?

Major issue: ptr_iterator  implementation.
-----------------------------------------

So what is the problem? Well, since void*
is used internally, the iterators must cast to the
proper type in operator*; that is no problem
for the default indireted iterators; the problem
is with the iterators from

ptr_iterator ptr_begin();
ptr_iterator ptr_end();

One way to define would be to say

typedef internal_container::iterator ptr_iterator;

Then the reference type would be void*& and not
T*& as we would like. So if the user wanted to
sort the container, he would do

std::sort( cont.begin(), cont.end(),
              void_ptr_indirect_fun< std::less<T>, T>() );

This give us a rather insecure interface where you have to cast manually
to T* inside the functor. So I wish we could get a T*& reference type.

I think, from discussion with David Abrahams, that the current implementation
is non-portable even though my test works:

            typedef T*&      reference;
            reference dereference() const
            {
                // void_type is void* or const void*
                // I'm not sure why this is needed, but it seems to be
                return reinterpret_cast<reference>( const_cast<void_type&>( 
*iter_ ) );
            }

Does anybody knows how to rewrite this crappy code propoerly?

I think we're faced with three options

1. keep the current behavior and describe in the docs that it is non-portable

2. go back to making ptr_iterator the default iterator with void*& reference 
type;

3. add a small subset of algorithms to the classes themselves; I'm thinking 
that the subset
    from std::list is appropriate:
    - sort
    - remove_if
    - remove
    - unique
    - reverse
    - merge

Let me hear what you think

best regards

-- 
Thorsten Ottosen
----------------------------
www.dezide.com
www.cs.aau.dk/index2.php?content=Research/bss
www.boost.org
www.open-std.org/JTC1/SC22/WG21/