The SGI hashing classes hash_set and
hash_set have been deprecated by the
unordered_set, unordered_multiset, unordered_map,
unordered_multimap containers in TR1 and C++11, and
may be removed in future releases.
The SGI headers
<hash_map>
<hash_set>
<rope>
<slist>
<rb_tree>
are all here;
<backwards/hash_map> and
<backwards/hash_set>
are deprecated but available as backwards-compatible extensions,
as discussed further below.
<ext/rope> is the SGI
specialization for large strings ("rope," "large strings," get it? Love
that geeky humor.)
<ext/slist> (superseded in
C++11 by <forward_list>)
is a singly-linked list, for when the doubly-linked list<>
is too much space overhead, and
<ext/rb_tree> exposes the
red-black tree classes used in the implementation of the standard maps
and sets.
Each of the associative containers map, multimap, set, and multiset have a counterpart which uses a hashing function to do the arranging, instead of a strict weak ordering function. The classes take as one of their template parameters a function object that will return the hash value; by default, an instantiation of hash. You should specialize this functor for your class, or define your own, before trying to use one of the hashing classes.
The hashing classes support all the usual associative container functions, as well as some extra constructors specifying the number of buckets, etc.
Why would you want to use a hashing class instead of the “normal”implementations? Matt Austern writes:
[W]ith a well chosen hash function, hash tables generally provide much better average-case performance than binary search trees, and much worse worst-case performance. So if your implementation has hash_map, if you don't mind using nonstandard components, and if you aren't scared about the possibility of pathological cases, you'll probably get better performance from hash_map.
The deprecated hash tables are superseded by the standard unordered
associative containers defined in the ISO C++ 2011 standard in the
headers <unordered_map>
and <unordered_set>.
@ 1.1.1.1.30.2 log @Mostly merge changes from HEAD upto 20200411 @ text @d31 1 a31 1 hashing d36 1 a36 1 hash. @ 1.1.1.1.28.1 log @Sync with HEAD, resolve a couple of conflicts @ text @d2 1 a2 1
@ 1.1.1.2 log @import GCC 6.5.0. this is largely a maint release with no particularly features listed here: http://gcc.gnu.org/gcc-6/changes.html this fixes over 250 PRs in the GCC bugzilla: https://gcc.gnu.org/bugzilla/buglist.cgi?bug_status=RESOLVED&resolution=FIXED&target_milestone=6.5 @ text @d2 1 a2 1
@ 1.1.1.3 log @import GCC 8.3. it includes these new features: - many optimisations improved: inter-procedural, profile-directed, LTO, loops including user-controllable unroll support, and more. - columns numbers added to line numbers in dwarf - gcov extended significantly - many sanitizer updates - many new warning messages - many better hints and more useful error messages - minor ABI changes on x86-64 libstdc++, and some c++17 modes - draft c++2a features - better c++17 experimental support - Armv8.4-A supported, better 8.2-A and 8.3-A support, including 32 bit arm port. cortex a-55, a-75 and a-55.a-75 combo support. - in the GCC bugzilla, 8.1 shows 1149 bugs fixed, 8.2 shows 100, and 8.3 shows 158. @ text @d31 1 a31 1 hashing d36 1 a36 1 hash. @ 1.1.1.4 log @import GCC 7.5.0. doing this here so that the vendor branch has the code we'll merge into gcc.old and the netbsd-9 tree gcc tree. GCC 8.4.0 will be imported immediately on top of this again, restoring the current status. these PRs in the GCC bugzilla are fixed with this update: 89869 80693 89795 84272 85593 86669 87148 87647 87895 88103 88107 88563 88870 88976 89002 89187 89195 89234 89303 89314 89354 89361 89403 89412 89512 89520 89590 89621 89663 89679 89704 89734 89872 89933 90090 90208 87075 85870 89009 89242 88167 80864 81933 85890 86608 87145 88857 89024 89119 89214 89511 89612 89705 89400 81740 82186 84552 86554 87609 88105 88149 88415 88739 88903 89135 89223 89296 89505 89572 89677 89698 89710 90006 90020 90071 90328 90474 91126 91162 91812 91887 90075 88998 89945 87047 87506 88074 88656 88740 91137 89008 84010 89349 91136 91347 91995 89397 87030 60702 78884 85594 87649 87725 88181 88470 88553 88568 88588 88620 88644 88906 88949 89246 89587 89726 89768 89796 89998 90108 90756 90950 91704 88825 88983 86538 51333 89446 90220 91308 92143 89392 90213 90278 91131 91200 91510 89037 91481 87673 88418 88938 88948 90547 27221 58321 61250 67183 67958 77583 83531 86215 88648 88720 88726 89091 89466 89629 90105 90329 90585 90760 90924 91087 89222 81956 71861 35031 69455 81849 82993 85798 88138 88155 88169 88205 88206 88228 88249 88269 88376 77703 80260 82077 86248 88393 90786 57048 66089 66695 67679 68009 71723 72714 84394 85544 87734 88298 90937 91557 63891 64132 65342 68649 68717 71066 71860 71935 77746 78421 78645 78865 78983 79485 79540 85953 88326 89651 90744 @ text @d31 1 a31 1 hashing d36 1 a36 1 hash. @ 1.1.1.5 log @re-import GCC 8.4.0. @ text @d31 1 a31 1 hashing d36 1 a36 1 hash. @ 1.1.1.6 log @initial import of GCC 10.3.0. main changes include: caveats: - ABI issue between c++14 and c++17 fixed - profile mode is removed from libstdc++ - -fno-common is now the default new features: - new flags -fallocation-dce, -fprofile-partial-training, -fprofile-reproducible, -fprofile-prefix-path, and -fanalyzer - many new compile and link time optimisations - enhanced drive optimisations - openacc 2.6 support - openmp 5.0 features - new warnings: -Wstring-compare and -Wzero-length-bounds - extended warnings: -Warray-bounds, -Wformat-overflow, -Wrestrict, -Wreturn-local-addr, -Wstringop-overflow, -Warith-conversion, -Wmismatched-tags, and -Wredundant-tags - some likely C2X features implemented - more C++20 implemented - many new arm & intel CPUs known hundreds of reported bugs are fixed. full list of changes can be found at: https://gcc.gnu.org/gcc-10/changes.html @ text @d2 1 a2 1
The SGI hashing classes hash_set and
hash_set have been deprecated by the
unordered_set, unordered_multiset, unordered_map,
unordered_multimap containers in TR1 and C++11, and
may be removed in future releases.
The SGI headers
<hash_map>
<hash_set>
<rope>
<slist>
<rb_tree>
are all here;
<backwards/hash_map> and
<backwards/hash_set>
are deprecated but available as backwards-compatible extensions,
as discussed further below.
<ext/rope> is the SGI
specialization for large strings ("rope," "large strings," get it? Love
that geeky humor.)
<ext/slist> (superseded in
C++11 by <forward_list>)
is a singly-linked list, for when the doubly-linked list<>
is too much space overhead, and
<ext/rb_tree> exposes the
red-black tree classes used in the implementation of the standard maps
and sets.
Each of the associative containers map, multimap, set, and multiset have a counterpart which uses a hashing function to do the arranging, instead of a strict weak ordering function. The classes take as one of their template parameters a function object that will return the hash value; by default, an instantiation of hash. You should specialize this functor for your class, or define your own, before trying to use one of the hashing classes.
The hashing classes support all the usual associative container functions, as well as some extra constructors specifying the number of buckets, etc.
Why would you want to use a hashing class instead of the “normal”implementations? Matt Austern writes:
[W]ith a well chosen hash function, hash tables generally provide much better average-case performance than binary search trees, and much worse worst-case performance. So if your implementation has hash_map, if you don't mind using nonstandard components, and if you aren't scared about the possibility of pathological cases, you'll probably get better performance from hash_map.
The deprecated hash tables are superseded by the standard unordered
associative containers defined in the ISO C++ 2011 standard in the
headers <unordered_map>
and <unordered_set>.
The SGI hashing classes hash_set and
hash_set have been deprecated by the
unordered_set, unordered_multiset, unordered_map,
unordered_multimap containers in TR1 and C++11, and
may be removed in future releases.
The SGI headers
<hash_map>
<hash_set>
<rope>
<slist>
<rb_tree>
are all here;
<backwards/hash_map> and
<backwards/hash_set>
are deprecated but available as backwards-compatible extensions,
as discussed further below.
<ext/rope> is the SGI
specialization for large strings ("rope," "large strings," get it? Love
that geeky humor.)
<ext/slist> (superseded in
C++11 by <forward_list>)
is a singly-linked list, for when the doubly-linked list<>
is too much space overhead, and
<ext/rb_tree> exposes the
red-black tree classes used in the implementation of the standard maps
and sets.
Each of the associative containers map, multimap, set, and multiset have a counterpart which uses a hashing function to do the arranging, instead of a strict weak ordering function. The classes take as one of their template parameters a function object that will return the hash value; by default, an instantiation of hash. You should specialize this functor for your class, or define your own, before trying to use one of the hashing classes.
The hashing classes support all the usual associative container functions, as well as some extra constructors specifying the number of buckets, etc.
Why would you want to use a hashing class instead of the “normal”implementations? Matt Austern writes:
[W]ith a well chosen hash function, hash tables generally provide much better average-case performance than binary search trees, and much worse worst-case performance. So if your implementation has hash_map, if you don't mind using nonstandard components, and if you aren't scared about the possibility of pathological cases, you'll probably get better performance from hash_map.
The deprecated hash tables are superseded by the standard unordered
associative containers defined in the ISO C++ 2011 standard in the
headers <unordered_map>
and <unordered_set>.