在使用 sortedcontainers.sortedset 时，若元素的排序键（由 key 参数定义）在元素仍存在于集合中时被修改，将导致集合内部结构损坏，进而引发 discard 或其他操作失败。正确的做法是先将元素从 sortedset 中移除，修改其键值相关的属性，然后再重新添加回集合，以确保集合的有序性和内部一致性。
Python SortedSet 概述
sortedcontainers.SortedSet 是 Python 中一个非常有用的数据结构，它提供了一个保持有序的集合，支持快速的添加、删除和查找操作。与内置的 set 不同，SortedSet 中的元素总是按其值或通过自定义 key 函数定义的键进行排序。这使得它在需要维护有序唯一元素集合的场景中表现出色，例如查找最高/最低评分的食物、管理优先级队列等。
键不变性原则：SortedSet 的核心要求
SortedSet 的内部实现依赖于元素的哈希值和比较结果来维护其有序性。因此，它对存储的元素有一个关键的要求：元素的哈希值和总排序（即其键）在元素存储于 SortedSet 期间必须保持不变。 官方文档对此有明确警告：
Sorted set values must be hashable and comparable. The hash and total ordering of values must not change while they are stored in the sorted set.
这意味着，如果你使用 key 函数来定义元素的排序方式，那么 key 函数所依赖的任何元素属性在元素存在于 SortedSet 期间都不能被修改。一旦这些属性改变，SortedSet 就无法正确地找到该元素或维护其在集合中的正确位置。
错误示范：在集合内修改键相关属性
考虑一个食物评分系统，我们希望根据评分（降序）和食物名称（升序）来获取最高评分的食物。SortedSet 通过 key=lambda x: (-self.food_map[x][1], self.food_map[x][2]) 定义了排序规则，其中 self.food_map[x][1] 是评分，self.food_map[x][2] 是食物名称。
立即学习“Python免费学习笔记（深入）”；
当尝试修改食物评分时，一个常见的错误是先修改评分，然后尝试从 SortedSet 中移除该元素，再重新添加：
import collections
from sortedcontainers import SortedSet
from typing import List
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.food_map = {} # Food: [cuisine, rating, food]
self.cuisines_map = collections.defaultdict(SortedSet) # Cuisine: SortedSet(Food)
for index in range(len(foods)):
food = foods[index]
cuisine = cuisines[index]
rating = ratings[index]
self.food_map[food] = [cuisine, rating, food]
# 初始化 SortedSet 时定义排序键
if cuisine not in self.cuisines_map:
self.cuisines_map[cuisine] = SortedSet(key=lambda x: (-self.food_map[x][1], self.food_map[x][2]))
self.cuisines_map[cuisine].add(food)
def changeRating_problematic(self, food: str, newRating: int) -> None:
cuisine = self.food_map[food][0]
# 错误操作：先修改评分，再尝试移除
self.food_map[food][1] = newRating # 此时 'food' 的键已经改变
self.cuisines_map[cuisine].discard(food) # 尝试移除时，SortedSet无法找到旧键对应的元素
self.cuisines_map[cuisine].add(food)
def highestRated(self, cuisine: str) -> str:
return self.cuisines_map[cuisine][0] if self.cuisines_map[cuisine] else ""
# 示例：
obj = FoodRatings(["kimchi","miso","sushi","moussaka","ramen","bulgogi"],
["korean","japanese","japanese","greek","japanese","korean"],
[9,12,8,15,14,7])
# obj.changeRating_problematic("sushi", 16) # 这将导致错误，因为 'sushi' 的键在 SortedSet 内部已经“失效”在 changeRating_problematic 方法中，当 self.food_map[food][1] = newRating 执行后，food 这个字符串在 SortedSet 中对应的排序键 ((-self.food_map[food][1], self.food_map[food][2])) 已经发生了变化。此时，SortedSet 内部仍然尝试使用旧的键值来定位和移除 food，但由于键已改变，导致查找失败，从而引发 KeyError 或其他内部不一致的错误。
正确实践：先移除，后修改，再添加
解决这个问题的关键在于遵循 SortedSet 的键不变性原则。如果需要修改影响元素排序键的属性，必须先将元素从 SortedSet 中移除，然后进行修改，最后再将修改后的元素重新添加回 SortedSet。这样，SortedSet 就能以新的键值正确地重新定位和排序元素。
以下是 changeRating 方法的正确实现：
import collections
from sortedcontainers import SortedSet
from typing import List
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.food_map = {} # Food: [cuisine, rating, food]
# 使用 defaultdict 简化初始化逻辑
self.cuisines_map = collections.defaultdict(
lambda: SortedSet(key=lambda x: (-self.food_map[x][1], self.food_map[x][2]))
)
for index in range(len(foods)):
food = foods[index]
cuisine = cuisines[index]
rating = ratings[index]
self.food_map[food] = [cuisine, rating, food]
self.cuisines_map[cuisine].add(food)
def changeRating(self, food: str, newRating: int) -> None:
cuisine = self.food_map[food][0]
# 正确操作：先从 SortedSet 中移除元素
self.cuisines_map[cuisine].discard(food)
# 然后修改影响排序键的属性
self.food_map[food][1] = newRating
# 最后将修改后的元素重新添加回 SortedSet
self.cuisines_map[cuisine].add(food)
def highestRated(self, cuisine: str) -> str:
# 确保集合非空，避免索引错误
return self.cuisines_map[cuisine][0] if self.cuisines_map[cuisine] else ""
# 示例用法：
obj = FoodRatings(["kimchi","miso","sushi","moussaka","ramen","bulgogi"],
["korean","japanese","japanese","greek","japanese","korean"],
[9,12,8,15,14,7])
print(f"Initial highest rated Japanese food: {obj.highestRated('japanese')}") # 预期: miso (12)
obj.changeRating("sushi", 16)
print(f"After sushi rating changed to 16, highest rated Japanese food: {obj.highestRated('japanese')}") # 预期: sushi (16)
obj.changeRating("miso", 5)
print(f"After miso rating changed to 5, highest rated Japanese food: {obj.highestRated('japanese')}") # 预期: sushi (16)
obj.changeRating("ramen", 18)
print(f"After ramen rating changed to 18, highest rated Japanese food: {obj.highestRated('japanese')}") # 预期: ramen (18)在这个修正后的 changeRating 方法中，我们首先调用 self.cuisines_map[cuisine].discard(food) 将 food 从 SortedSet 中移除。此时，SortedSet 仍然能够使用 food 当前的（旧的）键值来定位并删除它。移除成功后，我们再安全地修改 self.food_map[food][1] 为 newRating。最后，通过 self.cuisines_map[cuisine].add(food) 将 food 重新添加回 SortedSet。此时，SortedSet 会根据 food 更新后的评分和名称重新计算其排序键，并将其放置在正确的位置。
注意事项与总结
- 键不变性是核心： 任何依赖元素哈希或比较结果进行内部管理的 Python 数据结构（如 set, dict, SortedSet 等）都要求其元素的键在存储期间保持不变。
-
修改策略： 当需要修改元素的键相关属性时，标准做法是：
- 将元素从集合中移除。
- 修改元素的属性。
- 将修改后的元素重新添加回集合。
- 性能考量： 移除和重新添加操作会带来一定的性能开销，尤其是在大型集合中。但对于大多数应用场景，这种开销通常是可接受的，并且是维护数据结构完整性的必要步骤。
- 查阅文档： 在使用任何第三方库或复杂数据结构时，务必查阅其官方文档，了解其对元素的要求和操作限制，这能有效避免潜在的错误。
通过理解并遵循 SortedSet 的键不变性原则，我们可以更健壮、更高效地利用这个强大的数据结构来构建复杂的应用。
