Does Python have an ordered set?

python

ordered-set

data-structure

collections

byAnton Shumikhin·Nov 18, 2024

An ordered set is achievable through Python's collections.OrderedDict. It acts as a set while retaining insertion order. For a more specialized approach, create an OrderedSet class that employs OrderedDict behind the scenes:

from collections import OrderedDict

class OrderedSet(OrderedDict):
    # Look Ma, no duplicates!🙅‍♂️
    def add(self, key):
        self[key] = None

my_ordered_set = OrderedSet('abracadabra')
# Now you see 'em, now you don't 💨
print(list(my_ordered_set))  # ['a', 'b', 'r', 'c', 'd']

With this OrderedSet class, duplication is a thing of the past while maintaining insertion order. Call the add() method to introduce new items while keeping the order intact.

Python's hidden gem: Ordered sets

Emulating ordered sets with dictionaries

From Python 3.7+, dict remembers insertion order as part of the language specification. Thus, you can use dict itself to act as an ordered set:

# I came, I saw, I ordered 🤓
my_ordered_set = dict.fromkeys('abracadabra')
print(list(my_ordered_set))  # ['a', 'b', 'r', 'c', 'd']

In this example, dict.fromkeys() creates a new dictionary with keys from the given iterable, both preserving order and eliminating duplicates. The keys() method then allows you to grasp the keys preserving their insertion order.

Ordering courtesy of third-party libraries

Several third-party libraries offer more traditional set interfaces yet continue to preserve the order of items:

ordered-set: A handy PyPI library delivering a mutable set that never forgets its order.
collections-extended: An alternate PyPI package offering sets havings dual traits - sequence behavior and set behavior, along with remembering the sequence of insertion.
boltons: This library offers IndexedSet, which not only maintains the insertion order but also has a knack for indexing.

To install boltons, just run the magic command:

pip install boltons

IndexedSet from boltons stands out by supporting index-based retrieval, a feature missing in standard sets or the solutions based on OrderedDict.

Balancing trade-offs: Performance and functionality

Operation Order: Set operations such as union, intersection, and difference can sway the order of elements. The solutions offered by OrderedDict and third-party libraries guard this order.
Big O Notation: dict and OrderedDict grant O(1) complexity for lookup, insertion, and deletion. However, some operations in the third-party libraries may have higher complexity.
Insert Quarter for More Space: An OrderedDict often needs more memory than a standard dict due to maintaining the order of inserted keys.

Big Brain Time: Advanced ordered set use-cases

Building a feature-packed OrderedSet

If you have a use-case, where the standard solutions just don't cut it, it might be time to build your own:

from collections import OrderedDict

class OrderedSet(OrderedDict):
    # add more methods as per requirements here
    def add(self, key):
        self[key] = None

    def discard(self, key):
        # You shall not pass... if nonexistent! 🧙
        self.pop(key, None)

The right tool for the job

For lighter tasks: OrderedDict provides everything you need for creating ordered sets. It keeps your external dependencies to a minimum.
For feature-rich needs: Lean on third-party libraries if your use-case demands advanced set operations or indexed access.
Mindful of memory: Memory usage varies across implementations, so the right choice depends on the memory constraints of your specific application.