Everything About Python SortedDict

Sorteddict is present in “sortedcontainers” library. It is similar to ordered mapping in c++. This is a mapping method similar to dictionaries in python. It contains key-value pairs. The only difference in sortedDict is the keys are stored in a sorted manner. The keys in SortedDict must be hashable. So, if you want a sorted dictionary structure for your projects, this is the perfect place.

It almost had the same methods as a normal dictionary in python. The key-value pairs can be added, deleted, and updated using functions provided by “sorteddict”. So, let’s understand how you can use it –

Importing Python SortedDict

First, you’ll have to install sortedcontainers external module. To do this, use the following command –

pip install sortedcontainers

For users using jupyter and Anaconda, you might have a different virtual environment; you need to install the module there.

Importing dictionary from sorted containers.

from sortedcontainers import sortedDict

Now, you can use the SortedDict class to initialize a dictionary and sort it.

Initializing a Python SortedDict

Initializing an empty sorted dictionary. This is the same as creating an object instance.

dict = SortedDict()

We can either initialize an empty dictionary or declare some key, and value pairs while initializing it.

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})

Now, your dict variable will be a dictionary, a-like class, wherein it’s already sorted way.

Adding elements

We can directly add elements to the dictionary by following the below syntax. Inserting will take log(n) (worst case) time complexity. The default dictionary which we use generally has a time complexity of O(1). But here, since you’re iterating through the dictionary before placing a key-value pair, it is O(n), where n is an existing number of key-value pairs.

dict["a"]="abc"

If you’re familiar with the binary search, the Sorted Dict performs the binary search whenever you’re adding a new key-value pair. This is used to find the correct position of the new key-value pair.

Updating values of the existing keys in Python SortedDict

We can update the values of the keys i.e, dictionaries are mutable in python. It will change the value.

dict["a"]="abc"
dict["a"]=1234

Removing a pair in the dictionary

We can remove the key-value pair by the del function, similar to a normal dictionary.

del dict["abc"]

Iterating over a dictionary

Using a for loop, we can print the keys and values in a Python SortedDict.

for key in dict:
    print("key : ",key ,"value : ",dict[key])

Length of a dictionary

We can get the length of a dictionary using the len keyword. It specifies the number of key-value pairs.

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})
l=len(dict)

Knowing whether a key is present in Dictionary

By using in keyword, we can check whether it is present or not. The return type is bool.

if key in dict:
    print("yes")
else:
    print("no")

Clearing whole sorteddict

We can clear all the key-value pairs at once. It will become empty. The time complexity for clearing is O(n).

dict.clear()

Printing keys in a Python SortedDict

The keys will be printed in a sorted manner. At the same time, the keys are printed randomly in a normal dictionary. You can also use this to iterate over keys.

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})
print(dict.keys())

Printing values in a Python SortedDict

This can be achieved by using the values() function. You can also use this to iterate over values.

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})
print(dict.values())

You can combine zip() with keys() and value() methods to create custom sorting based on keys or values. Then you can easily iterate through it.

Python SortedDict Implementation Example

In the following example, we’ll initialize a dictionary. Then add a key-value pair to the dictionary. Then there are methods to loop through the dictionary and delete the key-value pair.

from sortedcontainers import SortedDict

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})

# printing the dictionary
print('dictionary is: ', dict)
print()
# Adding key value pairs to a dictionary
dict[4] = "xyz"

#Dictionary after adding
print(dict)

print()
# checking whether a key is present or not

if 1 in dict: 
	print('1 is present')
else:
	print('1 is not present')
print()

# iterating over key , value pairs in a dictionary

print('dict elements are: ')

for key in dict:
     print("key : ",key ,"value : ",dict[key])
	
print()

# removing all elements from the dictionary
dict.clear()

print('All elements are cleared: ', dict)

Output –

Python SortedDict Example

It also has many methods, such as copy(), iter(), pop(), index(), and so on.

Python Sorted Dict by Value

If you want to sort your dictionary by value, then the best way is to extract keys and values into a different list and sort the values and keys according to values. There is no use case for creating a SortedDict by value. Instead, you should look for a different way to structure your data.

Python Sorted Dict Bisect

Bisect methods in sorted dict can be used to get index of key element from either left or right. These two methods are bisect_key_left() and bisect_key_right().

dict = SortedDict({1: "abc", 2: "defg", 3:"klmn"})
print(dict.bisect_key_left(-1))
print(dict.bisect_key_right(-1))

Python SortedDict Reverse

For reverse sorted dict, you can call the keys() function and then use [::-1] to reverse the list. Now loop through this list and get your values.

Python SortedDict Performance

Sorted Dict performance is the same as that of normal dict except for the methods to add elements. Whenever you’re adding an element, the dictionary has to go through a binary search to find an appropriate index to add the element.

FAQs

Is python dictionary sortable?

No, the default dict class is not sortable. Instead, you can use the other external modules like SortedDict to create one.

What is the time complexity of SortedDict?

All the time, complexities are similar to a normal dictionary except for the get and add methods. The expected time complexity is O(log(n)).

Is SortedDict part of an in-built module?

No. SortedDict is present in the sortedcontainers external module.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments