I made an early version of a sorted collection library for Zig. Sorted collections are data structures that maintain the data in sorted order. Examples of these data structures are `java.util.TreeMap` in Java and `std::map` in C++. These data structures are mainly used for fast lookups (point search) and fast range searches.
The library is available on GitHub: https://github.com/CogitatorTech/ordered
masklinn•11h ago
habedi0•11h ago
LandR•9h ago
Galanwe•9h ago
So a list is ordered, but can be sorted or not. A set is unordered but sorted. I guess a priority queue is ordered and sorted.
cb321•8h ago
One might qualify such as "system-ordered", or in the Python insert-ordered dict, qualify with "insertion-ordered", though hash tables in general are sort of a melange of hash-ordering. The same container may also support efficient iteration in multiple orders (e.g., trees often support key order as well as another order, like VM/node pool slot number order).
So, in this context (where things are obviously elements of a computer program), it isn't obvious that hair-splitting over ordered vs. sorted in their purest senses is very helpful when what is really missing is qualification.
Of course, like in many things, people tend to name computer program elements after their abstractions. This is where confusion often comes from (and not just in computing!) .. borrowing the names without all the properties (or maybe with more properties, as in this case, though that is all probably a bit iffy with the frailty of how you enumerate/decompose properties).
EDIT: In a similar way, in a realized computer, almost any "set" representation can also be a "map". You just add satellite data. Even a bit-vector can have a "parallel vector" with satellite data you access after the bits (which could even be pointful in terms of cache access). This can cause similar confusions to the "ordered" vs. "sorted" stuff.
4b11b4•2h ago
effectively you could think of them the same, or that sorting is an application of using the order rules for a given type