Hello again! This lesson's topic is Sorted Maps (or Sorted Dicts). Similar to dictionaries, Sorted Maps are data structures that store key-value pairs but in an ordered manner. Learning about Sorted Maps enriches our set of tools for organized and efficient data manipulation. Today's goal is to work with Sorted Maps using the Python sortedcontainers library.

In Python, we differentiate between standard dictionaries and Sorted Maps. Comparing regular dictionaries to Sorted Maps is akin to comparing a messy bookshelf to a well-organized library — the latter maintains order. Although Python natively does not include Sorted Maps, we'll leverage an external library, sortedcontainers.

The sortedcontainers library is a Python package that offers a Sorted List, Sorted Set, and Sorted Dict. Unlike regular collections, sorted collections maintain an order for their elements, which can be valuable for many algorithms and applications. Today, we'll utilize the SortedDict class from sortedcontainers, a dictionary that sorts its keys.

To create a SortedDict object, pass a dictionary or any key-value pair iterable, ensuring that the keys are immutable. For instance:

Python
Copy to clipboard
1from sortedcontainers import SortedDict
2
3# Dictionary with fruits as keys and corresponding counts as values
4sd = SortedDict({'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2})
5
6# Print the SortedDict
7print(sd)  # Output: SortedDict({'apple': 4, 'banana': 3, 'orange': 2, 'pear': 1})

A SortedDict object boasts several useful methods. Here are some crucial ones:

• SortedDict.bisect_left(key): This identifies an insertion point for a new key. If the key already exists, the insertion point is to the left of any current entries.
• SortedDict.bisect_right(key): This is similar to bisect_left, but with the insertion point to the right of existing entries.
• SortedDict.pop(key[, default]): This removes the specified key and returns its associated value.
• SortedDict.get(key[, default]): This presents the value for the key if it exists; otherwise, it returns a default value.
• SortedDict.peekitem(index=-1): This method allows you to peek at an item in the sorted dictionary without removing it. By default, it returns the last (maximum) item as a (key, value) tuple. You can specify an index to peek at an item in a specific position based on its key order.

Consider the following Python code, which incorporates these methods:

Python
Copy to clipboard
1from sortedcontainers import SortedDict
2
3# Initialize SortedDict
4sd = SortedDict({'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2})
5
6# 'apple' is found at index 0
7print(sd.bisect_left('apple'))  # Output: 0
8# 'apple' is found before index 1
9print(sd.bisect_right('apple'))  # Output: 1
10
11# Remove 'apple' and print the removed item
12item = sd.pop('apple')
13print('Popped item:', item)  # Output: Popped: 4
14
15# Attempt to fetch a nonexisting key
16value = sd.get('apple', 'Not found')
17print('Value:', value)  # Output: Value: Not found
18
19# Peek at the last item
20last_item = sd.peekitem()
21print('Last item:', last_item)  # Output: Last item: ('pear', 1)

Congratulations! You have successfully delved into sorted maps. This exploration included understanding the sortedcontainers library, creating SortedDict instances, and navigating SortedDict's valuable methods. Next, you can look forward to hands-on exercises to fortify your understanding and expand your skillset. Keep practicing!