2

In the default container/heap package in go, there's an example for implementing a priority queue.

While looking at the sample code, it uses a slice []*Item, and implements the heap.Interface.

My trouble is with the following bit. Why are some functions declared with the priority queue as a slice and sometimes as a pointer to slice ?:

func (pq PriorityQueue) Swap(i, j int) {...}
// vs
func (pq *PriorityQueue) Push(x interface{}) {...}

Why isn't it always (pq PriorityQueue) ? On this other StackOverflow thread about pointer to slices, the docs say that slices are refence types, so why use pointers on them ? I'm having trouble with the fact that the official doc says something then mixes both without explaining the point of adding a pointer.

Thanks for your insights !

EDIT: Here's an example:

// original sample code from the docs:
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

// is this the same (removed pointers to slice) ?
func (pq PriorityQueue) Push(x interface{}) {
    n := len(pq)
    item := x.(*Item)
    item.index = n
    pq = append(pq, item)
}

If both functions are the same, why use a pointer now ?

Community
  • 1
  • 1
achedeuzot
  • 4,164
  • 4
  • 41
  • 56

1 Answers1

6

This article on the Go blog explains why.

From the section Passing slices to functions:

It's important to understand that even though a slice contains a pointer, it is itself a value. Under the covers, it is a struct value holding a pointer and a length. It is not a pointer to a struct.

As a result you either need to pass a pointer or you need to return the slice as a value if you want to modify it with append.

If you just want to modify the contents of a slice you can simply pass the slice by value:

Even though the slice header is passed by value, the header includes a pointer to elements of an array, so both the original slice header and the copy of the header passed to the function describe the same array. Therefore, when the function returns, the modified elements can be seen through the original slice variable.

With append you are modifying the slice header. And

Thus if we want to write a function that modifies the header, we must return it as a result parameter

Or:

Another way to have a function modify the slice header is to pass a pointer to it.

IamNaN
  • 6,654
  • 5
  • 31
  • 47
  • Thanks for the information but I still don't understand why they changed the function prototypes in the middle of the sample code. I added an example at the bottom of my question to illustrate this. – achedeuzot May 07 '15 at 12:21
  • Swap and Push do different things. Swap only changes the content of the slice. Push adds to the slice and thus changes the length of the slice, i.e. the slice header. Because of that you need a pointer (or return the modified copy). Your second example will not work because append will modify a copy of the slice header. – IamNaN May 07 '15 at 12:27
  • If you look at the heap example it says right in the comments: `// Push and Pop use pointer receivers because they modify the slice's length, not just its contents.` – IamNaN May 07 '15 at 12:28
  • Oh right, I didn't expand the `IntHeap` example ! Also I found [this useful SO post about a strange `Pop method has no pointer receiver` error](http://stackoverflow.com/questions/22543025/priority-queue-and-heap). – achedeuzot May 07 '15 at 12:37