From 37db34b1d053392f4d8899178a7f647bb70f400e Mon Sep 17 00:00:00 2001 From: redi Date: Mon, 11 Feb 2013 00:19:41 +0000 Subject: =?UTF-8?q?2013-02-10=20=20Fran=C3=A7ois=20Dumont=20=20=20=09=20=20=20=20Jonathan=20Wakely=20=20?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * doc/xml/manual/containers.xml: Add section on unordered containers. * doc/xml/manual/using.xml: Fix incomplete sentence. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@195937 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 6 +++ libstdc++-v3/doc/xml/manual/containers.xml | 82 +++++++++++++++++++++++++++++- libstdc++-v3/doc/xml/manual/using.xml | 2 +- 3 files changed, 88 insertions(+), 2 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 522c8851a00..32b391ee475 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2013-02-10 François Dumont + Jonathan Wakely + + * doc/xml/manual/containers.xml: Add section on unordered containers. + * doc/xml/manual/using.xml: Fix incomplete sentence. + 2013-02-10 Jonathan Wakely PR libstdc++/56267 diff --git a/libstdc++-v3/doc/xml/manual/containers.xml b/libstdc++-v3/doc/xml/manual/containers.xml index c90ffc65e46..920b491db36 100644 --- a/libstdc++-v3/doc/xml/manual/containers.xml +++ b/libstdc++-v3/doc/xml/manual/containers.xml @@ -349,7 +349,87 @@ - + +
+ Unordered Associative + + +
+ Hash Code + +
+ Hash Code Caching Policy + + + 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. + + + The C++ standard requires that erase and swap + 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 noexcept + or throw(). + + + Secondly, libstdc++ also needs the hash code in the implementation of + local_iterator and const_local_iterator 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. + + + 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: + + + #include <unordered_set> + + struct hasher + { + std::size_t operator()(int val) const noexcept + { + // Some very slow computation of a hash code from an int ! + ... + } + } + + namespace std + { + template<> + struct __is_fast_hash<hasher> : std::false_type + { }; + } + +
+
+ +
+ +
Interacting with C diff --git a/libstdc++-v3/doc/xml/manual/using.xml b/libstdc++-v3/doc/xml/manual/using.xml index 61190f5d17b..dfc5cef2408 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 -The exclamation point to the left of the stdc++.h.gch listing means that the generated PCH file was used, and thus the +The exclamation point to the left of the stdc++.h.gch listing means that the generated PCH file was used. Detailed information about creating precompiled header files can be found in the GCC documentation. -- cgit v1.2.1