Patchwork unordered containers doc

login
register
mail settings
Submitter Jonathan Wakely
Date Feb. 11, 2013, 12:24 a.m.
Message ID <CAH6eHdTj3vcuqoTCkhCWsHMWrOJV14vioBVJbPN-g68nYD8YJg@mail.gmail.com>
Download mbox | patch
Permalink /patch/219531/
State New
Headers show

Comments

Jonathan Wakely - Feb. 11, 2013, 12:24 a.m.
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  <fdumont@gcc.gnu.org>
            Jonathan Wakely  <jwakely.gcc@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.gcc@gmail.com>
Date:   Sun Feb 10 22:27:40 2013 +0000

    2013-02-10  François Dumont  <fdumont@gcc.gnu.org>
    	    Jonathan Wakely  <jwakely.gcc@gmail.com>
    
    	* doc/xml/manual/containers.xml: Add section on unordered containers.
    	* doc/xml/manual/using.xml: Fix incomplete sentence.
François Dumont - Feb. 11, 2013, 9:34 p.m.
That's crystal clear. I think I can recognize one or two words from my 
original proposal like 'The' or 'in' :-)

François


On 02/11/2013 01:24 AM, Jonathan Wakely wrote:
> 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  <fdumont@gcc.gnu.org>
>              Jonathan Wakely  <jwakely.gcc@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.
Benjamin Kosnik - Feb. 12, 2013, 12:48 a.m.
> 2013-02-10  François Dumont  <fdumont@gcc.gnu.org>
>             Jonathan Wakely  <jwakely.gcc@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.

Great to see this. 

Jonathan, I can confirm validation and html creation. Just sanity
checking.....

I re-generated the html bits for the gcc website. You can find the diff
attached. 

-benjamin

Patch

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">
+  <info><title>Unordered Associative</title></info>
+  <?dbhtml filename="unordered_associative.html"?>
+
+  <section xml:id="containers.unordered.hash" xreflabel="Hash">
+    <info><title>Hash Code</title></info>
+
+  <section xml:id="containers.unordered.cache" xreflabel="Cache">
+    <info><title>Hash 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 <code>erase</code> and <code>swap</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 <code>noexcept</code>
+      or <code>throw()</code>.
+    </para>
+    <para>
+      Secondly, libstdc++ also needs the hash code in the implementation of
+      <code>local_iterator</code> and <code>const_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_set&gt;
+
+      struct hasher
+      {
+        std::size_t operator()(int val) const noexcept
+        {
+          // Some very slow computation of a hash code from an int !
+          ...
+        }
+      }
+
+      namespace std
+      {
+        template&lt;&gt;
+          struct __is_fast_hash&lt;hasher&gt; : std::false_type
+          { };
+      }
+    </programlisting>
+  </section>
+</section>
+
+</section>
+
+<!-- Sect1 04 : Interacting with C -->
 <section xml:id="std.containers.c" xreflabel="Interacting with C"><info><title>Interacting with C</title></info>
 <?dbhtml filename="containers_and_c.html"?>
   
diff --git a/libstdc++-v3/doc/xml/manual/using.xml b/libstdc++-v3/doc/xml/manual/using.xml
index 61190f5..dfc5cef 100644
--- a/libstdc++-v3/doc/xml/manual/using.xml
+++ b/libstdc++-v3/doc/xml/manual/using.xml
@@ -755,7 +755,7 @@  g++ -Winvalid-pch -I. -include stdc++.h -H -g -O2 hello.cc -o test.exe
 . /mnt/share/bld/H-x86-gcc.20071201include/c++/4.3.0/string
 </programlisting>
 
-<para>The exclamation point to the left of the <code>stdc++.h.gch</code> listing means that the generated PCH file was used, and thus the </para>
+<para>The exclamation point to the left of the <code>stdc++.h.gch</code> listing means that the generated PCH file was used.</para>
 <para/>
 
 <para> Detailed information about creating precompiled header files can be found in the GCC <link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="http://gcc.gnu.org/onlinedocs/gcc/Precompiled-Headers.html">documentation</link>.