4 ms·

There is another, perhaps more important, reason: If you need sorted keys, the map is almost certainly the wrong data structure. Sure, there may be some edge c

There is another, perhaps more important, reason: If you need sorted keys, the map is almost certainly the wrong data structure. Sure, there may be some edge case situations, like where you are dealing with someone else's code where you don't have control over the structures you've been given, but: 1. The standard library doesn't appeal to edge cases. 2. The "noiser" solutions to deal with the edge case serve as a reminder that you aren't working in the optimal space.

jerf 2y ago
I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that if you think you need sorted keys, double-check. I program an awful lot of things without sorted keys, and I am quite aware of the issues around sorting, and I suspect without proof that a lot of people swearing by sorted maps are imposing false ordering requirements on their code more often than they realize. The ideal solution is not need order at all. (I am especially suspicious of extensive use of maps where the keys are sorted by insertion order. That smells... antipatternish to me.)
kbolino 2y ago
This is a bridge that the standard library has already crossed, though. Off the top of my head, both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. Whether in particular cases, a properly ordered data structure (like a tree) should be used instead, is a valid question to ask, and thanks to the custom iterators, it'll now be more ergonomic to use. But if I usually use a particular map for its O(1) operations and only occasionally iterate over the whole thing, yet need consistent iteration order, then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request.
- randomdata 2y ago
  > both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. That is literally the edge case example I gave. Perhaps there is a better way to describe it than "edge case", but semantics is a silly game. > then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request. And, indeed, the standard library provides slices.Sorted(maps.Keys(m)) for exactly that. Ergonomic enough, while making the compromise being made reasonably explicit to help with readability – which is far more important than saving a few keystrokes. If typing is your bottleneck, practice will quickly solve that problem.
  - kbolino 2y ago
    It's never really been about saving keystrokes, but about re-writing the same (fairly common) operation over and over again (and not necessarily the same way each time), and not being able to benefit from future optimizations. However, as examined in a sibling thread, there doesn't seem to actually be any missed optimization which could potentially be applied here.
    - randomdata 2y ago
      In what way is the operation common? We obviously would never say that there is never a use for such thing as there are clear edge cases where it is necessary, but as jerf points out, it is probably not what you actually need in most cases. Even ignoring that in the most common case the map isn't the right structure to begin with, what even is the general case for the situations that remain? You mentioned the marshalling of arbitrary data case, but in that case you also have reflection details to worry about, and which you can optimize for with a custom implementation, and thus wouldn't likely use the built-in anyway. A sibling thread discussed the cache benefits of colocating the values with the keys if a map is exceedingly small, but as soon as the map is of any reasonable size the added overhead of the values is almost certainly going to blow the cache even where the keys alone might still fit. All of which is to say that the best approach is highly context dependent. How do you even begin to choose which is the general case if you were to include such a function?

jerf 2y ago

I endorse this, as I commented in another reply under my post that the correct cache-aware answer is another data structure entirely. But I'd also suggest that if you think you need sorted keys, double-check. I program an awful lot of things without sorted keys, and I am quite aware of the issues around sorting, and I suspect without proof that a lot of people swearing by sorted maps are imposing false ordering requirements on their code more often than they realize. The ideal solution is not need order at all. (I am especially suspicious of extensive use of maps where the keys are sorted by insertion order. That smells... antipatternish to me.)

kbolino 2y ago

This is a bridge that the standard library has already crossed, though. Off the top of my head, both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. Whether in particular cases, a properly ordered data structure (like a tree) should be used instead, is a valid question to ask, and thanks to the custom iterators, it'll now be more ergonomic to use. But if I usually use a particular map for its O(1) operations and only occasionally iterate over the whole thing, yet need consistent iteration order, then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request.

randomdata 2y ago
> both encoding/json and text/template guarantee sorted iteration order of maps. I don't think it's an edge case at all. That is literally the edge case example I gave. Perhaps there is a better way to describe it than "edge case", but semantics is a silly game. > then the built-in map still seems like the right choice, and having a standard way to iterate it is a reasonable request. And, indeed, the standard library provides slices.Sorted(maps.Keys(m)) for exactly that. Ergonomic enough, while making the compromise being made reasonably explicit to help with readability – which is far more important than saving a few keystrokes. If typing is your bottleneck, practice will quickly solve that problem.
- kbolino 2y ago
  It's never really been about saving keystrokes, but about re-writing the same (fairly common) operation over and over again (and not necessarily the same way each time), and not being able to benefit from future optimizations. However, as examined in a sibling thread, there doesn't seem to actually be any missed optimization which could potentially be applied here.
  - randomdata 2y ago
    In what way is the operation common? We obviously would never say that there is never a use for such thing as there are clear edge cases where it is necessary, but as jerf points out, it is probably not what you actually need in most cases. Even ignoring that in the most common case the map isn't the right structure to begin with, what even is the general case for the situations that remain? You mentioned the marshalling of arbitrary data case, but in that case you also have reflection details to worry about, and which you can optimize for with a custom implementation, and thus wouldn't likely use the built-in anyway. A sibling thread discussed the cache benefits of colocating the values with the keys if a map is exceedingly small, but as soon as the map is of any reasonable size the added overhead of the values is almost certainly going to blow the cache even where the keys alone might still fit. All of which is to say that the best approach is highly context dependent. How do you even begin to choose which is the general case if you were to include such a function?