4 ms·

its completely pointless to make this an iterator, because you have to loop the entire map to do so, which kills any benefit of using iterators

by 38 2y ago

kbolino 2y ago
And yet slices.Sorted was added which does exactly this already, but only for single-valued iterators.
- deleted 2y ago
  [deleted]
- randomdata 2y ago
  > And yet slices.Sorted was added which does exactly this already It does not. slices.Sorted accepts an iterator, but returns a slice. Like the earlier comments point out, Go tries its best to give a reasonable idea of what kind of complexity is involved at the API level. slices.Sorted returning an iterator would mask that. By returning a slice, it makes clear that the entire collection of data needs to be first iterated over as the parent described.
  - kbolino 2y ago
    This is a good point which likely explains why maps.Sorted doesn't exist (yet): what would it even return? I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. If it ought to return a slice of entries, that opens up new problems. What is an entry? A two-member generic struct? Ok, fine, but then how do I ergonomically iterate over them, pulling out both members? There's no clear solution to that problem yet.
    - randomdata 2y ago
      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
    - 38 2y ago
      > I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. if a function returns an iterator, it should be iterating the input. thats impossible in this situation. you'd need to loop the entire map, then return an iterator that tricks the user into thinking they are getting better performance when they are getting the worst possible performance.
randomdata 2y ago
Not completely pointless. It avoids the need to retain a full copy of all the values. But a good demonstration of why this kind of thing isn't a good fit for the standard library.

its completely pointless to make this an iterator, because you have to loop the entire map to do so, which kills any benefit of using iterators

by 38 2y ago

its completely pointless to make this an iterator, because you have to loop the entire map to do so, which kills any benefit of using iterators

kbolino 2y ago

And yet slices.Sorted was added which does exactly this already, but only for single-valued iterators.

deleted 2y ago
[deleted]
randomdata 2y ago
> And yet slices.Sorted was added which does exactly this already It does not. slices.Sorted accepts an iterator, but returns a slice. Like the earlier comments point out, Go tries its best to give a reasonable idea of what kind of complexity is involved at the API level. slices.Sorted returning an iterator would mask that. By returning a slice, it makes clear that the entire collection of data needs to be first iterated over as the parent described.
- kbolino 2y ago
  This is a good point which likely explains why maps.Sorted doesn't exist (yet): what would it even return? I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. If it ought to return a slice of entries, that opens up new problems. What is an entry? A two-member generic struct? Ok, fine, but then how do I ergonomically iterate over them, pulling out both members? There's no clear solution to that problem yet.
  - randomdata 2y ago
    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
  - 38 2y ago
    > I think returning an iterator is acceptable, the docs could explain the expense of the operation, and the implementation could change in the future as needed. But that does hide some complexity. if a function returns an iterator, it should be iterating the input. thats impossible in this situation. you'd need to loop the entire map, then return an iterator that tricks the user into thinking they are getting better performance when they are getting the worst possible performance.

randomdata 2y ago

Not completely pointless. It avoids the need to retain a full copy of all the values. But a good demonstration of why this kind of thing isn't a good fit for the standard library.