Does Rust has a std algorithms library (like C++) that contains common algorithms, i.e. find, count etc and can be used on collections from std::collections or is this solved differently in rust
C++ conflates the meaning of:
-
a general-purpose iterator (i.e., a lazy sequence of elements, i.e., an "object" that yields elements when "polled" (which makes it possible, for instance, to have infinite iterators)), which corresponds, in Rust, to the
Iteratorinterface, -
and what Rust calls slices, i.e., contiguous(-ly laid out in memory) sequences of elements.
For operations that don't rely on backing storage, but just on scanning the elements of a collection, the first API is the one that makes most sense, so that's where you'll find ops such as .find(), .any(), .max(), etc.
And for operations that do, such as in-place mutation, you should look at the slices API directly, where you'll find ops such as .sort() or .rotate().
That being said, the standard library does not hold all the possible algorithms in the universe (how could it?), so, for more advanced algorithms, looking for external libraries tailored for it is the way to go, especially given how easy it is in Rust to pull a dependency:
-
for
Iteratoron steroids,use ::itertools::Itertools;, -
for specific slice ops such as shuffling, you'd have to look in a more rng-oriented crate, such as
::rand.
When in doubt, you can always search within the standard library, or search among the public external crates (that may not always be as good as one'd desire, in which case for pervasive patterns that require external crates, I recommend taking a look at "the Rust cookbook".
8 Likes
That is definitely not what iterator is in C++
Of course not, but there is a certain "pool" of common algorithms that std should provide.
Thanks for the answer, but do I understand it correctly? There isn't such thing like let's say std::sort to which you can provide either range/container or iterators from any container?
Like I've said. I'm confused how it is done in rust. Rust also seem to name things identically to let's say C++ but they mean something different. Like iterator for example.
That is exactly what I've just discovered. Thanks
The standard library only provides sorting for slices (and by extension things that can expose their contents as a slice). I'm not too familiar with what C++ means with iterator, but Rust uses the same meaning as a lot of other languages, and if C++ means something else, then C++ is honestly the odd one out.
1 Like
No, Rust is odd.
I'm not talking about just sorting algorithm. I'm talking about some sort of module that would have most common algorithms in it. See algorithm header from C++
Rust doesn't collect all of the algorithms in a single module.
2 Likes
OK, so how it is done in rust. I have a collection and I do want to find an item. Does each collection implement find?
Each collection exposes some way of obtaining an iterator over the items in that collection. You can then use the Iterator::find method on the iterator to find your value. This method is automatically implemented for all iterators, although collections can override it if they have a faster way to do it (e.g. iterators over slices override skip to be constant time).
2 Likes
OK, thanks. But what do you mean that the method is automatically implemented?
Traits can provide a default implementation for some of their methods, which looks like this:
trait MyTrait {
fn you_must_implement_me(&self) -> i32;
fn automatically_implemented(&self) -> i32 {
self.you_must_implement_me() + 1
}
}
When implementing the trait for a type, you don't have to implement methods with a default implementation:
impl MyTrait for i32 {
fn you_must_implement_me(&self) -> i32 {
*self
}
}
The Iterator trait provides a large number of utility functions as methods with default implementations.
1 Like
std::iter::IntoIterator
Conversion into an Iterator .
By implementing IntoIterator for a type, you define how it will be converted to an iterator. This is common for types which describe a collection of some kind.
If you look at the bottom, you can see for which types the trait is implemented.
Yep, hence my:
C++ seems to call iterator what in Rust is rather a slice (or a cursor, but that's an API that isn't that useful in Rust, since it is incompatible with Rust's magnificent exclusive pointer abstraction &mut (abusingly dubbed "mutable reference")).
- Or in other terms, a Rust ("object" (whose type) implements)
Iteratorcan be viewed as a cursor, but one that is unable to change the direction in which it moves (so you cannot use anIteratorto start scanning, find an element, and then start scanning backwards).
It is important to realize that Rust splits those two notions explicitly, so you will need to use the tool from the appropriate place.
2 Likes
let collection = ...; // could be a Vec, a HashMap, a LinkedList, _etc._
if let Some(found) = collection.iter().find(...) {
// use the `found` element
} else {
// not found case
}
This is because Rust collections are iterables, i.e., an Iterator "object" can be retrieved out of them; by convention through the .iter(), .iter_mut(), or .into_iter() methods, corresponding to each of the types of the Rust trinity:
-
by shared / shareable / copiable reference
&T(usually corresponding toT const &reference type in C++), -
by exclusive / unique reference (
&mut T; careful this reference type has stronger properties than C++'sT &mutable reference), -
by move / in an owned manner (
T).
Once you get that object that implements the Iterator interface, you automagically get all the algorithms that can be implemented with a single uni-directional scan, such as .find(), .any(), .max().
3 Likes
C++ iterator specification is a mess that I think no language should try to rely on for terminology. There are 6 different kinds of iterators which are not always extensions of each other.
The basic iterator concept in C++ requires two operations: an overload of dereference operator *it and of the increment operator it++ both with a set of preconditions. However it does not promise that the result of *it is a reference—but it can specifically not be void— or what semantics increment has. For iterators over sequences, an iterator is dereferencable and incrementable if it is not a past-the-end iterator but at the same time no comparison operator is required? Honestly, I'm out of ideas how this requirement alone is any useful.
An input iterator should do all work in its overload of it++ as its deref is required to be idempotent. But at the same time an output iterator must heavily rely on overloading *it instead and most standard ones in fact don't do anything on their ++ operators. Neverthelss callers must increment them anyways to avoid UB. Random access iterators must implement offsetting (+= n, -= n) and do so in constant time. It must also be possible compute offsets between iterators which is not at all equivalent. There is no intermediate concept. I doubt most code takes the later requirement serious and it has no semantic check. In particular, an iterator over an iovec/WSABUF could not fulfill it...
The forward iterator gives you that you get a reference from deref and a comparison to a past-the-end but you still can't stored the reference and assume it is valid after iterating to the next element (it++). If anything these are already too strong requirements for most implementations as copies must be incrementable independently and iterators that compare equal must also return the same element and vice-versa.
And finally, a contiguous iterator is a superfluous concept as it is equivalent to some span of memory and shouldn't have any other useful implementation as indeed you are allowed to circumvent any method overloads by getting the memory addresses directly. The only useful benefit is stronger typing of the iterator type itself.
6 Likes
I think the root of your confusion is that Rust generally doesn't expose a module grab-bag of functions, instead algorithms are implemented as methods on the structs or traits for which they're useful.
7 Likes
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.