[MS] How useful is the hint passed to the std::unordered_… collections? - devamazonaws.blogspot.com

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

The answer varies by implementation.

For Microsoft's STL, the hint is used by _Find_Hint:¹ 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 does nothing, whereas insert_or_assign updates the value. For containers that allow duplicate keys, a matching hint is used to insert the new element without performing a search.

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

The gcc libstdc++ implementation is mostly the same as the clang implementation: It ignores the hint for containers that do not permit duplicate keys, and it uses the hint for containers that permit duplicate keys provided the hint's key matches that of the inserted item. As a special case, for containers that permit duplicate keys that are "small" and have "slow" hash functions, 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.

Wait, what do "small" and "slow" mean? The gcc libstdc++ implementation considers a container to be "small" if it has at most 20 elements, and it considers all hash functions by default to be "fast", except for long double.

To summarize:

  Must keys be unique?
Yes No
msvc/STL Hint used if matches Hint used if matches
clang/libcxx Hint ignored Hint used if matches
gcc/libstdc++ (large or fast) Hint ignored Hint used if matches
gcc/libstdc++ (small and slow) Hint ignored Hint used

¹ In the STL code, you should know that the _Traitsobj::operator() returns true if the keys are unequal.


Post Updated on October 28, 2024 at 02:00PM
Thanks for reading
from devamazonaws.blogspot.com

Comments

Post a Comment

Popular posts from this blog

Scenarios capability now generally available for Amazon Q in QuickSight - devamazonaws.blogspot.com

Today, AWS announces the general availability of the scenarios capability of Amazon Q in QuickSight. Amazon Q guides you through data analysis by uncovering hidden trends, making recommendations for your business, and intelligently suggesting next steps for deeper exploration—all in response to natural language interactions. Now anyone can explore past trends, forecast future scenarios, and model solutions without needing specialized skill, analyst support, or manual manipulation of data in spreadsheets. With its intuitive interface and step-by-step guidance, the scenarios capability of Amazon Q in QuickSight helps users perform complex data analysis up to 10x faster than spreadsheets. Whether you're optimizing marketing budgets, streamlining supply chains, or analyzing investments, Amazon Q makes advanced data analysis accessible so you can make data-driven decisions across your organization. This capability is accessible from any Amazon QuickSight dashboard, so you can move seam...
Read more

[MS] Introducing Pull Request Annotation for CodeQL and Dependency Scanning in GitHub Advanced Security for Azure DevOps - devamazonaws.blogspot.com

Image
In the world of software development, security is paramount. As developers, we strive to write clean, efficient, and most importantly, secure code. GitHub Advanced Security for Azure DevOps has always been at the forefront of providing tools that make it easier to build and release high-quality software. Today, we’re excited to announce a new feature release that will take your code security to the next level: PR (Pull Request) Annotation for CodeQL and Dependency Scanning. PR Annotation - What Does it Mean for You? Pull Request Annotation brings security insights directly into your development workflow. Here’s how it works: When you raise a Pull Request, CodeQL runs automatically, scanning for any potential security issues. Dependency Scanning concurrently checks for vulnerabilities in packages or libraries you might be using. If any issues are found, they are reported directly on the PR interface as annotations. Developers can see exactly what the problem is and where it occu...
Read more

AWS Console Mobile Application adds support for Amazon Lightsail - devamazonaws.blogspot.com

AWS customers can now access Amazon Lightsail from within the AWS Console Mobile App to monitor and manage Lightsail instances, containers, databases, network, storage, snapshots, domains and DNS while on the go. Visit the Services tab in the AWS Console Mobile App and select Lightsail to get started. The AWS Console Mobile App enables AWS customers monitor and manage a select set of resources and receive push notifications to stay informed and connected with their AWS resources while on-the-go. The sign-in process supports biometrics authentication, making access to AWS resources simple, secure, and quick. Lightsail offers easy-to-use virtual private server (VPS) instances, storage, databases, and more for a cost-effective monthly price. For AWS services not available natively, customers can access the AWS Management Console via an in-app browser to access service pages without additional authentication, manual navigation, or need to switch from the app to a browser. Visit the AWS...
Read more