unordered containers doc

[François Dumont <frs dot dumont at gmail dot com>]

Hi

    Here is doc proposal for unordered containers hash code cache policy.

    I don't really know what to put in the new section xml:id, 
xreflabel attributes. Is there any guidelines for those ?

    I did a successful make doc-xml-validate-docbook but failed with 
make doc-html-docbook. Am I suppose to regenerate the html doc ?

François

Index: doc/xml/manual/containers.xml
===================================================================
--- doc/xml/manual/containers.xml	(revision 195814)
+++ doc/xml/manual/containers.xml	(working copy)
@@ -349,7 +349,86 @@
 
 </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>
+    <?dbhtml filename="unordered_hash.html"?>
+  
+  <section xml:id="containers.unordered.cache" xreflabel="Cache">
+    <info><title>Hash Code Caching Policy</title></info>
+    
+    <para>
+      To enhance performance of the unordered containers libstdc++ can cache
+      the hash code. But caching the hash code has also a trade off, the
+      memory overhead. Here is how libstdc++ decide to cache the hash code
+      or not.
+    </para>
+    <blockquote>
+      <para>
+	First, libstdc++ must respect the C++ Standard, erase or swap operations
+	shall not throw. As erase or swap operations in the libstdc++
+	implementation need the hash code it will be cached unless the hasher is
+	noexcept qualified.
+      </para>
+      <para>
+	Second, libstdc++ also need the hash code in the implementation of
+	local_iterator. If you want to be able to write:
+      </para>
+
+      <programlisting>
+	std::unordered_set&lt;int&gt;::local_iterator lit;
+	...
+      </programlisting>
+
+      <para>
+	the hash code must be cache or the hasher must be default constructible.
+	So if the hasher is not default constructible the hash code will be
+	cache. Note that using an uninitialized iterator fell in the category of
+	undefined behaviors. So the default constructed hasher, even if maybe
+	invalid, won't be used as long as the iterator it initialized.
+      </para>
+      <para>
+	Last, if the two previous implementation contraints are met, libstdc++
+	won't cache the hash code. But computing a hash code might be an expensive
+	operation and making your hasher not noexcept qualified or not default
+	constructible too hard just to benefit from the hash code to be cache.
+	This is why libstdc++, as an extension, provide a hash traits to qualify
+	your hasher in terms of performance. If fast libstdc++ won't cache the
+	hash code, otherwise it will. Here is how to qualify your hasher:
+      </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>
+      <para>
+	Note that default libstdc++ behavior is to consider your hasher as fast.
+      </para>
+   </blockquote>
+  </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"?>