Swift 有序集 [英] Swift Ordered Set

问题描述

Swift 是否有 有序 集合类型?如果没有，如果我想使用一个，我有哪些选择?

标准库的 Set 是无序的，如文档中所述:

<块引用>

数组是值的有序集合.集合是唯一值的无序集合.字典是键值关联的无序集合.

然而，许多适用于实现有序集(和字典)的数据结构是已知的，特别是 balanced二叉树，例如红黑树.>

作为一个例子，c++ 的 stl 有 有序集 和映射，并允许使用下限和上限对它们进行范围查询.

我知道可以将集合的成员排序到数组中，但我追求的是具有 O(log(n)) 插入、删除和查询的数据结构.

解决方案

Swift 没有原生有序集类型.如果您使用 Foundation，则可以在 Swift 中使用 NSOrderedSet.如果没有，您有机会编写自己的有序集数据结构.

更新:Swift Package Manager 包括一个可能有用的 OrderedSet 实现.它包装了一个数组和一个集合，并管理访问以获得有序的集合行为.

更新 #2:Apple 的 Swift Collections 存储库包含一个有序集实现.

Does Swift have an ordered set type? And if not, what are my options if I want to use one?

The standard library's Set is unordered, as is made clear in the documentation:

Arrays are ordered collections of values. Sets are unordered collections of unique values. Dictionaries are unordered collections of key-value associations.

However, many data structures suitable for implementing ordered sets (and dictionaries) are known, in particular balanced binary trees such as Red-Black trees.

As an example of this, c++'s stl has ordered sets and maps, and allows range queries on them using lower and upper bounds.

I know that a set's members can be sorted in to an array, but I am after a data structure with O(log(n)) insertion, removal and query.

解决方案

Swift does not have a native ordered set type. If you use Foundation, you can use NSOrderedSet in Swift. If not, you have the opportunity to write your own ordered set data structure.

Update: Swift Package Manager includes an OrderedSet implementation that may be useful. It wraps both an array and a set and manages access to get ordered set behavior.

Update #2: Apple's Swift Collections repository contains an ordered set implementation.

这篇关于Swift 有序集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！