Map ordering (best way to enforce)

[josvazg]

In Go 1 there is definitely no default order in traversing a map.

When you need some order (alphabetical, LIFO, FIFO, etc) on a map, or you just need the ordering to be consistent, 

What is the Go way to do it?

I only imagine you coud do something like:

type orderedMap {

 themap map[ktype]etype

 theorder []ktype

}

So that there is a slice to keep a ordered list of keys (or a linked list) but I don't find it elegant.

[Peter Bourgon]

Go maps are by definition unordered. If you want ordered key-value
semantics, I recommend a package like https://github.com/petar/GoLLRB.
Alternatively, your imagined code is fine for many use-cases, IMO.

[Russ Cox]

On Wed, Mar 28, 2012 at 15:32, josvazg <jos...@gmail.com> wrote:
> When you need some order (alphabetical, LIFO, FIFO, etc) on a map, or you
> just need the ordering to be consistent,

alphabetical: pull the keys or key-value pairs into a slice + sort.
LIFO: use a slice
FIFO: use a channel

[Kelvin Lau]

What a pitty.

Seems Go doesn't have balanced binary tree like std::set in C++.

[Jan Mercl]

On Sun, Jan 27, 2013 at 11:16 AM, Kelvin Lau <kelvin...@gmail.com> wrote:
> What a pitty.
> Seems Go doesn't have balanced binary tree like std::set in C++.

https://github.com/petar/GoLLRB
https://bitbucket.org/santucco/btree
https://code.google.com/p/go-avltree/
https://github.com/toberndo/go-stree
https://github.com/yasushi-saito/rbtree
https://github.com/saschpe/tribool
https://github.com/dhconnelly/rtreego
...

Statuses of the project in the above sample are not known to me. At
minimum they should compile with Go1.

-j

[Dan Kortschak]

and:

https://code.google.com/p/biogo.llrb
https://code.google.com/p/biogo.interval

[Dan Kortschak]

also (forgot):

http://code.google.com/p/biogo.kdtree

[John Asmuth]

What others have suggested in their replies is that with Go, it doesn't *really* matter if it's in the std lib or not. "go get" makes it so trivial to use an install 3rd party packages (your project can import, eg, "github.com/petar/gollrb/llrb" and if someone "go get"s your project, it will also fetch the llrb package) that the motivation is nearly gone.

[Nate Finch]

That's the great thing about Go. There's never a matter of what "Go" has. There's always someone out there who has written a package to do it, and it's trivial to get it, and adding it to your project doesn't cost anyone else any problems since they get it automatically with your project.

--
 
 

[theanal...@gmail.com]

I love go get.  It really is trivial to bring in 3rd party libs, their dependencies, etc.  Makes me feel a little bit spoiled as a programmer.

Of course, I'd be lying if I said that I trust all Go programmers (e.g., author of package X on github) as much as, say, Rob Pike.  Maybe this isn't entirely rational, but when I see something in the standard library it makes me feel confident, like it's been quite thoroughly tested and isn't going to cause me a heart attack when we deploy.  This helps me sleep at nights when I'm putting code into production.  On the other hand, when I use a 3rd party package, there's always a nagging feeling in the back of my mind that some critical bug is going to pop out after I've deployed.  There's something to be said for this peace of mind, whether or not it is warranted.  (And I honestly believe for the large part, the peace of mind that comes from using the standard library IS warranted.)

Not to mention you're at the mercy of the 3rd party licensing scheme and possibly of any OTHER 3rd party libs that they pulled into their project.  When you use something that's part of the Go standard library, you don't end up with the additional overhead of making sure all of your licenses are compatible, which I found out recently can be a real headache for moderately sized projects.

At my last job, everything we did was in house.  There was no chance that ANY of the code we wrote would EVER be distributed outside the company.  Since we weren't redistributing, this generally meant that we could use any random 3P library we wanted without worrying about license incompatibilities.

Conversely, at my current job, the expectation is that ALL of the software we write will be distributed.  I have to approach the question of "Which 3P library will I use?" much more carefully now to avoid painting myself into a corner with license requirements later on.

[Jesse McNelis]

On Sun, Jul 28, 2013 at 3:51 AM, <theanal...@gmail.com> wrote:

Of course, I'd be lying if I said that I trust all Go programmers (e.g., author of package X on github) as much as, say, Rob Pike. 

You shouldn't just trust third party packages. You should read the code.

 

Maybe this isn't entirely rational, but when I see something in the standard library it makes me feel confident, like it's been quite thoroughly tested and isn't going to cause me a heart attack when we deploy.  This helps me sleep at nights when I'm putting code into production. 

This becomes less and less true the larger the standard library is. See Ruby's standard library as an example. It's large and largely non-idiomatic, Python is similar. The size of the standard library has to match the resources allocated to maintain it for the life of the language.

 

On the other hand, when I use a 3rd party package, there's always a nagging feeling in the back of my mind that some critical bug is going to pop out after I've deployed.  There's something to be said for this peace of mind, whether or not it is warranted.  (And I honestly believe for the large part, the peace of mind that comes from using the standard library IS warranted.)

