3 ms·
An illustrative example is a string set which remembers its insertion order. In C++ you may write: struct OrderedSet { deque<string> storage;
by ridiculous_fish 5y ago
An illustrative example is a string set which remembers its insertion order. In C++ you may write:
struct OrderedSet {
deque<string> storage;
set<string_view> vals;
}
The deque holds the string contents, and the set holds views of those contents. This is safe because the deque has iterator stability, and it's pleasant because the `vals` set can just be a regular set.
As you say Rust does not allow this; its answer is IndexSet, and it is implemented differently, like:
struct OrderedSet {
Vec<String> buckets;
RawTable<usize> hashToBucketIndex;
}
RawTable is a hash table that doesn't know how to compute a hash or determine equality. Instead, you provide it with closures to do those tasks, but at the call site (not construction time).
Basically Rust achieves the same thing through a layer of indirection involving indexes, which is a common pattern.