保持特定状态的数组元素列表

Question

我有一长串元素。这是一个嵌入式平台，每个周期我都需要对所有设置了标志的元素进行操作。

只有少数元素在任何时候设置了标志。由于性能原因，我无法 运行 遍历整个数组。

我意识到一个解决方案可能是构建一个列表，其中包含设置了标志的元素的数组索引，并且 运行 通过该列表而不是整个数组。每当标志为 set/reset.

时，此列表就会更新

我猜这是一个古老的 "solved" 问题，但我缺少正确描述它的词汇。这个问题的最佳实践是什么，它叫什么？

谢谢

Answer 1

您要找的词是一组。您将标记的那些保留在某种子组（您称之为列表）中是正确的，但是列表是有序的。您不需要这种排序功能来存储一堆标记的元素；你想要一个集合，它是数组中所有元素的子集。

不对它们进行排序会给您带来性能优势，特别是在删除时，因为您不必移动列表中您删除的元素之后的所有元素。同样在随机位置访问上，如果您使用 HashSet，您将拥有恒定的时间。在某种程度上 "bad" 方面，遍历集合对象通常不如列表直观，因此您需要使用 Iterator 对象。