On 7 February 2013 21:01, François Dumont wrote:
Thanks for taking care of it. Here is another version, I think clearer.
Reading the doc I also found an unfinished sentence in an other chapter, it
is in the patch.
I made quite a few changes, partly to address the is_copy_assignable
check I added for PR 56267, the change I committed is attached.
Please let me know if you think it's wrong or unclear.
2013-02-10 François Dumont fdum...@gcc.gnu.org
Jonathan Wakely jwakely@gmail.com
* doc/xml/manual/containers.xml: Add section on unordered containers.
* doc/xml/manual/using.xml: Fix incomplete sentence.
Tested with doc-xml-validate-docbook and doc-html-docbook, committed to trunk.
commit b6bc6d55e08e5e49065e34d6adbdec897cfffa0f
Author: Jonathan Wakely jwakely@gmail.com
Date: Sun Feb 10 22:27:40 2013 +
2013-02-10 François Dumont fdum...@gcc.gnu.org
Jonathan Wakely jwakely@gmail.com
* doc/xml/manual/containers.xml: Add section on unordered containers.
* doc/xml/manual/using.xml: Fix incomplete sentence.
diff --git a/libstdc++-v3/doc/xml/manual/containers.xml
b/libstdc++-v3/doc/xml/manual/containers.xml
index c90ffc6..920b491 100644
--- a/libstdc++-v3/doc/xml/manual/containers.xml
+++ b/libstdc++-v3/doc/xml/manual/containers.xml
@@ -349,7 +349,87 @@
/section
-!-- Sect1 03 : Interacting with C --
+!-- Sect1 03 : Unordered Associative --
+section xml:id=std.containers.unordered xreflabel=Unordered
+ infotitleUnordered Associative/title/info
+ ?dbhtml filename=unordered_associative.html?
+
+ section xml:id=containers.unordered.hash xreflabel=Hash
+infotitleHash Code/title/info
+
+ section xml:id=containers.unordered.cache xreflabel=Cache
+infotitleHash Code Caching Policy/title/info
+
+para
+ The unordered containers in libstdc++ may cache the hash code for each
+ element alongside the element itself. In some cases not recalculating
+ the hash code every time it's needed can improve performance, but the
+ additional memory overhead can also reduce performance, so whether an
+ unordered associative container caches the hash code or not depends on
+ a number of factors. The caching policy for GCC 4.8 is described below.
+/para
+para
+ The C++ standard requires that codeerase/code and codeswap/code
+ operations must not throw exceptions. Those operations might need an
+ element's hash code, but cannot use the hash function if it could
+ throw.
+ This means the hash codes will be cached unless the hash function
+ has a non-throwing exception specification such as codenoexcept/code
+ or codethrow()/code.
+/para
+para
+ Secondly, libstdc++ also needs the hash code in the implementation of
+ codelocal_iterator/code and codeconst_local_iterator/code in
+ order to know when the iterator has reached the end of the bucket.
+ This means that the local iterator types will embed a copy of the hash
+ function when possible.
+ Because the local iterator types must be DefaultConstructible and
+ CopyAssignable, if the hash function type does not model those concepts
+ then it cannot be embedded and so the hash code must be cached.
+ Note that a hash function might not be safe to use when
+ default-constructed (e.g if it a function pointer) so a hash
+ function that is contained in a local iterator won't be used until
+ the iterator is valid, so the hash function has been copied from a
+ correctly-initialized object.
+/para
+para
+ If the hash function is non-throwing, DefaultConstructible and
+ CopyAssignable then libstdc++ doesn't need to cache the hash code for
+ correctness, but might still do so for performance if computing a
+ hash code is an expensive operation, as it may be for arbitrarily
+ long strings.
+ As an extension libstdc++ provides a trait type to describe whether
+ a hash function is fast. By default hash functions are assumed to be
+ fast unless the trait is specialized for the hash function and the
+ trait's value is false, in which case the hash code will always be
+ cached.
+ The trait can be specialized for user-defined hash functions like so:
+/para
+programlisting
+ #include lt;unordered_setgt;
+
+ struct hasher
+ {
+std::size_t operator()(int val) const noexcept
+{
+ // Some very slow computation of a hash code from an int !
+ ...
+}
+ }
+
+ namespace std
+ {
+templatelt;gt;
+ struct __is_fast_hashlt;hashergt; : std::false_type
+ { };
+ }
+/programlisting
+ /section
+/section
+
+/section
+
+!-- Sect1 04 : Interacting with C --
section xml:id=std.containers.c xreflabel=Interacting with
CinfotitleInteracting with C/title/info
?dbhtml filename=containers_and_c.html
