Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
600 views
in Technique[技术] by (71.8m points)

iterator - In Go is it possible to iterate over a custom type?

I have a custom type which internally has a slice of data.

Is it possible, by implementing some functions or an interface that the range operator needs, to iterate (using range) over my custom type?

question from:https://stackoverflow.com/questions/35810674/in-go-is-it-possible-to-iterate-over-a-custom-type

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The short answer is no.

The long answer is still no, but it's possible to hack it in a way that it sort of works. But to be clear, this is most certainly a hack.

There are a few ways you can do it, but the common theme between them is that you want to somehow transform your data into a type that Go is capable of ranging over.

Approach 1: Slices

Since you mentioned that you have a slice internally, this may be easiest for your use case. The idea is simple: your type should have an Iterate() method (or similar) whose return value is a slice of the appropriate type. When called, a new slice is created containing all of the elements of the data structure in whatever order you'd like them to be iterated over. So, for example:

func (m *MyType) Iterate() []MyElementType { ... }

mm := NewMyType()
for i, v := range mm.Iterate() {
    ...
}

There are a few concerns here. First, allocation - unless you want to expose references to internal data (which, in general, you probably don't), you have to make a new slice and copy all of the elements over. From a big-O standpoint, this isn't that bad (you're doing a linear amount of work iterating over everything anyway), but for practical purposes, it may matter.

Additionally, this doesn't handle iterating over mutating data. This is probably not an issue most of the time, but if you really want to support concurrent updates and certain types of iteration semantics, you might care.

Approach 2: Channels

Channels are also something that can be ranged over in Go. The idea is to have your Iterate() method spawn a goroutine that will iterate over the elements in your data structure, and write them to a channel. Then, when the iteration is done, the channel can be closed, which will cause the loop to finish. For example:

func (m *MyType) Iterate() <-chan MyElementType {
    c := make(chan MyElementType)
    go func() {
        for _, v := range m.elements {
            c <- v
        }
        close(c)
    }()
    return c
}

mm := NewMyType()
for v := range mm.Iterate() {
    ...
}

There are two advantages of this method over the slice method: first, you don't have to allocate a linear amount of memory (although you may want to make your channel have a bit of a buffer for performance reasons), and second, you can have your iterator play nicely with concurrent updates if you're into that sort of thing.

The big downside of this approach is that, if you're not careful, you can leak goroutines. The only way around this is to make your channel have a buffer deep enough to hold all of the elements in your data structure so that the goroutine can fill it and then return even if no elements are read from the channel (and the channel can then later be garbage collected). The problem here is that, a) you're now back to linear allocation and, b) you have to know up-front how many elements you're going to write, which sort of puts a stop to the whole concurrent-updates thing.

The moral of the story is that channels are cute for iterating, but you probably don't want to actually use them.

Approach 3: Internal Iterators

Credit to hobbs for getting to this before me, but I'll cover it here for completeness (and because I want to say a bit more about it).

The idea here is to create an iterator object of sorts (or to just have your object only support one iterator at a time, and iterate on it directly), just like you would in languages that support this more directly. What you do, then, is call a Next() method which, a) advances the iterator to the next element and, b) returns a boolean indicating whether or not there's anything left. Then you need a separate Get() method to actually get the value of the current element. The usage of this doesn't actually use the range keyword, but it looks pretty natural nonetheless:

mm := MyNewType()
for mm.Next() {
    v := mm.Get()
    ...
}

There are a few advantages of this technique over the previous two. First, it doesn't involve allocating memory up-front. Second, it supports errors very naturally. While it's not really an iterator, this is exactly what bufio.Scanner does. Basically the idea is to have an Error() method which you call after iteration is complete to see whether iteration terminated because it was done, or because an error was encountered midway through. For purely in-memory data structures this may not matter, but for ones that involve IO (e.g., walking a filesystem tree, iterating over database query results, etc), it's really nice. So, to complete the code snippet above:

mm := MyNewType()
for mm.Next() {
    v := mm.Get()
    ...
}
if err := mm.Error(); err != nil {
    ...
}

Conclusion

Go doesn't support ranging over arbitrary data structures - or custom iterators - but you can hack it. If you have to do this in production code, the third approach is 100% the way to go, as it is both the cleanest and the least of a hack (after all, the standard library includes this pattern).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...