Why is vec in different namespace than LinkedList

Vec is in std::vec::Vec, LinkedList is in std::collections::LinkedList.
Both of those data structures are containers. What is the reason that they are both not in std::collections?

1 Like

Because the Vec<T> is so universal while the LinkedList<T> is for niche use case. Vec<T> should be your default choice if you need zero or more data of same type. If you want LinkedList<T>, try reconsider it again.

In most case the Vec<T> is faster due to the cache locality. Modern CPUs have near-megabyte of L1 cache. If your entire data would fits within the CPU cache, not necessarily for L1 but including the larger levels, the vector would outperform the linked list on pushing to the front which is the slowest operation of the vector and the fastest operation of the linked list.

This all is true, but doesn't explain why it isn't std::collections::Vec though. As Vec in prelude anyway and cases where you need std::vec::Iter are exceedingly rare, that wouldln't really hurt ergonomics.

1 Like

My guess is that the answer can be summarized in one word: "history". :grinning:

4 Likes

Historical reasons: Originally, collections was a separate crate from std, but vec had to be in std so that other std APIs could use it. (collections depended on std rather than the other way around.)

This separation could have been fixed after all of these types were moved to the alloc crate and re-exported from std, but it wasn't.

7 Likes

Thank you for your answer.
That is somewhat saddening. The reason for this is that at such an early stage, when there is a still chance to keep the language clean, there is already so many "historical or other" reasons to have somewhat messy from the beginning state of affairs.

Graydon Hoare began work on Rust in 2006. Rust was announced in 2010. Rust 1.0 was released in 2015. How good is your foresight over such long time-spans?

3 Likes

For some context: Rust was first released more than a decade ago (in July, 2010). The rearrangement of the std crate happened several years later, in mid-2014. At that time, the Rust team was already pushing toward a 1.0 release (which ended up happening in early 2015) and working hard to stabilize APIs and stop breaking existing code except when absolutely necessary.

This meant freezing some APIs in less-than-perfect states, but the resulting stability was absolutely crucial for getting people to actually adopt Rust, resulting in the ecosystem and community that we have today.

3 Likes

To me this is simply organizing your work correctly from the beginning, not start working and hope that there will be time to sort/clean/fix things later. And as we already see - there isn't. It is not a surprise for anybody who works more than a year in widely understood IT sector.

Well put.

Putting Vec in a separate module makes sense to me, since Vec is much more fundamental than the other collections. Just like the primitive integer types aren't in std::num.

Putting it in std::collections is fine too. It's fine either way.

I disagree. HashMap is also fundamental, if not more fundamental and more commonly used than vector.

Drive by comment, but is there a real disagreement here? It seems like what is proposed is std::collections::vec, with re-exports of Vec in predlude and std::collections, and this seems to satisfy everyone?

Yep. What is the status of the proposal?

From the viewpoint of a system language, Vec is the owned counterpart to contiguous slices, which are essential in memory control. Memory management and pointer arithmetic run directly on contiguous memory. HashMap is less fundamental in this sense, and is far from as prevalent as Vec IMO. So I guess it's the reason that std::vec is a separate module, at least initially.

Similar arguments can be made for collections::Vec too, from a more mathematical viewpoint.

At the end of the day, the placement probably comes off as a minor issue that is probably not worth adjustment at this stage (or during the 1.0 days, for that matter). So the status is basically "nonexistent." Feel free to post in IRLO and see how it gets received :slight_smile:

Nahh.. probably like here, most people won't think it is either important or relevant.
I don't care. Not my language, not my problem. I'm just an user.

Removing module from existing path is breaking change, which the Rust will not make in decades. Only possible option is to pub use the std::vec within the std::collections, but I don't think it's a good idea.

And why wouldn't it be a good idea?

Well, we could do the opposite (move the implementation to alloc::collections and re-export it from alloc::vec and std::vec), right? Unless that breaks dependencies somehow in a way I'm not anticipating.

Then over two editions deprecate and eventually remove std::vec.

Honestly I forget std::vec even exists. Vec is in the prelude because virtually every nontrivial program uses it. But I can see where it might be an annoyance if you are in no_std land but still using alloc, I guess.

I thought it's obvious, but maybe it's just to me. Both locations has reasonable path so it's not clear for users which one is an alias to the another, or worse, they may think both are separate implementation with (confusingly) same name. I don't think having two locations make them more consistent, but it definitely can confuses newcommers.