CODEWITHSUNDEEP
algorithmgopriority-queue
cobie
cobie

Reputation: 7271

Standard library Priority Queue push method

The code snippet below is the library implementation of the push methods for a priority queue. I am wondering why the line with the code a = a[0 : n+1] does not throw an out of bounds errors. 

 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
}

Upvotes: 4

Views: 290

Answers (3)

Yuras
Yuras

Reputation: 13876

Is it an example from container/heap? If yes, then it doesn't throws an exception because capacity is big enough (see how the Push method is used). If you change the example to Push more items then the capacity, then it'll throw.

Upvotes: 1

zzzz
zzzz

Reputation: 91303

Because it works in a specific example program. Here are the important parts from the original/full example source)

const nItem = 10

and

pq := make(PriorityQueue, 0, nItem)

and

for i := 0; i < cap(pq); i++ {
        item := &Item{
                value:    values[i],
                priority: priorities[i],
        }
        heap.Push(&pq, item)
}

Upvotes: 2

jorelli
jorelli

Reputation: 8370

a slice is not an array; it is a view onto an existing array. The slice in question is backed by an array larger than itself. When you define a slice of an existing slice, you're actually slicing the underlying array, but the indexes referenced are relative to the source slice.

That's a mouthful. Let's prove this in the following way: we'll create a slice of zero length, but we'll force the underlying array to be larger. When creating a slice with make, the third parameter will set the size of the underlying array. The expression make([]int, 0, 2) will allocate an array of size 2, but it evaluates to a size-zero slice. 

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])
}

see here. You can use the cap keyword to reference the size of the array that backs a given slice.

The specific code that you asked about loops over cap(pq) in the calling context (container/heap/example_test.go line 90). If you modify the code at the call site and attempt to push another item into the queue, it will panic like you expect. I ... probably wouldn't suggest writing code like this. Although the code in the standard library executes, I would be very sour if I found that in my codebase. It's generally safer to use the append keyword.

Upvotes: 3

Related Questions