12 ms·

> 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

> 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.

pbsd 9y ago
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.
- Manishearth 9y ago
  aha! good to know. Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.
saagarjha 9y ago
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?
- Manishearth 9y ago
  The same thing. At compile time rust won't allow you to push to a vector if you have outstanding iterators.
  - Xorlev 9y ago
    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-is-ownership.html https://doc.rust-lang.org/book/second-edition/ch04-01-what-i...
  - kretin45 9y ago
    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?
    - Manishearth 9y ago
      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
      - kretin45 9y ago
        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.
- adrianN 9y ago
  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.
  - saagarjha 9y ago
    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.
blt 9y ago
I'm pretty sure some cpp vector implementations use three pointers instead of length and capacity.
- saagarjha 9y ago
  In the end, it's the same thing, isn't it? The amount of overhead is the same.
  - blt 9y ago
    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?

pbsd 9y ago

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.

Manishearth 9y ago
aha! good to know. Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.

saagarjha 9y ago

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?

Manishearth 9y ago
The same thing. At compile time rust won't allow you to push to a vector if you have outstanding iterators.
- Xorlev 9y ago
  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-is-ownership.html https://doc.rust-lang.org/book/second-edition/ch04-01-what-i...
- kretin45 9y ago
  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?
  - Manishearth 9y ago
    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
    - kretin45 9y ago
      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.
adrianN 9y ago
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.
- saagarjha 9y ago
  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.

blt 9y ago

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

saagarjha 9y ago
In the end, it's the same thing, isn't it? The amount of overhead is the same.
- blt 9y ago
  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?