如何为sortedcontainers.SortedDict设置排序谓词，实现按值有序并解决添加报错？

Hey there! Let’s break down your two SortedDict questions from the sortedcontainers library and fix that frustrating KeyError you ran into.

1. How to Set a Sort Predicate for SortedDict #

The SortedDict constructor lets you pass a key function as its first argument—this defines how the keys are sorted. The function takes a key from the dict and returns a value that’s used to determine the sort order.

Here’s the catch: this key function needs to work for any key you add later, not just the initial ones. Your KeyError happened because your lambda was pulling values from the external d dictionary instead of the SortedDict itself. When you added the new key 'd', it didn’t exist in d, so the lambda threw an error.

Quick Fix for Your Original KeyError #

If you want to stick with your initial approach (sorting by the datetime value linked to each key), you can’t rely on an external dict. For dynamic additions, a better approach is the subclass we’ll cover next, but if you just need to initialize with existing keys, pre-add all keys to the external dict first:

import datetime
from sortedcontainers import SortedDict

# Pre-add all keys you'll use to the external dict first
d = {
    'a': {'datetime': datetime.datetime.now()},
    'b': {'datetime': datetime.datetime.now()},
    'z': {'datetime': datetime.datetime.now()},
    'c': {'datetime': datetime.datetime.now()},
    'd': {'datetime': None}  # Placeholder for the key you'll add later
}

# Now the lambda can find all keys in d
sd = SortedDict(lambda key: d[key]['datetime'], d)
# Update the placeholder value
sd['d'] = {'datetime': datetime.datetime.now()}
print(sd)  # No KeyError!

2. Can SortedDict Maintain Order Based on Values (Not Keys)? #

By default, SortedDict only sorts and maintains order based on keys (using the key function if provided). To keep it ordered by values at all times—even when adding new entries or updating values—you need to extend its functionality, since:

• The built-in key function only operates on keys, not values.
• SortedDict doesn’t automatically re-sort when values change.

Solution: Subclass SortedDict for Value-Based Sorting #

A clean, maintainable way to do this is to create a subclass that overrides methods that modify the dict, so it re-sorts whenever values are added, removed, or updated. Here’s a working example tailored to your datetime use case:

from sortedcontainers import SortedDict
import datetime

class ValueSortedDict(SortedDict):
    def __init__(self, *args, **kwargs):
        # Initialize like a regular SortedDict
        super().__init__(*args, **kwargs)
        # Sort the initial keys based on their datetime values
        self._reorder_by_values()
    
    def _reorder_by_values(self):
        # Recreate the sorted keys list using the current values' datetime
        sorted_keys = sorted(self.keys(), key=lambda k: self[k]['datetime'])
        self._keys = sorted_keys
    
    def __setitem__(self, key, value):
        # First set the value like normal
        super().__setitem__(key, value)
        # Then re-sort the keys
        self._reorder_by_values()
    
    def pop(self, key, default=None):
        # Remove the key first
        result = super().pop(key, default)
        # If we actually removed something, re-sort
        if result is not default:
            self._reorder_by_values()
        return result

# How to use it
d = {
    'a': {'datetime': datetime.datetime(2024, 1, 1)},
    'b': {'datetime': datetime.datetime(2024, 1, 3)},
    'z': {'datetime': datetime.datetime(2024, 1, 2)}
}

sd = ValueSortedDict(d)
print(sd)  # Ordered by datetime: a, z, b

# Add a new entry—automatically re-sorts
sd['d'] = {'datetime': datetime.datetime(2024, 1, 0)}
print(sd)  # Now d is first, followed by a, z, b

# If you modify a value in-place, call _reorder_by_values() manually
sd['b']['datetime'] = datetime.datetime(2023, 12, 31)
sd._reorder_by_values()
print(sd)  # Now b is first, then d, a, z

This subclass keeps the dict ordered by values whenever you add or remove entries. For in-place value changes (like updating the datetime directly), you’ll need to call _reorder_by_values() manually since the subclass can’t detect those changes automatically.

内容的提问来源于stack exchange，提问作者NIkita Koren