Use code from people you trust. If you have a critical dependency on a certain project then it's a good idea to get involved in the project and get to know the people maintaining it.

--
=====================
http://jessta.id.au

[Jan Mercl]

On Sun, Jan 27, 2013 at 11:23 AM, Jan Mercl <0xj...@gmail.com> wrote:
> On Sun, Jan 27, 2013 at 11:16 AM, Kelvin Lau <kelvin...@gmail.com> wrote:
>> What a pitty.
>> Seems Go doesn't have balanced binary tree like std::set in C++.
>
> https://github.com/petar/GoLLRB
> https://bitbucket.org/santucco/btree
> https://code.google.com/p/go-avltree/
> https://github.com/toberndo/go-stree
> https://github.com/yasushi-saito/rbtree
> https://github.com/saschpe/tribool
> https://github.com/dhconnelly/rtreego
> ...

... and now also a generic B+Tree: http://godoc.org/github.com/cznic/b

-j

[riccard...@gmail.com]

While I understand there's a vast world of nice 3rd party libs to cope with what's missing natively, I really have to say that this is troublesome. It requires me to investigate among all your above listed projects AND scattered the implementation effort of many developers into dozens of shards projects, without a quality authoritative implementation.

Other languages (C++, Erlang, and even - through std library collections - the anything goes Python) have ordered maps, and since Go provides unoredered I don't see why it was limited to that only.

R

[Ian Lance Taylor]

On Fri, Jun 15, 2018 at 4:39 AM, <riccard...@gmail.com> wrote:
>
> While I understand there's a vast world of nice 3rd party libs to cope with
> what's missing natively, I really have to say that this is troublesome. It
> requires me to investigate among all your above listed projects AND
> scattered the implementation effort of many developers into dozens of shards
> projects, without a quality authoritative implementation.
>
> Other languages (C++, Erlang, and even - through std library collections -
> the anything goes Python) have ordered maps, and since Go provides
> unoredered I don't see why it was limited to that only.

This question boils down to "why doesn't have Go have generics," a
discussion that has been occurring in detail on many forums over many
years. https://golang.org/doc/faq#generics . The answer to "why
doesn't Go have this particular collection type" can't always be to
explicitly add that type to the language.

Ian

[Michael Jones]

Another view:

The map in Go promises only features supportable by a hash table implementation, and implements with a hash table for speed and hash-related aspects efficiency (wide spreading of close keys, etc.)

An "ordered map" pretty much wants to be a different data structure than a hash table with the left-leaning red-black tree (LLRB) as a good candidate. This would need a different interface than the built-in Go map--a way to traverse down and up.

That different implementation and different usage interface steers the answer toward application-specific implementations, such as the tree code that was shared above (general code) and as in the case of GoLLRB, the need for an application-specific ordering function (making the general case specific). This does not have the feel of a built-in feature because you can't easily use an ordered table without somehow saying how to order it, which is data-structure specific.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Michael T. Jones
michae...@gmail.com

[riccard...@gmail.com]

mm.. the criteria for inserting into a map such as defined by Golang is that of equivalence (A == B), whereas the one used to *ordered* maps, in the general understanding, is that of "precedence" (A < B).

There is a very good common sense definition of those relationships which is usually the one assumed by most languages standard libraries. Yet I'd qualify the "==" definition as arbitrary as that of "<".

I've to admit my background is C++ oriented, so I'd pretty much call me an STL enthusiast which, evidently, Go implementors weren't so much.

R

[Michael Jones]

Perhaps I was unclear.

type pair struct {

   x byte

   y time.Duration

   z [20]char

   key int32

}

var e OrderedMap[pair]int

what should i say to have e ordered by key and y? 

[Daniel Corbe]

Sorry for being dense, but I’m a go noob. Is there a reason you couldn’t
run sort to reorder a []pair?

Something like this:

type Products struct {
Id string `json:"_id"`
Price string `json:"price"`
}

type ByPrice []Products

func (p ByPrice) Len() int { return len(p) }
func (p ByPrice) Less(i, j int) bool {
return p[i].Floatize() < p[j].Floatize()
}
func (p ByPrice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

…
sort.Sort(ByPrice(x))
…

[Daniel Corbe]

Sorry for the double post, but here’s a functional example of using sort to
reorder slices.

https://github.com/dcorbe/target-base64-json-thingy

[Michael Jones]

There is no problem sorting such items. However the original question was "why does Go not have a map facility that can iterate in order to extract the elements." That (logically) means a map that is implemented in a different way, a way that keeps items in key-order and thus the need for the key-ordering capability of the comparison function.

This is not really the same as using a regular map, and extracting all the elements to a slice and sorting them, and using that slice in any case other than the "insert/delete everything" and then extract and sort and then use use case. It does not really do the add/remove/traverse all at the same time in an integrated way. That needs something like a tree (such as an LLRB as in GoLLRB) to have most of the features of a map and all of the features of an ordered collection.

This last is what I was explaining above. It is easy to test for equal. It is *not* easy to test for less than (other than for simple built-in data types). For a general ordering of compound data structures, you need a comparison function. If the built-in map were an ordered map, then you need a way to bind the comparison function to the map data structure. I was sharing this precise need in the last post above.