14
\$\begingroup\$

I have this code snippet comparing two slice references:

  fn compare(&self, a: &[u8], b: &[u8]) -> i64 {
    let mut p1 = a.as_ptr() as *mut u8;
    let mut p2 = b.as_ptr() as *mut u8;

    let mut min_len = cmp::min(a.len(), b.len());

    let mut ret = 0;
    while min_len > 0 {
      unsafe {
        if *p1 != *p2 {
          ret = *p1 as i64 - *p2 as i64;
          break;
        } else {
          p1 = p1.offset(1);
          p2 = p2.offset(1);
        }
      }
      min_len = min_len - 1;
    }

    if ret == 0 {
      if a.len() < b.len() {ret = -1;}
      else if a.len() > b.len() {ret = 1;}
    }

    return ret;
  }

I think I wrote it down in C style. I would like to write this in Rust style.

I could replace 'ret' with std::cmp::Ordering. What else could I do?

\$\endgroup\$
3
  • \$\begingroup\$ What is "Vec"? Something in Rust? Or just vector? \$\endgroup\$ Dec 12, 2019 at 0:11
  • \$\begingroup\$ @PeterMortensen Vec is a standard struct in Rust. However, this question doesn't actually relate to Vecs, and only requires a contiguous slice of memory. \$\endgroup\$
    – lights0123
    Dec 12, 2019 at 1:14
  • \$\begingroup\$ this would probably be UB in C. Comparing two pointer that are not from the same source is UB. I don't know for Rust. \$\endgroup\$
    – Stargateur
    Jan 24, 2020 at 23:43

4 Answers 4

13
\$\begingroup\$

What about this:

fn compare(a: &[u8], b: &[u8]) -> cmp::Ordering {
    for (ai, bi) in a.iter().zip(b.iter()) {
        match ai.cmp(&bi) {
            Ordering::Equal => continue,
            ord => return ord
        }
    }

    /* if every single element was equal, compare length */
    a.len().cmp(&b.len())
}

I've removed the self argument, and used the cmp-module to do the actual comparison and zip() as @alexv already suggested.

\$\endgroup\$
12
  • 2
    \$\begingroup\$ How about match ai.cmp(&bi) { Ordering::Equal => continue, ord => return ord }? \$\endgroup\$
    – trent
    Dec 11, 2019 at 15:03
  • 1
    \$\begingroup\$ @FrenchBoiethios I cannot judge if it's less idiomatic, bit it's a hell of a lot harder to read and to follow (at least for a beginner like me). \$\endgroup\$
    – AlexV
    Dec 11, 2019 at 15:14
  • 3
    \$\begingroup\$ @FrenchBoiethios I didn't say it was unidiomatic, I said it wasn't better. Good code is readable code. Really good code is code that's so stupid obvious, you don't need two brain cells to rub together in order to understand it. In my opinion, the explicit return in the for loop is more obvious than the implicit break hidden in the find in your answer. In a code review I'd prefer to be reading larkey's code rather than yours. But that doesn't mean yours is bad; I upvoted both. \$\endgroup\$
    – trent
    Dec 11, 2019 at 16:04
  • 1
    \$\begingroup\$ @trentcl Thanks for the suggestion, my Rust is a bit rusty and I used this as an exercise to get into the language again :) I really need to get used to using match more, it's such a nice tool. \$\endgroup\$
    – ljrk
    Dec 11, 2019 at 17:08
  • 1
    \$\begingroup\$ @FrenchBoiethios I suppose it comes down to the codebase, if this code is part of eg. a proofing framework, I'd rather use your code as I a) expect the contributers to be "fluent" in function programming (styles) and b) it's usually nicer to proof formally. If the code is however part of a low-levelish library or such, I'd use my approach as the people there are usually more comfortable with imperative programming. In the end Rust allows for both and a project needs to decide what they want to emphasize. I've updooted your answer as well, it beautifully shows off Rusts features! \$\endgroup\$
    – ljrk
    Dec 11, 2019 at 17:12
8
\$\begingroup\$

I take the idea to return an Ordering from the other answer:

use std::cmp;

pub fn compare(a: &[u8], b: &[u8]) -> cmp::Ordering {
    a.iter()
        .zip(b)
        .map(|(x, y)| x.cmp(y))
        .find(|&ord| ord != cmp::Ordering::Equal)
        .unwrap_or(a.len().cmp(&b.len()))
}

You can use the powerful Rust iterators:

  • zip allows to iterate both the slices at once,
  • map transforms each pair to an enum variant representing the ordering of the 2 numbers
  • find tries to find a pair that isn't equal
  • if nothing is found, I return the difference between the slices sizes.
\$\endgroup\$
5
\$\begingroup\$

The code is very C-like indeed. But fortunately there is no need to resort to raw pointers in that case. Rust has very useful Iterators along with a handy method called zip(...) that can be used here. To quote the relevant documentation:

zip() returns a new iterator that will iterate over two other iterators, returning a tuple where the first element comes from the first iterator, and the second element comes from the second iterator.

Sounds like a good match for what you're trying to do.

Below is the code rewritten using zip() (I omitted &self to make it compile in the Rust playground).

fn compare(a: &[u8], b: &[u8]) -> i64 {

    let mut ret = 0;
    for (p1, p2) in a.iter().zip(b.iter()) {
        if p1 != p2 {
            ret = *p1 as i64 - *p2 as i64;
            break;
        }
    }

    if ret == 0 {
        if a.len() < b.len() {
            ret = -1;
        }
        else if a.len() > b.len() {
            ret = 1;
        }
    }

    ret
}

Since you did not provide any test vectors, you will have to check yourself if the result is fully as expected in your application, and also if there are any major performance hits if that matters to you.

Also, there are likely even more compact versions to write this, because I'm not really highly experienced in Rust programming.

\$\endgroup\$
2
\$\begingroup\$

Also you may compare two slices without using zip(), try it on the Rust Playground:

fn compare<T: Ord>(a: &[T], b: &[T]) -> std::cmp::Ordering {
    let mut iter_b = b.iter();
    for v in a {
        match iter_b.next() {
            Some(w) => match v.cmp(w) {
                std::cmp::Ordering::Equal => continue,
                ord => return ord,
            },
            None => break,
        }
    }
    return a.len().cmp(&b.len());
}

fn main() {
    assert_eq!(std::cmp::Ordering::Equal, compare(&[1, 2, 3], &[1, 2, 3]));
    assert_eq!(std::cmp::Ordering::Less, compare(&[1, 0], &[1, 2]));
    assert_eq!(std::cmp::Ordering::Less, compare(&[], &[1, 2, 3]));
    assert_eq!(std::cmp::Ordering::Greater, compare(&[1, 2, 3], &[1, 2]));
    assert_eq!(std::cmp::Ordering::Greater, compare(&[1, 3], &[1, 2]));
}


Code review:

  1. You don't need the &self argument, since you did not use it: self parameter is only allowed in associated functions and not semantically valid as a function parameter. note: associated functions are those in impl or trait definitions

  2. You need use std::cmp; otherwise rewrite e.g. this: std::cmp::min(a.len(), b.len());

  3. It is not common to return -2 for compare(&[1, 0], &[1, 2]))

  4. Use min_len -= 1; instead of min_len = min_len - 1;

  5. You may use: ret = a.len() as i64 - b.len() as i64; which returns length diff instead of:

        if a.len() < b.len() {
            ret = -1;
        } else if a.len() > b.len() {
            ret = 1;
        }
  1. You don't need else after break here:
if *p1 != *p2 {
                ret = *p1 as i64 - *p2 as i64;
                break;
            }
  1. For simple code you may return instead of break:
fn compare(a: &[u8], b: &[u8]) -> i64 {
    let mut p1 = a.as_ptr() as *mut u8;
    let mut p2 = b.as_ptr() as *mut u8;
    let mut min_len = std::cmp::min(a.len(), b.len());
    while min_len > 0 {
        unsafe {
            if *p1 != *p2 {
                return *p1 as i64 - *p2 as i64;
            }
            p1 = p1.offset(1);
            p2 = p2.offset(1);
        }
        min_len -= 1;
    }
    return a.len() as i64 - b.len() as i64;
}
  1. You may simply avoid using unsafe like the following code:
fn compare(a: &[u8], b: &[u8]) -> i64 {
    let mut p1 = a.iter();
    let mut p2 = b.iter();
    let mut min_len = std::cmp::min(a.len(), b.len());
    while min_len > 0 {
        let v = *p1.next().unwrap();
        let w = *p2.next().unwrap();
        if v != w {
            return v as i64 - w as i64;
        }
        min_len -= 1;
    }
    return a.len() as i64 - b.len() as i64;
}
  1. You may use generics for more code reusability:
fn compare<T: Ord>(a: &[T], b: &[T]) -> std::cmp::Ordering {
    let mut p1 = a.iter();
    let mut p2 = b.iter();
    let mut min_len = std::cmp::min(a.len(), b.len());
    while min_len > 0 {
        let v = p1.next().unwrap();
        let w = p2.next().unwrap();
        if v != w {
            return v.cmp(w);
        }
        min_len -= 1;
    }
    return a.len().cmp(&b.len());
}

fn main() {
    assert_eq!(std::cmp::Ordering::Equal, compare(&[1, 2, 3], &[1, 2, 3]));
    assert_eq!(std::cmp::Ordering::Less, compare(&[1, 0], &[1, 2]));
    assert_eq!(std::cmp::Ordering::Less, compare(&[], &[1, 2, 3]));
    assert_eq!(std::cmp::Ordering::Greater, compare(&[1, 2, 3], &[1, 2]));
    assert_eq!(std::cmp::Ordering::Greater, compare(&[1, 3], &[1, 2]));
}

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.