Ben Chuanlong Du's Blog

It is never too late to learn.

Equivalent of C++'s std::set_difference in Rust

Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!

In [ ]:
:timing
:sccache 1

Tips and Traps

  1. There is no equivalent of C++'s std::set_difference in Rust. However, you can convert both inputs to HashSet (or BTreeSet) and then call the set_difference method on HashSet (or BTreeSet). However, you can implement an efficient one leveraging vector slice and binary search.
In [ ]:
struct SortedDiff<T, U: Iterator> {
    it1: T,
    it2: Peekable<U>,
}

impl<T, U, W> Iterator for SortedDiff<T, U>
    where
        T: Iterator<Item = W>,
        U: Iterator<Item = W>,
        W: Ord,
{
    type Item = W;
    
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(elm1) = self.it1.next() {
            'inner: loop {
                match self.it2.peek().map(|elm2| elm1.cmp(elm2)) {
                    None => return Some(elm1),
                    Some(Ordering::Less) => return Some(elm1),
                    Some(Ordering::Equal) => break 'inner,
                    Some(Ordering::Greater) => { self.it2.next(); },
                }
            }
        }
        
        None
    }
}

Remove Multiple Elements At Given Indexes from a Vector

Assuming the indexes are sorted.

swap_remove

If you do not care about persist the original order of elements, the most efficient way is to use the method Vec.swap_remove. The trick is to remove from the largest index using Vec.swap_remove.

Manually Calculate New Index

If persisting the original order is required, you can manually calculated the new index for each index to be removed. For example, if the element at index 1 needs to be removed, check the next index to see whether it is available until you find a valid index to use.

References

std::set_difference

C++ std::set_difference equivalent in Rust

std::slice

In [ ]:

Comments