How Rust and C++ Standard Libraries Handle Return Values: Position vs. Reference

Recently I have been experimenting with how Rust handles things differently from the C++ point of view and it is in my mind the first language introducing something new for a while (The borrow checker).

Anyways, one of the most important things in any programming language is handling algorithms and containers. One of the main differences between C++ and Rust in this context (and tbh any other language) is the separation of the algorithms from the containers and having some universal language (like the Iterators) to make the container be able to communicate with algorithms.

As iterators are nothing but fancy pointers, this introduces the problem of the programmer having to be careful when having some iterator, as it may be dangling at any point if we do any modifications on the container.

So as known for many C++ programmers, the notion of searching in an arbitrary Range [begin, end) is either to return an iterator to something inside the range if found or end.

So assuming something very basic like this:

std::vector<int> v{1,4,5};
auto it = std::ranges::find(v, 4);
v.clear();

We would clearly have a dangling reference.

In contrast, Rust handles that by returning an Option<&T> for the possibly existing element, and because of its super powerful borrow checker, it would not compile if trying to clear the vector as being done above, because we have a reference to it.

So the following code would not compile. Is not that nice?

let mut numbers = vec![3, 7, 2, 9, 5];
let maybeVal = numbers.iter().find(|&&x| x==9);
numbers.clear();
println!("{}", maybeVal.unwrap())

In fact, one of the guidelines found in the rust book is to return a reference (instead of an index) so that the compiler can handle the above awful cases.

So far so good, but does it always work with references? Unfortunately not.

One of the most critical decisions in any searching library is what to do when not finding the element? Should we return -1? or even a None like Rust (Usually called Bottom Element in Abstract Algebra)? Well, the inventor of STL Alexander Stepanov has discussed it in one of his talks arguing that it is almost wrong to return that bottom element instead of some useful position.

Okay wait a minute! Why would there exist any useful position when there is no matching element?

Well, almost right. Consider the example of binary search:

std::vector<int> v {1,4,5,6,7};
auto it = std::ranges::lower_bound(v, 5);

A typical scenario with a sorted sequence is to add the element in right order, so we may not find the element, but the algorithm would indeed as result of its searching end in a position mostly close to the 5 (or 5 itself as above), so we can then do v.insert(it, 5);

So what does Rust library do here? Well actually the same: it also returns either the index if found or the index of the insertion position—specifically as a Result<usize, usize> where Ok(index) means found and Err(insertion_position) means not found.

So any useful implementation would indeed return the position instead of the value itself, but the power of the STL library is its combination of reference and positions in the same type : The Iterator.

But here's the thing: this isn't just a pragmatic choice, it's actually forced by the borrow checker. If Rust's binary_search returned an Option<&T> like find does, you'd be completely stuck when trying to insert. Why? Because to insert an element, you need a mutable borrow of the vector (&mut Vec<T>). But if you're holding an immutable reference (&T) to an element, Rust's borrow checker won't let you get a mutable reference to the same vector. They can't coexist.

let mut v = vec![1, 4, 6, 7];
let reference = v.iter().find(|&&x| x==4); //immutable borrow
v.push(4); // ERROR: can't mutably borrow while immutably borrowed
println!("{}", reference.unwrap())

So returning an index isn't just convenient. it's the only way to make the insertion use case work. The index is a value type that doesn't borrow the vector, so you're free to mutate the vector afterward.

I am not saying it is good or bad, and I am not here to trash talk one language or the other. I just wanted to shed the light on something I noticed as someone a bit interested in language design.

I would say it is a wise choice what Rust did, and now I realize it's not just because binary search is a less frequent use case than linear search, it's actually enforced by the language's safety guarantees. It is just my opinion at the end. What do you think?