123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390 |
- ++++++++++++++++++++++++++++++++++
- |Boost| Pointer Container Library
- ++++++++++++++++++++++++++++++++++
- .. |Boost| image:: boost.png
- :Authors: Thorsten Ottosen
- :Contact: nesotto@cs.aau.dk or tottosen@dezide.com
- :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.*`_
- * `Upgrading from Boost v. 1.66.*`_
- * `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.
- ===================================
- Upgrading from Boost v. ``1.66.*``
- ===================================
- Starting with Boost v. ``1.67.0``, Boost.Pointer Container will use
- `Boost.Config <../../config/index.html>`_ to conditionally provide
- ``std::unique_ptr``-based interfaces in addition to, or instead of,
- interfaces using ``std::auto_ptr``. Details
- are on the `Compatible Smart Pointer <compatible_smart_ptr.html>`_
- page, which also explains the convention in this documentation of using
- .. parsed-literal::
- *compatible-smart-ptr*\ <T>
- to indicate such conditional interfaces.
- For C++98/03 users, this change has no observable effect.
- For C++11/14 users, there is no effect on existing code that used
- previous versions of Boost.Pointer Container, but now all function
- overloads taking an ``std::auto_ptr`` parameter are accompanied by an
- overload taking ``std::unique_ptr``. In the case of return types,
- ``std::auto_ptr`` is still always used. Note however that until C++17,
- it is possible to construct ``std::unique_ptr<T>`` implicitly from
- ``std::auto_ptr<T>``. Thus, users are free to modernize their code by
- replacing any explicit mention of ``std::auto_ptr`` with
- ``std::unique_ptr``. This change falls just short of a
- search-and-replace conversion, as it is possible that some code may
- have relied on ``std::auto_ptr`` being copyable. But such situations
- will result in compile-time errors which should be easy to fix.
- Although ``std::auto_ptr`` is formally removed as of ISO C++17,
- certain compiler or standard library vendors have chosen to leave it
- in for backwards compatibility. For compilers and standard libraries
- where this is *not* the case, C++17 compilation of code using
- Boost.Pointer Container is not possible with Boost v. ``1.66.*`` or
- earlier. This situation is fixed as of Boost v. ``1.67.0``.
- =====================
- 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ørn 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://www.open-std.org/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.
|