3 ms·
Every possible way to represent a set is a very thin wrapper around an existing data structure that is commonly implemented. There isn't a generally applicable
by Zergy 13y ago
Every possible way to represent a set is a very thin wrapper around an existing data structure that is commonly implemented. There isn't a generally applicable way to represent a set. All sets are simply existing structures (BitVectors, Linked Lists, BST, or HashTables) with functions like Union and Intersection being tacked on and all have very different performance considerations.
Basically there really isn't a general purpose way to make a set and it’s not a fundamental component of programming, it is a modified HashTables or what ever. So I argue sets don’t actually exist in CS because you can’t represent one as it exists mathematically. You are simply tacking union and intersect to an existing data structure.
- arnehormann 13y agoBut if you do use a map as a wrapper, use map[keytype]struct{} . That way the values don't need any memory at all, struct{} is for free.
- alok-g 13y agoThis would make sense for the case of a set. But does then Go provide (or intend to provide) these other data structures ("BitVectors, Linked Lists, BST, or HashTables")? Does it provide a sorted linked list?
- cmccabe 13y agoA bitvector: []bool Most of the time, you would use map[key]value rather than your own hash table or BST. If you need an implicit linked list, there is one in the standard library: http://golang.org/pkg/container/list/ http://golang.org/pkg/container/list/
- alok-g 13y agoYes, I noted that list container. If I need a sorted list, do I need to do that myself (which is OK though not ideal)? Or again there is some other container that can work possibly with a wrapper around it to emulate a sorted linked list?
- cmccabe 13y agoI think the thing to do is just to write a function to keep stepping through the list until you find the right place to insert, and then just use container/list. Sorry to be "that guy" who questions the question, but sorted lists aren't really a great data structure. As you probably already know, insertion is O(N), where N is the total number of elements in the list. It might be better just to use the GoLRB library, which provides some always-sorted tree structures.
- alok-g 13y agoYou are right. I had a very specific case where I needed a sorted list. I do not recall why anymore.