{"id":110428,"date":"2024-10-28T07:00:00","date_gmt":"2024-10-28T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110428"},"modified":"2024-10-28T07:00:01","modified_gmt":"2024-10-28T14:00:01","slug":"20241028-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20241028-00\/?p=110428","title":{"rendered":"How useful is the hint passed to the std::unordered_…<\/CODE> collections?"},"content":{"rendered":"

A little while ago, we learned about the value of the hint<\/code> to the C++ ordered associative containers std::map<\/code>, std::multimap<\/code>, std::set<\/code>, and std::multiset<\/code><\/a>. But what about the unordered associative containers std::unordered_map<\/code>, std::unordered_multimap<\/code>, std::unordered_set<\/code>, and std::unordered_multiset<\/code>?<\/p>\n

The answer varies by implementation.<\/p>\n

For Microsoft’s STL, the hint is used by _Find_Hint<\/code><\/a>:\u00b9 If the hint’s key is equivalent to the inserted item’s key, then we keep the hint. Otherwise, we ignore it. For containers that do not permit duplicate keys, a matching hint provides the exact node to update, avoiding the need to do a search for it. The code can just update the value or do nothing, depending on the method being implemented: insert<\/code> does nothing, whereas insert_or_assign<\/code> updates the value. For containers that allow duplicate keys, a matching hint is used to insert the new element without performing a search.<\/p>\n

The clang libcxx implementations outright ignores the hint for containers that do not permit duplicate keys<\/a>. For containers that permit duplicate keys, a hint whose key is equivalent to the item being inserted<\/a> is used to insert the new element without performing a search.<\/p>\n

The gcc libstdc++ implementation is mostly the same as the clang implementation: It ignores the hint for containers that do not permit duplicate keys<\/a>, and it uses the hint for containers that permit duplicate keys provided the hint’s key matches that of the inserted item<\/a>. As a special case, for containers that permit duplicate keys that are “small” and have “slow” hash functions<\/a>, it uses the hint as the starting point for a linear search through the hash table contents looking for a matching key. The idea is that if the hash function is “slow”, then it’s faster to just compare keys instead of going to effort of hashing them.<\/p>\n

Wait, what do “small” and “slow” mean? The gcc libstdc++ implementation considers a container to be “small” if it has at most 20 elements<\/a>, and it considers all hash functions by default to be “fast”<\/a>, except for long double<\/code>.<\/p>\n

To summarize:<\/p>\n\n\n\n\n\n\n\n\n
\u00a0<\/th>\nMust keys be unique?<\/th>\n<\/tr>\n
Yes<\/th>\nNo<\/th>\n<\/tr>\n
msvc\/STL<\/th>\nHint used if matches<\/td>\nHint used if matches<\/td>\n<\/tr>\n
clang\/libcxx<\/th>\nHint ignored<\/td>\nHint used if matches<\/td>\n<\/tr>\n
gcc\/libstdc++ (large or fast)<\/th>\nHint ignored<\/td>\nHint used if matches<\/td>\n<\/tr>\n
gcc\/libstdc++ (small and slow)<\/th>\nHint ignored<\/td>\nHint used<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\u00b9 In the STL code, you should know that the _Traitsobj::operator()<\/code> returns true<\/code> if the keys are unequal<\/i><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Only a little, or sometimes not at all.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110428","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Only a little, or sometimes not at all.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=110428"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110428\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}