5 ms·

On one hand it indeed feels like more strict version of move semantics in C++, on the other hand it also prohibits what is central idea of STL - having multiple

• yati 11y ago
  Most algorithms that I use from the C++ stdlib take `container.begin()` and `container.end()`, and use the latter to check for the end condition in the main loop. Given that Rust has the `Iter` trait which allows you to iterate straight through any type that implements it, I do not see the point in having multiple mutable references. I mean, sure, it is useful sometimes, but it also brings in a lot of headaches with it :)
  • 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.
• Manishearth 11y ago
  Multiple mutable references can be problematic though: http://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/ http://manishearth.github.io/blog/2015/05/17/the-problem-wit... (Rust has Cell/RefCell if you need this, though)
  • wuch 11y ago
    Thanks for link. In C++ ensuring whether something is safe is indeed sometimes quite non-trivial, my favourite, but non-practical example is non-empty std::list<int> x, used in following way: x.remove(x.front()); Comment for non-C++ programmers: front method returns a reference to the first value in the list, and remove takes a const reference to value and removes all elements that compare equal to it. Problem is of course that after comparing first element with provided argument, it would compare equal and be subsequently deleted, making the reference invalid. As a side comment, I will note that above is in fact required to work, though it is probably not something you should write.
    • Manishearth 11y ago
      I like this example a lot :)