4

下面的代码片段是优先级队列的推送方法的库实现。我想知道为什么代码行a = a[0 : n+1]不会引发越界错误。

 func (pq *PriorityQueue) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    // To simplify indexing expressions in these methods, we save a copy of the
    // slice object. We could instead write (*pq)[i].
    a := *pq
    n := len(a)
    a = a[0 : n+1]
    item := x.(*Item)
    item.index = n
    a[n] = item
    *pq = a
}
4

4 回答 4

3

切片不是数组；它是现有阵列的视图。有问题的切片由一个比自身大的数组支持。当您定义现有切片的切片时，您实际上是在对底层数组进行切片，但引用的索引是相对于源切片的。

那是一口。让我们用以下方式证明这一点：我们将创建一个长度为零的切片，但我们将强制底层数组更大。使用 创建切片时make，第三个参数将设置底层数组的大小。该表达式make([]int, 0, 2)将分配一个大小为 2 的数组，但它的计算结果为大小为零的切片。

package main

import ("fmt")

func main() {
    // create a zero-width slice over an initial array of size 2
    a := make([]int, 0, 2)
    fmt.Println(a)

    // expand the slice.  Since we're not beyond the size of the initial
    // array, this isn't out of bounds.
    a = a[0:len(a)+1]

    a[0] = 1
    fmt.Println(a)
    fmt.Println(a[0:len(a)+1])
}

看这里。您可以使用cap关键字来引用支持给定切片的数组的大小。

您询问的特定代码cap(pq)在调用上下文中循环（container/heap/example_test.go 第 90 行）。如果您在调用站点修改代码并尝试将另一个项目推入队列，它会像您预期的那样恐慌。我......可能不会建议编写这样的代码。虽然标准库中的代码执行，但如果我在我的代码库中发现它，我会很生气。append使用关键字通常更安全。

于 2013-02-03T16:55:16.390 回答
2

因为它适用于特定的示例程序。以下是原始/完整示例源中的重要部分）

const nItem = 10

和

pq := make(PriorityQueue, 0, nItem)

和

for i := 0; i < cap(pq); i++ {
        item := &Item{
                value:    values[i],
                priority: priorities[i],
        }
        heap.Push(&pq, item)
}
于 2013-02-03T16:56:42.200 回答
1

它是容器/堆的一个例子吗？如果是，那么它不会抛出异常，因为容量足够大（请参阅如何使用该Push方法）。如果您将示例更改为Push比容量更多的项目，那么它会抛出。

于 2013-02-03T16:57:00.710 回答
0

一般情况下是这样；示例中没有container/heap。这是我前段时间已经给你的一般修复。

func (pq *PriorityQueue) Push(x interface{}) {
    a := *pq
    n := len(a)
    item := x.(*Item)
    item.index = n
    a = append(a, item)
    *pq = a
}

Golang 解决 Project Euler 问题 #81

于 2013-02-03T17:05:53.030 回答