Don’t Settle for Unsorted: How Python Sorted Containers Can Revolutionize Your Code

How often did you observe the need for a data structure capable of sorting elements based on a specific key or criteria, rather than merely holding them? Naturally, one might initially consider the Heap data structure (priority queue). However, you may quickly encounter challenges with searching and replacement operations, leading to the realization that a heap is not the optimal solution in this case.

In this article let’s take a walkthrough of “Python Sorted Containers” a third-party library that offers a set of data structures maintaining their items in sorted order. It’s useful for operations like insertion, deletion, and search on sorted collections.

The Key data structures include:

• SortedDict: This implementation functions as a sorted dictionary, ensuring items are stored in sorted order based on their keys. It parallels the built-in Python dictionary but guarantees ordered items.
• SortedList: It’s a sorted list implementation. Unlike Python’s built-in list, it maintains elements in sorted order, providing quick access to sorted data.
• SortedSet: Similar to Python’s set, SortedSet is a collection of unique elements but maintains them in sorted order. This facilitates an efficient range of queries and other operations.

The advantage of using sortedcontainers lies in combining the efficiency of sorted data structures with the flexibility of Python’s native collections. It ensures fast performance for common operations while maintaining a familiar Pythonic interface.

Python’s standard library is great until you need a sorted collections type. Many will attest that you can get really far without one, but the moment you really need a sorted list, sorted dict, or sorted set, you’re faced with a dozen different implementations, most using C-extensions without great documentation and benchmarking. — library docs —

To use sorted containers, install it using pip:

pip install sortedcontainers

After installation, import and use the provided data structures, such as SortedDict, SortedSet, and SortedList, in your Python code.

from sortedcontainers import SortedDict, SortedList, SortedSet

Now Let’s dig deeper into these containers to learn more about key features, and considerations, and answer some questions that come to mind while viewing them, take an overview of Python code snippets to learn how to use them:

Sorted Dict

SortedDict functions as a sorted dictionary, maintaining its items in sorted order based on their keys. This data structure combines the characteristics of a dictionary with the guarantee of sorted order. Here are some key features and considerations for using SortedDict:

1. Sorted Order: The primary feature of SortedDict is that it keeps its items sorted based on their keys. This makes it suitable for use-cases where maintaining a specific order of items is essential.

2. Similar Interface to Dict: SortedDict provides an interface similar to the built-in Python dictionary. You can use common dictionary operations such as get, set, pop, and iteration over keys and values.

3. Efficient Operations: It offers efficient insertion and deletion operations with a time complexity similar to or better than the built-in dictionary. The sorted order ensures that lookups and range queries are faster compared to an unsorted collection.

4. Use Cases: SortedDict is beneficial when you need to store key-value pairs and require the items to be ordered based on their keys. This can be useful in use-cases where you want to iterate over the dictionary in a sorted manner or perform range queries based on key values.

Here's an example of using SortedDict:

from sortedcontainers import SortedDict
# Creating a SortedDict
my_dict = SortedDict({'banana': 3, 'apple': 1, 'orange': 2})
# Adding new items
my_dict['grape'] = 4
print(my_dict)
#SortedDict({'apple': 1, 'banana': 3, 'grape': 4, 'orange': 2})

What is the difference between dict, OrderedDict, and sortedDict?

• The regular dictionary (dict) is a native data structure in Python and does not guarantee any specific order for its items.
• The ordered dictionary (OrderedDict) is one Python collections and maintains the order in which items are inserted.
• The sorted dictionary (SortedDict) is sortedcontainers third-party data structure that maintains its items in sorted order based on keys.

Here’s an example of using all of them and what you expecting from every type:

from collections import OrderedDict
from sortedcontainers import SortedDict

# Regular Python Dictionary (dict)
regular_dict = {'apple': 3, 'banana': 2, 'orange': 1}
print("Regular Dictionary:", regular_dict)
#Regular Dictionary: {'apple': 3, 'banana': 2, 'orange': 1}

# Ordered Dictionary (OrderedDict)
ordered_dict = OrderedDict([('apple', 3), ('banana', 2), ('orange', 1)])
print("Ordered Dictionary:", ordered_dict)
#Ordered Dictionary: OrderedDict([('apple', 3), ('banana', 2), ('orange', 1)])


# Sorted Dictionary (SortedDict)
sorted_dict = SortedDict({'apple': 3, 'banana': 2, 'orange': 1})
print("Sorted Dictionary:", sorted_dict)
#Sorted Dictionary: SortedDict({'apple': 3, 'banana': 2, 'orange': 1})


# Adding a new item to each dictionary
regular_dict['grape'] = 4
ordered_dict['grape'] = 4
sorted_dict['grape'] = 4

