Hone logo
Hone
Problems

Implementing a Custom Defaultdict

Many programming tasks involve grouping or counting items. Often, you'll want to associate values with keys in a dictionary. However, standard Python dictionaries raise a KeyError if you try to access a key that doesn't exist. The collections.defaultdict class elegantly solves this by providing a default value for any key that hasn't been explicitly set. Your challenge is to implement a similar defaultdict from scratch.

Problem Description

Your task is to create a Python class named CustomDefaultdict that mimics the behavior of collections.defaultdict. This custom class should behave like a standard Python dictionary but should automatically provide a default value when a non-existent key is accessed for the first time.

Key Requirements:

  • The CustomDefaultdict class should accept a default_factory argument during initialization. This default_factory will be a callable (like a function or a type, e.g., int, list, set) that is called without arguments to produce the default value for a new key.
  • When an item is accessed using square bracket notation (e.g., my_dict[key]) and the key does not exist, the default_factory should be called, and its return value should be inserted into the dictionary as the value for that key. Subsequent accesses to the same key should return this stored default value.
  • The CustomDefaultdict should support standard dictionary operations like assignment (my_dict[key] = value), iteration, and checking for key existence (key in my_dict).
  • If no default_factory is provided during initialization, it should default to None (similar to how collections.defaultdict with no arguments would behave if it were meant to raise errors, though in this exercise, we'll assume a default_factory is always provided, making it more useful).

Expected Behavior:

When you try to access a key that doesn't exist, the default_factory is invoked, its result is stored and returned, and the dictionary is modified.

Edge Cases to Consider:

  • What happens if the default_factory returns None?
  • How should the class handle being initialized with different types of callables (e.g., int, list, a lambda function)?

Examples

Example 1: Using int as a default factory for counting.

# Initialize CustomDefaultdict with int as the default factory
counts = CustomDefaultdict(int)

# Accessing a new key automatically assigns 0
print(counts['apple'])
# Expected Output: 0
print(counts)
# Expected Output: {'apple': 0}

# Incrementing the count
counts['apple'] += 1
print(counts['apple'])
# Expected Output: 1
print(counts)
# Expected Output: {'apple': 1}

# Accessing another new key
print(counts['banana'])
# Expected Output: 0
print(counts)
# Expected Output: {'apple': 1, 'banana': 0}

Explanation: When counts['apple'] is accessed for the first time, the default_factory (int) is called, returning 0. This 0 is stored as the value for 'apple', and then returned. Subsequent accesses to 'apple' return the stored value. When 'apple' is incremented, its value changes.

Example 2: Using list as a default factory for grouping.

# Initialize CustomDefaultdict with list as the default factory
groups = CustomDefaultdict(list)

# Adding items to lists associated with keys
groups['students'].append('Alice')
groups['students'].append('Bob')
groups['teachers'].append('Mr. Smith')

print(groups)
# Expected Output: {'students': ['Alice', 'Bob'], 'teachers': ['Mr. Smith']}

# Accessing a new key
print(groups['assistants'])
# Expected Output: []
print(groups)
# Expected Output: {'students': ['Alice', 'Bob'], 'teachers': ['Mr. Smith'], 'assistants': []}

Explanation: When groups['students'] is accessed and the key doesn't exist, list() is called, returning an empty list []. This list is assigned to 'students'. Then, elements are appended to this list. When groups['assistants'] is accessed, a new empty list is created and assigned to 'assistants'.

Example 3: Using a lambda function as a default factory.

# Initialize CustomDefaultdict with a lambda that returns a specific string
messages = CustomDefaultdict(lambda: "No message yet")

print(messages['user1'])
# Expected Output: No message yet
print(messages)
# Expected Output: {'user1': 'No message yet'}

messages['user1'] = "Welcome!"
print(messages['user1'])
# Expected Output: Welcome!
print(messages)
# Expected Output: {'user1': 'Welcome!'}

print(messages['user2'])
# Expected Output: No message yet
print(messages)
# Expected Output: {'user1': 'Welcome!', 'user2': 'No message yet'}

Explanation: The lambda function lambda: "No message yet" is called when a new key is accessed, providing the string "No message yet" as the default value.

Constraints

  • The CustomDefaultdict class should be implemented solely in Python.
  • You can inherit from dict if it simplifies your implementation, but the core __missing__ logic should be explicitly handled.
  • The default_factory will always be a valid callable.
  • Your implementation should efficiently handle a large number of key accesses and assignments.

Notes

  • Consider how Python's dictionary works internally. You might find the __missing__ special method particularly useful.
  • Think about how to store the default_factory and how to use it when a key is not found.
  • Ensure your class can be initialized with any valid callable as its default_factory.
Loading editor...
python