Implementing containers

[Oleg Eterevsky]

Hi!

I've been playing around with Go and came to a point where I needed to
implement some general containers like stack and queue. Do I
understand correctly that in absence of generics, the only way to do
it is to put interface{} values in them? If that is the case, will it
mean that it's impossible to make them typesafe? What about
performance: how much worse is a container of interface{} than a
container specifically implemented to handle say uint32?

Here's the sample of code that I've written. It seems to work, but is
this the intended way of implementing a container?

type Stack struct {
elements []interface{}
}

func NewStack() *Stack {
stack := new(Stack)
stack.elements = make([]interface{}, 0)
return stack
}

func (s *Stack) Push(v interface{}) {
if len(s.elements) >= cap(s.elements) {
newElements := make([]interface{}, len(s.elements), 2*cap(s.elements) + 1)
copy(newElements, s.elements)
s.elements = newElements
}

s.elements = append(s.elements, v)
}

func (s *Stack) Pop() (interface{}, bool) {
if len(s.elements) == 0 {
return nil, false
}

value := s.elements[len(s.elements) - 1]
s.elements = s.elements[:len(s.elements) - 1]
return value, true
}

--
Thanks,
Oleg Eterevsky

[roger peppe]

to be honest, if i need a stack, i usually implement it for the type
in question, or inline, as it's only a very small number of lines:

type stack []T
func (s *stack) push(t T) {
*s = append(*s, t)
}
func (s *stack) pop() T {
n := len(*s)
t := (*s)[n-1]
*s = (*s)[:n-1]
return t
}

an alternative is to use container/list.
the same applies to queues - container/list works well for a queue;
i'd usually just inline the below implementation.

type queue list.List

func newQueue() *queue {
return (*queue)(list.New())
}
func (q *queue) push(t T) {
l := (*list.List)(q)
l.PushBack(t)
}
func (q *queue) pop() T {
l := (*list.List)(q)
return l.Remove(l.Front()).(T)
}
func (q *queue) len() int {
return (*list.List)(q).Len()
}

yes, interface{} has an overhead, but
it's not too bad for most purposes. if you find it's a bottleneck
in a particular case, it's usually ok to copy
the code and specialise the types.

[chl]

Another alternative would be to implement a more specific stack on a more general stack that uses interface{}

Eg:

type IntStack struct {

     s Stack

}

func (i IntStack) Push (n int) {

     i.s.Push(n)

}

func (i IntStack) Pop () int {

     v := i.s.Pop()

     if v == nil {

          return 0

     }

     return v.(int)

}

or another alternative would be to use 2 functions that do the type checking.

func IntPush(s Stack, n int) {

        s.Push(n)

}

func IntPop(s Stack) (n int) {

        v := s.Pop()

        if v != nil {

              n = v.(int)