Easier List struct?
508 views
Skip to first unread message
Martin Nordström
Mar 22, 2012, 3:09:12 PM3/22/12
to golang-nuts
Hi,
I'm working with a project where I want to be able to add and remove
many objects within a list. Thus the built-in slice in Go would not be
a good approach because the operation of removing an object in the
middle of a slice is too heavy. I've been using the standard List
struct in Go (http://golang.org/pkg/container/list/) but I think it
has several disadvantages compared to list classes in other languages.
The first disadvantage is that it is possible to store any kind of
object, and can thus not be limited to only one type of struct or to
one type of objects which fulfills some specific interface. Hence, you
might append an object to a list that has a type which you did not
intend to have in the list. The other disadvantage is that when you
want to loop over all objects in the list you cannot use the built in
clause range and you also have to explicitly convert the Value of an
Element (in the list) back to its original type before you can use it
as a normal object, which becomes very tedious after just a few times.
Is it possible to somehow use the reflect package in Go to get rid of
the disadvantages that I mentioned here or is the only way out of this
to wait for generic types to be implemented in Go (which will probably
never happen anyway..)?
Thanks in advance!
I'm working with a project where I want to be able to add and remove
many objects within a list. Thus the built-in slice in Go would not be
a good approach because the operation of removing an object in the
middle of a slice is too heavy. I've been using the standard List
struct in Go (http://golang.org/pkg/container/list/) but I think it
has several disadvantages compared to list classes in other languages.
The first disadvantage is that it is possible to store any kind of
object, and can thus not be limited to only one type of struct or to
one type of objects which fulfills some specific interface. Hence, you
might append an object to a list that has a type which you did not
intend to have in the list. The other disadvantage is that when you
want to loop over all objects in the list you cannot use the built in
clause range and you also have to explicitly convert the Value of an
Element (in the list) back to its original type before you can use it
as a normal object, which becomes very tedious after just a few times.
Is it possible to somehow use the reflect package in Go to get rid of
the disadvantages that I mentioned here or is the only way out of this
to wait for generic types to be implemented in Go (which will probably
never happen anyway..)?
Thanks in advance!
Steve McCoy
Mar 22, 2012, 3:56:16 PM3/22/12
to golan...@googlegroups.com
Removing an item from a slice is not necessarily a heavy operation. If you don't care about the element order, you can simply swap the dead element with the last element and then shrink the slice.
Andrew Gerrand
Mar 22, 2012, 4:06:21 PM3/22/12
to Martin Nordström, golang-nuts
You could write a wrapper for container/list that performs type assertions on insertion and retrieval if you need type safety. Of course this might get a little tedious if you want to use many lists with many kinds of value types. On the other hand it would be fairly straightforward to automate the generation of these wrappers.
The slice approach may not be as slow as you think. The built in copy function is very fast. You might try just using slices first and see if you actually have performance issues.
In the absence of generic types, these are your options.
Andrew
Kyle Lemons
Mar 22, 2012, 5:17:21 PM3/22/12
to Andrew Gerrand, Martin Nordström, golang-nuts
2012/3/22 Andrew Gerrand <a...@google.com>
You could write a wrapper for container/list that performs type assertions on insertion and retrieval if you need type safety. Of course this might get a little tedious if you want to use many lists with many kinds of value types. On the other hand it would be fairly straightforward to automate the generation of these wrappers.The slice approach may not be as slow as you think. The built in copy function is very fast. You might try just using slices first and see if you actually have performance issues.In the absence of generic types, these are your options.Andrew
Well, you could always copy container/list and specialize it for your type with sed or something :)
Dave Cheney
Mar 22, 2012, 5:37:25 PM3/22/12
to Kyle Lemons, Andrew Gerrand, Martin Nordström, golang-nuts
gofmt will also do the substitutions for you. If you look in the source history for the various container packages there are hints in the old Makefiles.
Dave
Sonia Keys
Mar 23, 2012, 1:19:25 PM3/23/12
to golan...@googlegroups.com
Slice solutions are almost always best. Steve's solution of moving the last element is best if you can do that. Andrew's solution of using the copy function is best if you need to maintain order. Are your structs really big? You could keep a slice of pointers to them instead of a slice of structs.
If you really want linked list representation, just code it. To my eye,
for p := list; p != nil; p = p.next {
is just as readable as
for i := 0; i < n; i++ {
It's true that you would probably want to code a few functions like insert and delete, but code for these should be simple and efficient.
If you really want linked list representation, just code it. To my eye,
for p := list; p != nil; p = p.next {
is just as readable as
for i := 0; i < n; i++ {
It's true that you would probably want to code a few functions like insert and delete, but code for these should be simple and efficient.
minux
Mar 23, 2012, 3:33:13 PM3/23/12
to Dave Cheney, Kyle Lemons, Andrew Gerrand, Martin Nordström, golang-nuts
On Fri, Mar 23, 2012 at 5:37 AM, Dave Cheney <da...@cheney.net> wrote:
gofmt will also do the substitutions for you. If you look in the source history for the various container packages there are hints in the old Makefiles.
Yeah, gofmt -r is so powerful!
Jan Mercl
Mar 23, 2012, 4:17:26 PM3/23/12
to golan...@googlegroups.com
Made me sentimental ;-)
Reply all
Reply to author
Forward
0 new messages