Is it good idea to store unordered_set as key in unordered_map

Question

I am looking to store unordered_set as key in unordered_map, is it good idea or I should use std::set to store some data and then use std::map to store std::set as key. Which would be better for performance/lookup?

Any suggestions would help

Answer 1

As with a lot of data-structure performance-related questions, the precise answer will depend on your data set.
Considering that you're only interested in lookup performance, small data sets will generally favor using the ordered versions of containers, where "data set" means the average number of elements in your keys for the key type (set vs. unordered_set), and the number of (set, value_type) items for the outer map type (map vs. unordered_map). By the way, nothing prevents you from mixing ordered and unordered containers, such as unordered_map, value_type>
Still, the only way to be 100% sure which container is better, is to profile this with your actual data.

With that in mind, here are some more details:

• For the outer container, there's a good chance that using unordered_map will deliver better lookup performance, based on the usual characteristics of hash containers. However, there is a subtler impact which depends on the comparative performance of the key container's hash less-than operator and function.
• For the key container, lookup performance is impacted by the relative performance of the container's less-than-operator (if your outer container is a map) or its hash function (if your outer container is an unordered_map).

I'll try to post some actual tests to measure this later.