print("Regular Dictionary:", regular_dict)
#Regular Dictionary: {'apple': 3, 'banana': 2, 'orange': 1, 'grape': 4}

print("Ordered Dictionary:", ordered_dict)
#Ordered Dictionary: OrderedDict([('apple', 3), ('banana', 2), ('orange', 1), ('grape', 4)])

print("Sorted Dictionary:", sorted_dict)
#Sorted Dictionary: SortedDict({'apple': 3, 'banana': 2, 'grape': 4, 'orange': 1})

As you see that the regular dictionary may not preserve the order of insertion, the ordered dictionary preserves the insertion order but without any consideration for sorting, and the sorted dictionary guarantees sorted order based on keys, and don’t keep any criteria about order of insertion.

Sorted List

SortedList functions as a sorted list, maintaining its elements in sorted order besides combining the characteristics of a list with the guarantee of sorted order, offering efficient operations for insertion, deletion, and search. Here are some key features and considerations for using SortedList:

1. Sorted Order: The defining characteristic of SortedList lies in its ability to maintain a sorted order of elements. This quality proves beneficial in situations where preserving a specific order of items is of paramount importance.

2. List-Like Interface: SortedList provides an interface similar to the built-in Python list. You can use common list operations such as indexing, slicing, appending, and popping.

3. Efficient Operations: It offers efficient insertion and deletion operations with a time complexity similar to or better than the built-in list. The sorted order ensures that binary search-based operations are faster compared to an unsorted list.

4. Use Cases: SortedList is beneficial when you need a list-like data structure that maintains its elements in sorted order. This can be helpful in use-cases where you want to perform efficient searches or maintain a sorted collection of elements.

Here’s an example of using SortedList:

from sortedcontainers import SortedList

# Creating a SortedList
sorted_list = SortedList([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print("Sorted List:", sorted_list)
#Sorted List: SortedList([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])

# Adding new elements
sorted_list.add(8)
sorted_list.update([7, 0])
print("Updated Sorted List:", sorted_list)
#Updated Sorted List: SortedList([0, 1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9])

# Removing elements
sorted_list.discard(5)
print("Sorted List after Discarding 5:", sorted_list)
#Sorted List after Discarding 5: SortedList([0, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9])

# Performing binary search
index = sorted_list.bisect_left(4)
print("Index of 4 in Sorted List:", index)
#Index of 4 in Sorted List: 6

What is the difference between SortedList and heapq in Python?

Of course, this question can come to your mind while thinking about the difference between them and when to use them, but in the short answer yes, they share major similarities in main functions but with minor preferences depending on the use case, This table provides a quick overview of the key characteristics and use cases of SortedList and heapq:

Comparison between SortedList and heapq

Sorted Set

SortedSet operates as a sorted set, which is a collection of unique elements maintained in sorted order. Here are key features and considerations for using SortedSet:

1. Sorted Order: The primary characteristic is that it keeps its elements in sorted order. Elements are unique, and the set maintains a specific order based on their values, so it can be a Swiss knife data structure, imagine having container able to keep items sorted and unique in the same time with efficient management way.

2. Set-Like Interface: SortedSet provides a set-like interface, supporting common set operations such as union, intersection, and difference, besides efficient membership tests, insertions, and deletions.

3. Efficient Operations: Similar to other data structures in the sortedcontainers library, SortedSet offers efficient operations with a time complexity comparable to or better than the built-in set.

4. Use Cases: Ideal when you need a set with elements maintained in a specific order. It’s suitable where you require both set-like operations and the guarantee of sorted order.

Here’s an example of the usage of SortedSet:

from sortedcontainers import SortedSet

# Creating a SortedSet
sorted_set = SortedSet([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print("Sorted Set:", sorted_set)
#Sorted Set: SortedSet([1, 2, 3, 4, 5, 6, 9])


# Adding a new element
sorted_set.add(8)
print("Sorted Set after Adding 8:", sorted_set)
#Sorted Set after Adding 8: SortedSet([1, 2, 3, 4, 5, 6, 8, 9])


# Performing set-like operations
intersection_set = sorted_set.intersection([1, 2, 3, 4, 5])
print("Intersection Set:", intersection_set)
#Intersection Set: SortedSet([1, 2, 3, 4, 5])

Overall, Python sortedcontainers provide an effective solution for maintaining sorted data structures. The SortedDict, SortedList, and SortedSet offer specific benefits and an intuitive Python interface. By combining the versatility of Python’s built-in collections with the efficiency of sorted data structures, these containers are advantageous for a range of needs. From managing sorted key-value pairs to organizing lists and sets, Python Sorted Containers offer improved speed and ease of use. Ultimately, the main goal is to strategically position the appropriate container to maximize the advantages based on the specific use case.

If you have any questions about this topic it would be great to reach me on LinkedIn.