Efficient Hash Maps and Sets in C++ STL Quiz Quiz

Explore key concepts of using hash maps and sets with the C++ Standard Template Library. This quiz covers usage, efficiency, operations, and common pitfalls to help solidify foundational understanding for programmers working with unordered_map and unordered_set containers in C++.

1. Default Container for Hash Maps

   Which container in C++ STL should you use to implement a hash-based key-value map for efficient average-time lookups?

   1. set
   2. unordered_map
   3. map
   4. vector

   Explanation: unordered_map is a hash-based associative container that provides constant average-time complexity for lookups. map implements a balanced tree, resulting in log-time lookup, while vector does not support key-value associations. set stores only unique values without a value component, making unordered_map the correct choice.

2. Unique Elements Guarantee in Sets

   Which property is always true for unordered_set in C++ STL, even if you try to insert identical values multiple times?

   1. No sorting is guaranteed
   2. All values remain unique
   3. Duplicate values are allowed
   4. Values are automatically sorted

   Explanation: An unordered_set ensures all elements are unique, and adding a duplicate value has no effect. Duplicate values are explicitly not allowed. While no sorting is guaranteed, that alone does not distinguish unordered_set from other containers, and the uniqueness requirement is always enforced.

3. Underlying Data Structure

   What is the underlying data structure most commonly used by unordered_map and unordered_set?

   1. Hash table
   2. Doubly linked list
   3. Binary search tree
   4. Heap

   Explanation: Both unordered_map and unordered_set are implemented using hash tables, allowing fast average-time lookups. Binary search trees like those used in map or set offer log-time complexity. Doubly linked lists and heaps are not used as underlying structures in these containers.

4. Valid Insertion Syntax for unordered_set

   What is the correct way to insert the integer 7 into an unordered_set named 'numbers'?

   1. numbers.add(7);
   2. numbers.insert(7);
   3. numbers.append(7);
   4. numbers.push(7);

   Explanation: The insert member function is used for adding elements to an unordered_set. add, push, and append are not valid member functions for unordered_set. Using anything other than insert will result in a compilation error.

5. Checking for Element Existence

   Which method should you use to efficiently check whether key 42 exists in an unordered_map named 'data'?

   1. data.exists(42)
   2. data.contains(42, 0)
   3. data.find(42) != data.end()
   4. data[42]

   Explanation: Using find and comparing to end efficiently checks for key existence without modifying the container. The contains function is only available in more recent standards, and exists does not exist as a member. Using operator[] will insert the key if it does not exist, which is inefficient for existence checks.

6. Time Complexity of Insertion

   What is the average time complexity for inserting an element into an unordered_set?

   1. O(1)
   2. O(n)
   3. O(log n)
   4. O(n log n)

   Explanation: Average-time insertion in an unordered_set is O(1) because it uses a hash table. log n complexity is typical for tree-based containers such as set. O(n) and O(n log n) are incorrect, as hash tables optimize for constant average-time insertion.

7. Hash Function Customization

   If you want to use a custom data type as the key in an unordered_map, what must you provide?

   1. A comparison operator only
   2. A copy constructor
   3. A move assignment operator
   4. A hash function and equality operator

   Explanation: For custom keys in unordered_map, a hash function and equality operator are needed for storage and lookup. Comparison operators are used in ordered containers, not unordered_map. Copy and move operations affect copying and moving but are not sufficient for key usage.

8. Bucket Count Adjustment

   Which operation directly affects the number of internal buckets in an unordered_set, potentially reducing collisions?

   1. reserve
   2. rehash
   3. compress
   4. sort

   Explanation: The rehash function changes the number of buckets, impacting collision handling efficiency. sort does not affect hash tables as they are unordered. reserve adjusts capacity for elements, not buckets, and compress is not a valid unordered_set member function.

9. Duplicate Key Handling in unordered_map

   What happens if you insert a new pair with a key already existing in an unordered_map?

   1. Insertion fails with an error
   2. The old value is deleted, and none added
   3. The value for the key is updated
   4. Both values are stored

   Explanation: When a duplicate key is inserted in an unordered_map, the corresponding value is updated. Insertion does not fail, and unordered_map does not store duplicate keys with different values. The old value is replaced, not deleted without replacement.

10. Removing an Element from unordered_set

    What is the correct way to remove the value 15 from an unordered_set named 'nums'?

    1. nums.delete(15);
    2. nums.remove(15);
    3. nums.erase(15);
    4. nums.pop(15);

    Explanation: The erase function is the correct way to remove elements from an unordered_set. remove, delete, and pop are not valid member functions and will cause compilation errors. Using erase ensures the specified value is removed if it exists.