|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r75015 - in branches/release/libs: functional functional/hash/doc unordered unordered/doc
From: dnljms_at_[hidden]
Date: 2011-10-17 16:23:28
Author: danieljames
Date: 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
New Revision: 75015
URL: http://svn.boost.org/trac/boost/changeset/75015
Log:
Merge unordered+hash documentation updates.
Added:
branches/release/libs/functional/hash/doc/rationale.qbk
- copied, changed from r74908, /trunk/libs/functional/hash/doc/rationale.qbk
Properties modified:
branches/release/libs/functional/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/libs/functional/hash/doc/hash.qbk | 5 +
branches/release/libs/functional/hash/doc/intro.qbk | 10 ++-
branches/release/libs/functional/hash/doc/portability.qbk | 12 ----
branches/release/libs/functional/hash/doc/rationale.qbk | 27 ++++-----
branches/release/libs/unordered/doc/changes.qbk | 15 ++++-
branches/release/libs/unordered/doc/compliance.qbk | 110 +++++++++++++++++++++++----------------
branches/release/libs/unordered/doc/ref.php | 19 +++++-
branches/release/libs/unordered/doc/ref.xml | 76 +++++++++++++++++++++++----
8 files changed, 178 insertions(+), 96 deletions(-)
Modified: branches/release/libs/functional/hash/doc/hash.qbk
==============================================================================
--- branches/release/libs/functional/hash/doc/hash.qbk (original)
+++ branches/release/libs/functional/hash/doc/hash.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -14,11 +14,16 @@
]
]
+[def __issues__
+ [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf
+ Library Extension Technical Report Issues List]]
+
[include:hash intro.qbk]
[include:hash tutorial.qbk]
[include:hash portability.qbk]
[include:hash disable.qbk]
[include:hash changes.qbk]
+[include:hash rationale.qbk]
[xinclude ref.xml]
[include:hash links.qbk]
[include:hash thanks.qbk]
Modified: branches/release/libs/functional/hash/doc/intro.qbk
==============================================================================
--- branches/release/libs/functional/hash/doc/intro.qbk (original)
+++ branches/release/libs/functional/hash/doc/intro.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -18,9 +18,6 @@
[def __multi-index-short__ [@boost:/libs/multi_index/doc/index.html
Boost.MultiIndex]]
[def __bimap__ [@boost:/libs/bimap/index.html Boost.Bimap]]
-[def __issues__
- [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf
- Library Extension Technical Report Issues List]]
[def __hash-function__ [@http://en.wikipedia.org/wiki/Hash_function hash function]]
[def __hash-table__ [@http://en.wikipedia.org/wiki/Hash_table hash table]]
@@ -44,5 +41,12 @@
* the standard containers.
* extending [classref boost::hash] for custom types.
+[note
+This hash function is designed to be used in containers based on
+the STL and is not suitable as a general purpose hash function.
+For more details see the [link hash.rationale rationale].
+]
+
+
[endsect]
Modified: branches/release/libs/functional/hash/doc/portability.qbk
==============================================================================
--- branches/release/libs/functional/hash/doc/portability.qbk (original)
+++ branches/release/libs/functional/hash/doc/portability.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -90,16 +90,4 @@
Full code for this example is at
[@boost:/libs/functional/hash/examples/portable.cpp /libs/functional/hash/examples/portable.cpp].
-[h2 Other Issues]
-
-On Visual C++ versions 6.5 and 7.0, `hash_value` isn't overloaded for built in
-arrays. __boost_hash__, [funcref boost::hash_combine] and [funcref boost::hash_range] all use a workaround to
-support built in arrays so this shouldn't be a problem in most cases.
-
-On Visual C++ versions 6.5 and 7.0, function pointers aren't currently supported.
-
-When using GCC on Solaris, `boost::hash_value(long double)` treats
-`long double`s as `double`s - so the hash function doesn't take into account the
-full range of values.
-
[endsect]
Copied: branches/release/libs/functional/hash/doc/rationale.qbk (from r74908, /trunk/libs/functional/hash/doc/rationale.qbk)
==============================================================================
--- /trunk/libs/functional/hash/doc/rationale.qbk (original)
+++ branches/release/libs/functional/hash/doc/rationale.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -14,8 +14,8 @@
and output values. They attempt to uniformally distribute the output
values for very similar inputs. This hash function makes no such
attempt. In fact, for integers, the result of the hash function is often
-just the input value. So similar but different input values will result
-in similar but different output values.
+just the input value. So similar but different input values will often
+result in similar but different output values.
This means that it is not appropriate as a general hash function. For
example, a hash table may discard bits from the hash function resulting
@@ -25,28 +25,23 @@
So why not implement a higher quality hash function? Well, the standard
makes no such guarantee, it just requires that the hashes of two
-different values are unlikely to collide. So containers or algorithms
+different values are unlikely to collide. Containers or algorithms
designed to work with the standard hash function will have to be
implemented to work well when the hash function's output is correlated
-to its input. Since they are paying that cost it would be wasteful to
-expand the effort to make a higher quality hash function.
+to its input. Since they are paying that cost a higher quality hash function
+would be wasteful.
-If you do need a higher quality hash function, there are several options
+For other use cases, if you do need a higher quality hash function,
+there are several options
available. One is to use a second hash on the output of this hash
function, such as [@http://www.concentric.net/~ttwang/tech/inthash.htm
-Thomas Wang's hash function]. But for many types this might not work as
+Thomas Wang's hash function]. This this may not work as
well as a hash algorithm tailored for the input.
For strings that are several fast, high quality hash functions
-available, such as:
-
-* [@http://burtleburtle.net/bob/hash/index.html Bob Jenkins' hash
- functions]
-* [@http://www.azillionmonkeys.com/qed/hash.html Paul Hsieh's hash
- functions]
-* [@http://code.google.com/p/cityhash/ Google's CityHash]
-* [@http://code.google.com/p/smhasher/ MurmurHash3]
-
+available (for example [@http://code.google.com/p/smhasher/ MurmurHash3]
+and [@http://code.google.com/p/cityhash/ Google's CityHash]),
+although they tend to be more machine specific.
These may also be appropriate for hashing a binary representation of
your data - providing that all equal values have an equal
representation, which is not always the case (e.g. for floating point
Modified: branches/release/libs/unordered/doc/changes.qbk
==============================================================================
--- branches/release/libs/unordered/doc/changes.qbk (original)
+++ branches/release/libs/unordered/doc/changes.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -134,16 +134,23 @@
* Fix a bug when inserting into an `unordered_map` or `unordered_set` using
iterators which returns `value_type` by copy.
-[h2 Boost 1.48.0]
+[h2 Boost 1.48.0 - Major update]
This is major change which has been converted to use Boost.Move's move
-emulation, and be more compliant with the C++11 standard. This has resulted
-in some breaking changes:
+emulation, and be more compliant with the C++11 standard. See the
+[link unordered.compliance compliance section] for details.
+
+The container now meets C++11's complexity requirements, but to do so
+uses a little more memory. This means that `quick_erase` and
+`erase_return_void` are no longer required, they'll be removed in a
+future version.
+
+C++11 support has resulted in some breaking changes:
* Equality comparison has been changed to the C++11 specification.
In a container with equivalent keys, elements in a group with equal
keys used to have to be in the same order to be considered equal,
- now they can be a permutation of each other. To keep the old
+ now they can be a permutation of each other. To use the old
behavior define the macro `BOOST_UNORDERED_DEPRECATED_EQUALITY`.
* The behaviour of swap is different when the two containers to be
Modified: branches/release/libs/unordered/doc/compliance.qbk
==============================================================================
--- branches/release/libs/unordered/doc/compliance.qbk (original)
+++ branches/release/libs/unordered/doc/compliance.qbk 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -4,56 +4,77 @@
[section:compliance C++11 Compliance]
+[section:move Move emulation]
+
+Support for move semantics is implemented using Boost.Move. If rvalue
+references are available it will use them, but if not it uses a close,
+but imperfect emulation. On such compilers you'll need to use Boost.Move
+to take advantage of using movable container elements, also note that:
+
+* Non-copyable objects can be stored in the containers, but without support
+ for rvalue references the container will not be movable.
+* Argument forwarding is not perfect.
+
+[endsect]
+
[section:allocator_compliance Use of allocators]
-C++11 introduced a new, mostly backwards compatible, allocator system.
-This uses a traits class, `allocator_traits` to handle the allocator
+C++11 introduced a new allocator system. It's backwards compatible due to
+the lax requirements for allocators in the old standard, but might need
+some changes for allocators which worked with the old versions of the
+unordered containers.
+It uses a traits class, `allocator_traits` to handle the allocator
adding extra functionality, and making some methods and types optional.
-At the time of writing there isn't a stable release of a standard library
-with `allocator_traits` (libc++ has `allocator_traits` but it hasn't been
-released yet) so a partial implementation is always used.
+During development a stable release of
+`allocator_traits` wasn't available so an internal partial implementation
+is always used in this version. Hopefully a future version will use the
+standard implementation where available.
+The member functions `construct`, `destroy` and `max_size` are now
+optional, if they're not available a fallback is used.
A full implementation of `allocator_traits` requires sophisticated
-member function detection which requires support for SFINAE expressions,
-or something close. This is available on GCC from version 4.4, Clang and
-Visual C++ 2008 (with a little hacking) or later.
-
-On these compilers, the `construct`, `destroy` and `max_size` member functions
-are optional, as per C++11. On other compilers they are still required.
+member function detection so that the fallback is used whenever the
+member function call is not well formed.
+This requires support for SFINAE expressions, which are available on
+GCC from version 4.4 and Clang. They aren't supported by
+Visual C++ 2008/2010, but with a bit of hacking it's possible to support
+certain use cases.
+
+On other compilers, there's just a test to see if the allocator has
+a member, but no check that it can be called. So rather than using a
+fallback there will just be a compile error.
`propagate_on_container_copy_assignment`,
-`propagate_on_container_move_assignment` and
-`propagate_on_container_swap` are supported on most compilers
-(/TODO/: which ones don't support them?).
-`select_on_container_copy_construction` is also supported, but on
-compilers without full member function detection it must have exactly
-the right function signature, and can't be declared in a base class
-in order for it to be detected.
+`propagate_on_container_move_assignment`,
+`propagate_on_container_swap` and
+`select_on_container_copy_construction` are also supported.
+Due to imperfect move emulation, some assignments might check
+`propagate_on_container_copy_assignment` on some compilers and
+`propagate_on_container_move_assignment` on others.
The use of the allocator's construct and destruct methods might be a bit
surprising.
-Nodes are constructed and destructed using the allocator, but the objects
-contained in the node are stored in aligned space within the node
-and constructed and destructed by calling the constructor and destructor
-directly. So `construct` and `destroy` are called for the node, but not for
-the object.
+Nodes are constructed and destructed using the allocator, but the elements
+are stored in aligned space within the node and constructed and destructed
+by calling the constructor and destructor directly.
+
+In C++11 the allocator's construct function has the signature:
+
+ template <class U, class... Args>
+ void construct(U* p, Args&&... args);
+
+which supports calling `construct` for the contained object, but
+most existing allocators don't support this. If member function detection
+was good enough then with old allocators it would fall back to calling
+the element's constructor directly but in general, detection isn't good
+enough to do this which is why Boost.Unordered just calls the constructor
+directly every time. In most cases this will work okay.
`pointer_traits` aren't used. Instead, pointer types are obtained from
-rebound allocators.
-
-[endsect]
-
-[section:move Move emulation]
-
-Move emulation is implemented using Boost.Move. If rvalue references are
-available it will use them, but if not it uses a close, but imperfect emulation
-and to get the advantage of using movable container elements, you'll need to
-use Boost.Move.
-
-* Non-copyable objects can be stored in the containers, but without support
- for rvalue references the container will not be movable.
-* The number of arguments used in `emplace` is limited to /TODO/.
-* Argument forwarding is not perfect.
+rebound allocators, this can cause problems if the allocator can't be
+used with incomplete types. If `const_pointer` is not defined in the
+allocator, `boost::pointer_to_other<pointer, const value_type>::type`
+is used to obtain a const pointer.
[endsect]
@@ -74,22 +95,19 @@
Older drafts of the standard also supported variadic constructors
for `std::pair`, where the first argument would be used for the
first part of the pair, and the remaining for the second part.
-For the same example:
-
- x.emplace("key", 1, 2);
-
-This is emulated in Boost.Unordered, but will be deprecated soon.
-While it is a lot more compact, it lead to ambiguities so it was
-removed.
[endsect]
-[section:swap Swapping]
+[section:misc Miscellaneous]
When swapping, `Pred` and `Hash` are not currently swapped by calling
`swap`, their copy constructors are used. As a consequence when swapping
an exception may be throw from their copy constructor.
+Variadic constructor arguments for `emplace` are only used when both
+rvalue references and variadic template parameters are available.
+Otherwise `emplace` can only take up to 10 constructors arguments.
+
[endsect]
[endsect]
Modified: branches/release/libs/unordered/doc/ref.php
==============================================================================
--- branches/release/libs/unordered/doc/ref.php (original)
+++ branches/release/libs/unordered/doc/ref.php 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -116,16 +116,28 @@
</typedef>
<typedef name="pointer">
<type>typename allocator_type::pointer</type>
+ <description>
+ <para>
+ <code>value_type*</code> if
+ <code>allocator_type::pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="const_pointer">
<type>typename allocator_type::const_pointer</type>
+ <description>
+ <para>
+ <code>boost::pointer_to_other<pointer, value_type>::type</code>
+ if <code>allocator_type::const_pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="reference">
- <type>typename allocator_type::reference</type>
+ <type>value_type&</type>
<purpose><simpara>lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="const_reference">
- <type>typename allocator_type::const_reference</type>
+ <type>value_type const&</type>
<purpose><simpara>const lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="size_type">
@@ -320,7 +332,8 @@
<notes>
<para>
On compilers without rvalue references, this is emulated using
- Boost.Move.
+ Boost.Move. Note that on some compilers the copy assignment
+ operator may be used in some circumstances.
</para>
</notes>
<requires>
Modified: branches/release/libs/unordered/doc/ref.xml
==============================================================================
--- branches/release/libs/unordered/doc/ref.xml (original)
+++ branches/release/libs/unordered/doc/ref.xml 2011-10-17 16:23:27 EDT (Mon, 17 Oct 2011)
@@ -61,16 +61,28 @@
</typedef>
<typedef name="pointer">
<type>typename allocator_type::pointer</type>
+ <description>
+ <para>
+ <code>value_type*</code> if
+ <code>allocator_type::pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="const_pointer">
<type>typename allocator_type::const_pointer</type>
+ <description>
+ <para>
+ <code>boost::pointer_to_other<pointer, value_type>::type</code>
+ if <code>allocator_type::const_pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="reference">
- <type>typename allocator_type::reference</type>
+ <type>value_type&</type>
<purpose><simpara>lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="const_reference">
- <type>typename allocator_type::const_reference</type>
+ <type>value_type const&</type>
<purpose><simpara>const lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="size_type">
@@ -265,7 +277,8 @@
<notes>
<para>
On compilers without rvalue references, this is emulated using
- Boost.Move.
+ Boost.Move. Note that on some compilers the copy assignment
+ operator may be used in some circumstances.
</para>
</notes>
<requires>
@@ -1001,16 +1014,28 @@
</typedef>
<typedef name="pointer">
<type>typename allocator_type::pointer</type>
+ <description>
+ <para>
+ <code>value_type*</code> if
+ <code>allocator_type::pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="const_pointer">
<type>typename allocator_type::const_pointer</type>
+ <description>
+ <para>
+ <code>boost::pointer_to_other<pointer, value_type>::type</code>
+ if <code>allocator_type::const_pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="reference">
- <type>typename allocator_type::reference</type>
+ <type>value_type&</type>
<purpose><simpara>lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="const_reference">
- <type>typename allocator_type::const_reference</type>
+ <type>value_type const&</type>
<purpose><simpara>const lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="size_type">
@@ -1205,7 +1230,8 @@
<notes>
<para>
On compilers without rvalue references, this is emulated using
- Boost.Move.
+ Boost.Move. Note that on some compilers the copy assignment
+ operator may be used in some circumstances.
</para>
</notes>
<requires>
@@ -1951,16 +1977,28 @@
</typedef>
<typedef name="pointer">
<type>typename allocator_type::pointer</type>
+ <description>
+ <para>
+ <code>value_type*</code> if
+ <code>allocator_type::pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="const_pointer">
<type>typename allocator_type::const_pointer</type>
+ <description>
+ <para>
+ <code>boost::pointer_to_other<pointer, value_type>::type</code>
+ if <code>allocator_type::const_pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="reference">
- <type>typename allocator_type::reference</type>
+ <type>value_type&</type>
<purpose><simpara>lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="const_reference">
- <type>typename allocator_type::const_reference</type>
+ <type>value_type const&</type>
<purpose><simpara>const lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="size_type">
@@ -2155,7 +2193,8 @@
<notes>
<para>
On compilers without rvalue references, this is emulated using
- Boost.Move.
+ Boost.Move. Note that on some compilers the copy assignment
+ operator may be used in some circumstances.
</para>
</notes>
<requires>
@@ -2936,16 +2975,28 @@
</typedef>
<typedef name="pointer">
<type>typename allocator_type::pointer</type>
+ <description>
+ <para>
+ <code>value_type*</code> if
+ <code>allocator_type::pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="const_pointer">
<type>typename allocator_type::const_pointer</type>
+ <description>
+ <para>
+ <code>boost::pointer_to_other<pointer, value_type>::type</code>
+ if <code>allocator_type::const_pointer</code> is not defined.
+ </para>
+ </description>
</typedef>
<typedef name="reference">
- <type>typename allocator_type::reference</type>
+ <type>value_type&</type>
<purpose><simpara>lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="const_reference">
- <type>typename allocator_type::const_reference</type>
+ <type>value_type const&</type>
<purpose><simpara>const lvalue of <type>value_type</type>.</simpara></purpose>
</typedef>
<typedef name="size_type">
@@ -3140,7 +3191,8 @@
<notes>
<para>
On compilers without rvalue references, this is emulated using
- Boost.Move.
+ Boost.Move. Note that on some compilers the copy assignment
+ operator may be used in some circumstances.
</para>
</notes>
<requires>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk