4 ms·
Yeah, this is definitely the downside to Go. You can write more or less the same code as your C++ in Rust like this: use std::collections::HashSet;
by nicoburns 8y ago
Yeah, this is definitely the downside to Go. You can write more or less the same code as your C++ in Rust like this:
use std::collections::HashSet;
fn main () {
let strings = vec![
"apple", "cAt", "cat", "Dog", "apple", "dog", "Cat",
"Apple", "dOg", "banana", "cat", "dog", "apple",
];
let mut set : HashSet<&'static str> = HashSet::new();
let strings : Vec<&str> = strings
.into_iter()
.filter(|string| set.insert(string))
.collect();
println!("{:?}", strings);
}
(runnable snippet: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7d19d63ac220173cc7a40d2695841b69 https://play.rust-lang.org/?version=stable&mode=debug&editio...)
EDIT: updated to make use of the fact that `set.insert` returns a boolean.
- johannkokos 8y agoJust like C++, your filter can be simplified like, filter(|string| {set.insert(string)} as insert return a bool.
- nicoburns 8y agoOo, I didn't realise that. Super handy. I've updated my snippet to make use of your suggestion :)
- DougBTX 8y agoThe output form this is a little different form the article, as it additionally requires: * that the uniqueness check is done case-insensitively, * that the casing from the first instance of the string in the input array should be used in the output, and * that the output should be ordered based on the order of the first instance of the string in the input array Possibly an unusual set of requirements (I'd generally expect that if removing duplicates from a list, that the output order wouldn't matter) but hey, different problems have different requirements. The desired output is: apple cAt Dog banana while that code snippet produces: apple cAt cat Dog dog Cat Apple dOg banana
- dbaupp 8y agoSimilar to the C++, all of those are addressed by inserting lower-cased into the set, which can be achieved via an extra method call: set.insert(string.to_lowercase()) It also requires adjusting/deleting the type annotation on the set. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cc937cb3fca05c3111beda5948e93cb6 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- lasagnaphil 8y agoI've tried to fix the Rust code, but I'm getting some lifetime errors. Can anyone spot the problem? (Note: I've used C++ for most of the time and am still uncomfortable with Rust) use std::collections::HashSet; fn main () { let strings = vec![ "apple", "cAt", "cat", "Dog", "apple", "dog", "Cat", "Apple", "dOg", "banana", "cat", "dog", "apple", ]; let mut set : HashSet<&'static str> = HashSet::new(); let strings : Vec<&str> = strings .into_iter() .map(|string| (string, string.to_lowercase())) .filter(|(_, lower)| set.insert(lower)) .map(|(string, _)| string) .collect(); println!("{:?}", strings); }
- dbaupp 8y agoThe lower value is of type &String because the argument to filter is of type &(String, String) and the pattern match needs to propagate the &. The reference is only valid for the body of the filter closure (that is, it is &'short String, for some anonymous/unnamed lifetime 'short), but it is being put into a set that expects &'static str (the explicit type on the let line). The &String to &str type coercion is fine, but it's not correct to treat the &'short as a &'static (the short one is potentially invalid after filter's closure returns). Changing the type annotations won't make this compile, because it is actually catching a real bug. The iterator is lazy and the full pipeline is executed for each element at once: lowercasing, inserting into the set, inserting into the Vec that's the result of the collect, and deallocating the lower string. This last step is the key/danger: if the HashSet held references/slices to the lower strings (instead of owning them), those references would become dangling immediately and future look-ups into the set won't work right/will trigger undefined behaviour. The problem is a little clearer (and mostly fixed) if you simplify the code slightly by removing the two map calls, and instead call to_lowercase in the filter directly: .into_iter() .filter(|string| set.insert(string.to_lowercase())) .collect(); This form is a type error, that can be corrected by changing the type annotation to be HashSet<String>, or even removing it entirely and letting type inference handle it. The HashSet owning the strings is the key, so they only disappear after the entire iteration is complete, not after each element.
- twic 8y agoFor completeness, Java is basically the same: List<String> strings = new ArrayList<>(List.of("apple", "cAt", "cat", "Dog", "apple", "dog", "Cat", "Apple", "dOg", "banana", "cat", "dog", "apple")); Set<String> seen = new HashSet<>(); strings.removeIf(s -> !seen.add(s.toLowerCase())); strings.forEach(System.out::println); EDIT How much copying does each implementation do? The Go version only copies in the cleanup pass he doesn't show, so it copies each surviving element once, and no other elements. The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving). The C++ version uses remove_if, and the documentation doesn't specify how it does the copying [1], but knowing what C++ people are like, it will probably do the minimum of copying too. The Java version hits some truly hoopy code in removeIf [2], which does the same minimal copying, but does allocate a bitmap and walk the array twice, in order to support predicates which want to look at the rest of the list. I would say all of these reflect their language's values. The Go code is efficient, but only because the programmer has to write it all out longhand, so there is nowhere for inefficiency to hide. The C++ code is (i think!) efficient, because C++ implementers value maximal efficiency in their libraries. The Java code sacrifices a little efficiency to allow its users to do silly things safely. [1] https://en.cppreference.com/w/cpp/algorithm/remove https://en.cppreference.com/w/cpp/algorithm/remove [2] http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/util/ArrayList.java#l1696 http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/j...
- Arnavion 8y ago>The Rust version makes a new vector, so it does the same minimal amount of copying (well, moving). To be clear, the Rust version does not do any copying or moving of the strings. Both the set and the new Vec contains &'static str, same as the original Vec. But a more realistic example is where the original Vec was of String elements instead of &'static str. The same point would still apply, but the result Vec of &str would borrow from the original Vec of String. If the goal was to produce a Vec of String, then it would need to copy (clone) the Strings from the original Vec.