ptr_container.rst

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

++++++++++++++++++++++++++++++++++
 |Boost| Pointer Container Library
++++++++++++++++++++++++++++++++++

.. |Boost| image:: boost.png



:Authors:       Thorsten Ottosen
:Contact:       [e-mail] or [e-mail]
:Organizations: `Department of Computer Science`_, Aalborg University, and `Dezide Aps`_
:date:          27th of October 2007
:Copyright:     Thorsten Ottosen 2004-2007. Use, modification and distribution is subject to the Boost Software License, Version 1.0 (see LICENSE_1_0.txt__).

__ http://www.boost.org/LICENSE_1_0.txt

.. _`Department of Computer Science`: http://www.cs.aau.dk
.. _`Dezide Aps`: http://www.dezide.com

========
Overview
========

Boost.Pointer Container provides containers for holding heap-allocated
objects in an exception-safe manner and with minimal overhead.
The aim of the library is in particular to make OO programming
easier in C++ by establishing a standard set of classes, methods
and designs for dealing with OO specific problems

* Motivation_
* Tutorial_
* Reference_
* `Usage guidelines`_
* Examples_
* `Library headers`_
* FAQ_
* `Upgrading from Boost v. 1.33.*`_
* `Upgrading from Boost v. 1.34.*`_
* `Upgrading from Boost v. 1.35.*`_
* `Future Developments`_
* Acknowledgements_
* References_

..
          - `Conventions <conventions.html>`_
          - `The Clonable Concept <reference.html#the-clonable-concept>`_
          - `The Clone Allocator Concept <reference.html#the-clone-allocator-concept>`_
          - `Pointer container adapters <reference.html#pointer-container-adapters>`_
          - `Sequence container classes <reference.html#sequence-containers>`_
        
            - `ptr_vector <ptr_vector.html>`_
            - `ptr_deque <ptr_deque.html>`_
            - `ptr_list <ptr_list.html>`_
            - `ptr_array <ptr_array.html>`_
          - `Associative container classes  <reference.html#associative-containers>`_
        
            - `ptr_set <ptr_set.html>`_
            - `ptr_multiset <ptr_multiset.html>`_
            - `ptr_map <ptr_map.html>`_
            - `ptr_multimap <ptr_multimap.html>`_
          - `Indirected functions <indirect_fun.html>`_
          - `Class nullable <reference.html#class-nullable>`_
          - `Exception classes <reference.html#exception-classes>`_
          


.. _Tutorial: tutorial.html


.. _Reference: reference.html

.. _`Usage guidelines`: guidelines.html

.. _Examples: examples.html

.. _`Library headers`: headers.html

.. _FAQ: faq.html


==========
Motivation
==========

Whenever a programmer wants to have a container of pointers to
heap-allocated objects, there is usually only one exception-safe way:
to make a container of smart pointers like `boost::shared_ptr <../../smart_ptr/shared_ptr.htm>`_
This approach is suboptimal if

1. the stored objects are not shared, but owned exclusively, or

..

2. the overhead implied by smart pointers is inappropriate

This library therefore provides standard-like containers that are for storing
heap-allocated or `cloned <reference.html#the-clonable-concept>`_ objects (or in case of a map, the mapped object must be
a heap-allocated or cloned object). For each of the standard
containers there is a pointer container equivalent that takes ownership of
the objects in an exception safe manner.  In this respect the library is intended
to solve the so-called
`polymorphic class problem <faq.html#what-is-the-polymorphic-class-problem>`_.


The advantages of pointer containers are

1. Exception-safe pointer storage and manipulation.

..

2. Notational convenience compared to the use of containers of pointers.

..

3. Can be used for types that are neither Assignable nor Copy Constructible.

..

4. No memory-overhead as containers of smart pointers can have (see [11]_ and [12]_).

..

5. Usually faster than using containers of smart pointers (see [11]_ and [12]_).

..

6. The interface is slightly changed towards the domain of pointers
   instead of relying on the normal value-based interface. For example,
   now it is possible for ``pop_back()`` to return the removed element.
   
