3 ms·

Right, in most cases you could replace begin(), end() with whole container / range, when considering arguments to the algorithm function. Though, there are some

by wuch 11y ago

Right, in most cases you could replace begin(), end() with whole container / range, when considering arguments to the algorithm function. Though, there are some exceptions, like std::rotate, or just cases where you want to place result in the same container. Looking from the perspective of implementation of those algorithms, it is no longer that simple and single iterator is rarely sufficient, consider: std::unique, std::reverse, std::partition, std::sort, std::inplace_merge to name a few, where there is much more to it than just checking for end.

Tyr42 11y ago
Some of those do show up on iter. https://doc.rust-lang.org/std/iter/trait.Iterator.html https://doc.rust-lang.org/std/iter/trait.Iterator.html But some of the more specialized ones don't work using just iter. But on the other hand, no iterator invalidation.
- steveklabnik 11y ago
  The next version of Rust has _significantly_ updated documentation here. A link for anyone reading before the next two weeks: https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html
- wuch 11y ago
  The crucial difference I had in mind, is that those from C++ work in-place. Returning a new collection as a result poses no problem for either of those languages. Writing specialized version for each collection is also possible, but with STL you don't have to do that. Maybe it would be possible to implement those algorithms in Rust in terms of ranges like in D, instead of iterators? I will have to try and see.
  - Gankro 11y ago
    The problem with Ranges is you can't trust anything they tell you about bounds, and they can't trust you about bounds, so every access has to be checked. This hurts in algorithms like binary search and sorting (which are some of the few algorithms that don't work for iterators). Ultimately though, there just hasn't been a lot of demand for ranges. Iterators and slices do most of the work people care about. We actually had tried to make iterators more like ranges back in the day, but we tore it out because no one cared. To this day you can't sort a VecDeque, and no one has ever bothered us about it.
    - wuch 11y ago
      I did indeed look a little bit about previous attempts at collections in Rust, but didn't find too much about ranges. What would be good keywords and place to look for, any hints? It seems to me that you can go quite far with mutable but mutually disjoint ranges - which is more or less what slices do for vectors currently. They are also safe, because you can only split them into subslices (which borrow ownership), but not extend them (what could potentially create overlapping ranges). Moreover as long as there is any range to given container, you can't perform operations that could invalidate derived ranges (things that reallocate vector, etc.) Range checking don't seem that bad, because in most cases it is not about trusting what a range tells you, but range trusting itself which is fine. Take you example of binary search, if range would know how to split itself in the middle, it wouldn't really have to do any bounds checking. For sorted ranges maybe operation like lower_bound or upper bound would be great primitives, or single operation that encompasses both situations: let (lower_range, equivalent_range, upper_range) = range.split(&value); Of course, in general as you point out, you would have to pay a price of bounds checking for random access. As far as I can see, this should be sufficient to implement algorithmic part. What I still find hard to do, is to modify collections based on resulting range. For example, how to write equivalent to following C++ code, that first moves consecutive duplicates to the end of array, and then erases them from container: std::vector<int> v { ... }; v.erase(unique(v.begin(), v.end()), v.end()); I have a few ideas, which mostly boil down to following: create a description of operation to be executed, but is executed only after all ranges have returned their ownership over collection. But so far this interface have not been fully satisfactory.

by wuch 11y ago

Tyr42 11y ago

Some of those do show up on iter. https://doc.rust-lang.org/std/iter/trait.Iterator.html https://doc.rust-lang.org/std/iter/trait.Iterator.html But some of the more specialized ones don't work using just iter. But on the other hand, no iterator invalidation.

steveklabnik 11y ago
The next version of Rust has _significantly_ updated documentation here. A link for anyone reading before the next two weeks: https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html https://doc.rust-lang.org/beta/std/iter/trait.Iterator.html
wuch 11y ago
The crucial difference I had in mind, is that those from C++ work in-place. Returning a new collection as a result poses no problem for either of those languages. Writing specialized version for each collection is also possible, but with STL you don't have to do that. Maybe it would be possible to implement those algorithms in Rust in terms of ranges like in D, instead of iterators? I will have to try and see.
- Gankro 11y ago
  The problem with Ranges is you can't trust anything they tell you about bounds, and they can't trust you about bounds, so every access has to be checked. This hurts in algorithms like binary search and sorting (which are some of the few algorithms that don't work for iterators). Ultimately though, there just hasn't been a lot of demand for ranges. Iterators and slices do most of the work people care about. We actually had tried to make iterators more like ranges back in the day, but we tore it out because no one cared. To this day you can't sort a VecDeque, and no one has ever bothered us about it.
  - wuch 11y ago
    I did indeed look a little bit about previous attempts at collections in Rust, but didn't find too much about ranges. What would be good keywords and place to look for, any hints? It seems to me that you can go quite far with mutable but mutually disjoint ranges - which is more or less what slices do for vectors currently. They are also safe, because you can only split them into subslices (which borrow ownership), but not extend them (what could potentially create overlapping ranges). Moreover as long as there is any range to given container, you can't perform operations that could invalidate derived ranges (things that reallocate vector, etc.) Range checking don't seem that bad, because in most cases it is not about trusting what a range tells you, but range trusting itself which is fine. Take you example of binary search, if range would know how to split itself in the middle, it wouldn't really have to do any bounds checking. For sorted ranges maybe operation like lower_bound or upper bound would be great primitives, or single operation that encompasses both situations: let (lower_range, equivalent_range, upper_range) = range.split(&value); Of course, in general as you point out, you would have to pay a price of bounds checking for random access. As far as I can see, this should be sufficient to implement algorithmic part. What I still find hard to do, is to modify collections based on resulting range. For example, how to write equivalent to following C++ code, that first moves consecutive duplicates to the end of array, and then erases them from container: std::vector<int> v { ... }; v.erase(unique(v.begin(), v.end()), v.end()); I have a few ideas, which mostly boil down to following: create a description of operation to be executed, but is executed only after all ranges have returned their ownership over collection. But so far this interface have not been fully satisfactory.