4 ms·

We also frequently need reference types to contiguous storage in addition to value types of contiguous storage. In C++ this is satisfied by std::span for both

We also frequently need reference types to contiguous storage in addition to value types of contiguous storage. In C++ this is satisfied by std::span for both the static and dynamic cases.

LegionMammal978 5y ago
True. In Rust those are regular slices, and in C# and Java all collections are owned by the runtime anyway. Something which several languages do lack, though, is a view of a contiguous subsequence, in the manner of an std::span; it would be nice to see those in more places. I've also taken a look at Golang's slices, which have rather confusing ownership semantics. One can take a subslice of a slice, and its elements will track those of the original, but appending to that subslice will copy the values into an entirely new array. In fact, appending to the original slice past its capacity causes a reallocation, which can invalidate any preexisting subslices. This also occurs with C++ vectors and spans, if I am not mistaken. This is an area where I think Rust's borrow checker really shines; it prevents you from resizing a vector if there are any active slices, encouraging you to instead store a pair of indices or some other self-contained representation.
- brandmeyer 5y ago
  You cannot append to a std::span, or append to a vector-backed span through the span. You have to perform the append on the underlying vector. It is possible to perform an insertion into the middle of a std::vector through std::vector::insert. If you can establish the precondition that the underlying vector will not re-allocate as a result of the append, then it is perfectly safe to perform such an append while holding a reference to one or more elements of the vector. Same thing for insertions: references to elements before the insertion point may still remain valid if you can establish the precondition that the vector will not be resized. In both cases, it is straightforward to establish the precondition through the reserve() member plus some foreknowledge of how much extra capacity the algorithm needs. You can always construct a user-defined reference type which back-doors the borrow checker, such as by storing indexes instead of iterators as you mentioned. If the std.vector is reduced, then they are still just as invalid.

We also frequently need reference types to contiguous storage in addition to value types of contiguous storage. In C++ this is satisfied by std::span for both the static and dynamic cases.

LegionMammal978 5y ago

True. In Rust those are regular slices, and in C# and Java all collections are owned by the runtime anyway. Something which several languages do lack, though, is a view of a contiguous subsequence, in the manner of an std::span; it would be nice to see those in more places. I've also taken a look at Golang's slices, which have rather confusing ownership semantics. One can take a subslice of a slice, and its elements will track those of the original, but appending to that subslice will copy the values into an entirely new array. In fact, appending to the original slice past its capacity causes a reallocation, which can invalidate any preexisting subslices. This also occurs with C++ vectors and spans, if I am not mistaken. This is an area where I think Rust's borrow checker really shines; it prevents you from resizing a vector if there are any active slices, encouraging you to instead store a pair of indices or some other self-contained representation.

brandmeyer 5y ago
You cannot append to a std::span, or append to a vector-backed span through the span. You have to perform the append on the underlying vector. It is possible to perform an insertion into the middle of a std::vector through std::vector::insert. If you can establish the precondition that the underlying vector will not re-allocate as a result of the append, then it is perfectly safe to perform such an append while holding a reference to one or more elements of the vector. Same thing for insertions: references to elements before the insertion point may still remain valid if you can establish the precondition that the vector will not be resized. In both cases, it is straightforward to establish the precondition through the reserve() member plus some foreknowledge of how much extra capacity the algorithm needs. You can always construct a user-defined reference type which back-doors the borrow checker, such as by storing indexes instead of iterators as you mentioned. If the std.vector is reduced, then they are still just as invalid.