.. 
 
7. Propagates constness such that one cannot modify the objects via a ``const_iterator``.

..

8. Built-in support for deep-copy semantics via the `the Clonable concept`__

.. __: reference.html#the-clonable-concept

The disadvantages are

1. Less flexible than containers of smart pointers like `boost::shared_ptr <../../smart_ptr/shared_ptr.htm>`_

When you do need shared semantics, this library is not what you need.

====================================
 Upgrading from Boost v. ``1.33.*``
====================================

If you upgrade from one of these versions of Boost, then there has been one
major interface change: map iterators now mimic iterators from ``std::map``.
Previously you may have written ::

  for( boost::ptr_map<std::string,T>::iterator i = m.begin(), e = m.end();
       i != e; ++i )
  {
    std::cout << "key:" << i.key();
    std::cout << "value:" << *i;
    i->foo(); // call T::foo()
  }
  
and this now needs to be converted into ::
       
  for( boost::ptr_map<std::string,T>::iterator i = m.begin(), e = m.end();
       i != e; ++i )
  {
    std::cout << "key:" << i->first;
    std::cout << "value:" << *i->second;
    i->second->foo(); // call T::foo()
  }

Apart from the above change, the library now also introduces

- ``std::auto_ptr<T>`` overloads::

        std::auto_ptr<T> p( new T );
        container.push_back( p );

- Derived-to-Base conversion in ``transfer()``::

        boost::ptr_vector<Base>  vec;
        boost::ptr_list<Derived> list;
        ...
        vec.transfer( vec.begin(), list ); // now ok

Also note that `Boost.Assign <../../assign/index.html>`_ introduces better support
for pointer containers. 

====================================
 Upgrading from Boost v. ``1.34.*``
====================================

Serialization has now been made optional thanks to Sebastian Ramacher.
You simply include ``<boost/ptr_container/serialize.hpp>`` or perhaps
just one of the more specialized headers.

All containers are now copy-constructible and assignable. So you can e.g. now
do:: 

    boost::ptr_vector<Derived> derived = ...;
    boost::ptr_vector<Base>    base( derived );
    base = derived;
    
As the example shows, derived-to-base class conversions are also allowed.
 
A few general functions have been added::

    VoidPtrContainer&       base();
    const VoidPtrContainer& base() const;

These allow direct access to the wrapped container which is
sometimes needed when you want to provide extra functionality.
    
A few new functions have been added to sequences::

    void resize( size_type size );
    void resize( size_type size, T* to_clone );

``ptr_vector<T>`` has a few new helper functions to integrate better with C-arrays::

    void transfer( iterator before, T** from, size_type size, bool delete_from = true );
    T**  c_array();

Finally, you can now also "copy" and "assign" an ``auto_type`` ptr by calling ``move()``::

    boost::ptr_vector<T>::auto_type move_ptr = ...;
    return boost::ptr_container::move( move_ptr );

====================================
 Upgrading from Boost v. ``1.35.*``
====================================

The library has been fairly stable, but a few new containers have been supported:

-  ``boost::ptr_unordered_set<T>`` in ``<boost/ptr_container/ptr_unordered_set.hpp>``

-  ``boost::ptr_unordered_map<Key,T>`` in ``<boost/ptr_container/ptr_unordered_map.hpp>``

-  ``boost::ptr_circular_buffer<T>`` in ``<boost/ptr_container/ptr_circular_buffer.hpp>``

There are no docs for these classes yet, but they are almost identical to
``boost::ptr_set<T>``, ``boost::ptr_map<Key,T>`` and ``boost::ptr_array<T,N>``, respectively.
The underlying containers stem from the two boost libraries

- `Boost.Unordered <../../unordered/index.html>`_ 

- `Boost.Circular Buffer <../../circular_buffer/index.html>`_

Furthermore, `insert iterators <ptr_inserter.html>`_ have been added. 

=====================
 Future Developments
