具有O(1)查找和O(1)切片的F#数组

Question

我需要一个支持的类似数组的数据结构

a.[i]

在时间O(1)和

a.[i..j]

也及时O(1).

O(1)更新不是必需的.实际上,我需要的是一个具有就地切片或子阵列概念的常量数组.

我当然可以构建这样的东西Array,但如果我可以使用已存在的东西,我会更高兴吗？

Answer 1

.NET标准库具有ArraySegment<'T>用于此目的的类型.不幸的是,没有方法Item,并GetSlice允许您使用.[x],并.[x..y]分别语法.但您可以使用扩充添加它们:

type System.ArraySegment<'T> with

    member this.Item(x) =
        if x < 0 || x >= this.Count then
            raise (System.IndexOutOfRangeException("Index was outside the bounds of the array segment."))
        this.Array.[x + this.Offset]

    member this.GetSlice(start: int option, finish : int option) =
        let start = defaultArg start 0
        let finish = defaultArg finish (this.Count - 1)
        if start < 0 || finish >= this.Count then
            raise (System.IndexOutOfRangeException("Index was outside the bounds of the array segment."))
        new ArraySegment<'T>(this.Array, this.Offset + start, finish - start + 1)