Skip to content

Instantly share code, notes, and snippets.

@kaisellgren
Last active August 29, 2015 14:12
Show Gist options
  • Save kaisellgren/a3f1e724ba8a1d142808 to your computer and use it in GitHub Desktop.
Save kaisellgren/a3f1e724ba8a1d142808 to your computer and use it in GitHub Desktop.
Removes duplicate entries from Vec with a complexity of O(N(N+1)/2).
/// Is based on the dual pointer technique where ´current´ iterates as usual,
/// but ´runner´ iterates until it hits the ´current´, and then ´current´ proceeds.
pub fn remove_duplicates<'a, T: Eq>(data: &'a mut Vec<T>) {
let mut current_index = 0;
while current_index < data.len() {
let mut runner_index = 0;
while runner_index < current_index {
if &data[runner_index] == &data[current_index] {
data.remove(current_index);
current_index -= 1;
break;
}
runner_index += 1;
}
current_index += 1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment