Basic operations on iterators in Rust in comparison with C++

Question

In order to learn Rust, I'm rewriting some leetcode solution from C++ to Rust and on this way I struggle to understand how to perform some basic operations with iterators.

A particular good problem in this context is Data stream as disjoint intervals. The full implementation in C++ might be found elsewhere. To avoid going into particular algorithm details and concentrate on Rust syntax, I will post part of the C++ code which contains essential operations on C++ iterations which I struggle to translate into Rust:

map<int, int> m; // start to end, [x,y)
void addNum(int val) {
        auto next = m.upper_bound(val); // seems that m.range(val+1..) might give what I need
        if (next != begin(m)) { // begin(m) might be equivalent m.iter() but how to compare it with range is unclear
            auto cur = prev(next); // haven't found prev method on range
            int end = cur->second;
            // adds to end of existing interval
            if (val  == cur->second) {
                int start = cur->first;
                end = val+1;
                // merge two existing intervals
                // ...
            } else {
                // ...
            }
        }
        /// ...
    }

The question is what are the equivalent operations on iterators in Rust? In particular, how to do upper_bound, check that what I've found is begin, do prev, get values/keys out of iterator.

@mkrieger1 sorry, I've updated the post to address your question. Basically, how to rewrite the code in C++ so that it works in Rust. Maybe it requires restructuring due to conceptual differences in iterators in these two languages — Kirill Lykov
– Kirill Lykov, Commented Jan 29, 2022 at 20:36
How far did you come with the examples from the documentation of BTreeMap? Especially range — peterulb
– peterulb, Commented Jan 29, 2022 at 20:49

kmdreko · Accepted Answer · 2022-01-30 18:33:32Z

3

When converting code, you should think less about equivalent functions but equivalent concepts.

This code appears to find the entry in the map m that is at or before the key val. Rust's iterators are not like C++'s since they represent a range instead of a pointer to a value. We can use the range ..=val and get the entry at the end using .next_back():

fn addNum(m: &BTreeMap<i32, i32>, val: i32) {
    if let Some((first, second)) = m.range(..=val).next_back() {
        // rest of the logic
    }
}

^{Note: I've moved m from a global to a parameter.}

As another example of how iterators are different, you suggest that m.range(val+1..) is a way to find the .upper_bound(), which is true, but you would not be able to iterate backwards to before val+1. And likewise, in C++ you have to check against .begin() to see if the next access is valid, but in Rust, access and iteration are one-in-the-same, you simply try to get the next value and it will return None if it doesn't exist.

edited Jan 30, 2022 at 18:33

answered Jan 29, 2022 at 21:01

kmdreko

65.4k6 gold badges106 silver badges178 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Kirill Lykov Over a year ago

Maybe I didn't get your answer, but the code doesn't iterate over the map. Instead it finds the iterator pointing to the first occurrence of the element with key > val. Than, if this found iterator doesn't point to the first element of the map, we take the previous element from the found iterator and proceed accordingly. So the complexity of this method is supposed to be log(n)

kmdreko Over a year ago

My apologies, I misread the first if as a while. I've updated my answer and I used ideone and the Rust playground to compare them.

Kirill Lykov Over a year ago

Interesting, you search for the range up to val and later go back on this range. This is what should be written in the rust books (patterns of work with different standard things) instead of basics of syntax.

Collectives™ on Stack Overflow

Basic operations on iterators in Rust in comparison with C++

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related