=====================

There are indications that the ``void*`` implementation has a slight
performance overhead compared to a ``T*`` based implementation. Furthermore, a 
``T*`` based implementation is so much easier to use type-safely 
with algorithms. Therefore I anticipate to move to a ``T*`` based implementation.

Furthermore, the clone allocator might be allowed to have state. 
This design requires some thought, so if you have good ideas and use-cases'
for this, please don't hesitate to contact me.

Also, support for Boost.Interprocess is on the todo list.

There has been a few request for ``boost::ptr_multi_index_container<T,...>``. 
I investigated how difficult it would be, and it did turn out to be difficult, albeit
not impossible. But I don't have the resources to implement this beast 
for years to come, so if someone really needs this container, I suggest that they
talk with me in private about how it can be done.

================
Acknowledgements
================

The following people have been very helpful:

- Bj鴕n D. Rasmussen for unintentionally motivating me to start this library
- Pavel Vozenilek for asking me to make the adapters
- David Abrahams for the ``indirect_fun`` design
- Pavol Droba for being review manager
- Ross Boylan for trying out a prototype for real
- Felipe Magno de Almeida for giving fedback based on using the
  library in production code even before the library was part of boost
- Jonathan Turkanis for supplying his ``move_ptr`` framework
  which is used internally
- Stefan Slapeta and Howard Hinnant for Metrowerks support
- Russell Hind for help with Borland compatibility
- Jonathan Wakely for his great help with GCC compatibility and bug fixes
- Pavel Chikulaev for comments and bug-fixes
- Andreas Hommel for fixing the nasty Metrowerks bug
- Charles Brockman for his many comments on the documentation
- Sebastian Ramacher for implementing the optional serialization support

==========
References
==========

.. [1] Matt Austern: `"The Standard Librarian: Containers of Pointers"`__ , C/C++ Users Journal Experts Forum.

__ http://www.cuj.com/documents/s=7990/cujcexp1910austern/

.. [2] Bjarne Stroustrup, "The C++ Programming Language", `Appendix E: "Standard-Library Exception Safety"`__

__ http://www.research.att.com/~bs/3rd_safe.pdf

.. [3] Herb Sutter, "Exceptional C++".
.. [4] Herb Sutter, "More Exceptional C++".
.. [5] Kevlin Henney: `"From Mechanism to Method: The Safe Stacking of Cats"`__ , C++ Experts Forum, February 2002.

__ http://www.cuj.com/documents/s=7986/cujcexp2002henney/henney.htm

.. [6] Some of the few earlier attempts of pointer containers I have seen are the rather interesting NTL_ and the 
       pointainer_. 
       As of this writing both libraries are not exceptions-safe and can leak.

.. [7] INTERNATIONAL STANDARD, Programming languages --- C++, ISO/IEC 14882, 1998. See section 23 in particular.
.. [8] C++ Standard Library Closed Issues List (Revision 27), 
       Item 218, `Algorithms do not use binary predicate objects for default comparisons`__.

__ http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#218       
 
.. [9] C++ Standard Library Active Issues List (Revision 27), 
       Item 226, `User supplied specializations or overloads of namespace std function templates`__. 

__ http://gcc.gnu.org/onlinedocs/libstdc++/ext/lwg-active.html#226

.. [10] Harald Nowak, "A remove_if for vector", C/C++ Users Journal, July 2001.
.. [11] Boost smart pointer timings__

__ http://www.boost.org/libs/smart_ptr/smarttests.htm
 
.. [12] NTL_: Array vs std::vector and boost::shared_ptr 
.. [13] Kevlin Henney, `Null Object`__, 2002.

__ http://www.two-sdg.demon.co.uk/curbralan/papers/europlop/NullObject.pdf

.. _NTL: http://www.ntllib.org/asp.html
.. _pointainer: http://ootips.org/yonat/4dev/pointainer.h 


.. raw:: html 

        <hr>

:Copyright: Thorsten Ottosen 2004-2006.