Hacker News Reader

>One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated.

I believe this is incorrect and small-vector optimization is in fact disallowed by the C++ standard. In any case, standard or not, no implementation is ever going to do SVO because it would require a branch on every access, making them incompatible with SIMD instructions.

>Rust also has a concept of zero sized types, which C++ does not

No, C++ allows this optimization too, it just requires that the "sizeof" operator always returns an integer >= 1.

> how much you know about Rust

Very little, so please bear with me ;)

For example, from the linked page:

> Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less.

Does C++ also provide this guarantee?

> Vec will never perform a "small optimization" where elements are actually stored on the stack for two reasons:

Does C++ do this?

and from your response:

> No iterator invalidation from iterators you get from it

How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?

As you can see, I don't know enough about C++ as I would like either…

If you have 10 minutes or so, this is an excellent talk that explains how Rust's Vec<T> works by comparing it to Java and C++: https://youtu.be/ksirw1v5gXk?t=748 (The rest of the talk is great too, but it's 50mins in total!)

I haven't been exposed to how ownership/borrowing worked, so this video was great! Thanks for sharing it, since it made many of the other comments in this thread more clear.

> Does C++ also provide this guarantee?

I don't think it does. It might.

> Does C++ do this?

IIRC C++ is allowed to perform the optimization. I don't recall if any current implementations do. They might.

Edit: I'm wrong, it's not, however std::string is allowed to.

> How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?

Because Rust has an entire system of ownership and borrowing which exists at compile time to ensure these things don't happen.

C++ is not allowed to do the small buffer optimization for std::vector<T>. You'll find a number of small_vector<T> classes from third parties, though.

The reason is that std::swap(v1, v2) must never invalidate existing iterators and/or references to elements into either vector, which the optimization would clearly break.

std::string is the type you may be thinking of, where the standard does make a special exception to enable the SSO.

aha! good to know.

Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.

Well, I must be misunderstanding how iterators work in Rust, then. AFAIK in C++ an iterator is a thin wrapper around a pointer in memory, and resizing the container can cause the underlying "base" array to move around to somewhere else if it's reallocated–thus, the invalidation of the old iterator. What is a Rust iterator doing in this case?

In Rust you can have as many const references to a thing as you like, but you can only have a mutable reference to a thing if there are no other references (mutable or not) to the same thing. Hence it's not possible to have an iterator over a vector while trying to mutate it.

Ahh, so that's how it works. I wasn't quite getting how Rust's compiler was figuring this out, but I get it now.

The same thing. At compile time rust won't allow you to push to a vector if you have outstanding iterators.

To expand (hopefully correctly, I'm still learning Rust): You can have a single "mutable borrow" in a single lexical scope where you can mutate the vector _and its contents_ to your liking, but you can't pass a vector mid-mutation to another scope to read the vector while that borrow is active. It is safe to mutate the vector and its contents, as the vector owns the items inside it and there is only one active user of the collection.

If you don't have a mutable borrow active, you can immutably borrow it as many times as you like and iterate over it to your heart's content in as many scopes as you like, but you can't mutate it.

These borrows are lexically scoped.

This is a start to explaining ownership: https://doc.rust-lang.org/book/second-edition/ch04-01-what-i...

So, sorry for being not bright. But if I may ask, if I have a Vec<B> A, then, it has I have a mutable reference to it in the form of A. Now, I take a const iterator to an object in A, say it, then, though the iterator is const for object of type B, it is a mutable reference for the Vec<B> A, and hence, I now cannot reallocate A till all the iterators have died(most probably because of scope). Is that true?

I don't really understand the scenario you're putting out. Why would the iterator be a mutable reference? (there are mutable iterators but you explicitly said const).

Basically, in Rust, this happens:

    let x = vec![1,2,3,4];
    let iterator = vec.iter();
    vec.push(5); // will not compile, until iterator goes out of scope

Nevermind, I think I've got it, basically, all references to an object should die before an object is changed.

Yes. So I'm asking the logic behind this in context of ownership model. How can you derive the above behavior from the principle that only one mutable reference is allowed? If const iterator is not a mutable reference to a Vec, then A itself is the only mutable reference, and push back should be allowed.

Because vec.push has signature push(&mut self, value) https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pus...

That means you can think of it as push(&mut vec, 5) - you need to pass a mutable reference to the vec as the first a argument and the iterator is already holding one of them. So you're not allowed to.

You are allowed at most one mutable reference or multiple immutable references. Additionally, taking an immutable reference locks the object from mutation (and taking a mutable one locks it for reading from anywhere other than that reference).

The iterator is an immutable reference. push() is a mutating method. These don't work together.

Rust is "aliasing XOR mutability"

I'm pretty sure some cpp vector implementations use three pointers instead of length and capacity.

In the end, it's the same thing, isn't it? The amount of overhead is the same.

In the article, it sounded like there is actually a guarantee that the (pointer, integer, integer) representation is used in rust.

They are close to being equivalent, but maybe with weird-sized objects, the (pointer, pointer, pointer) version requires some divisions, and the other one only requires multiplications?

>> No iterator invalidation from iterators you get from it

> How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?

Rust's lifetimes.

> One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated.

Does C++ really not guarantee this? If yes then I probably have written quite a bit of "broken" code, which assumes that element addresses stay constant during moves of the container.

    std::vector<A> vec1; // And initialize it
    A* a = &vec1[0];
    auto vec2 = std::move(vec1);
    A* b = &vec2[0];
    assert(a == b);

> You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience.

I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?

> I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?

No, because Rust gives you the tools to compartmentalize this stuff pretty well. Yes, if you write an unsound program it will fail to compile, but the language also guides you in the direction of not writing one, so huge complicated codebases written in 100% safe rust are possible and do compile. With C++ as complexity grows it's harder to keep stuff safe, in my experience. YMMV.