# What would be your opinion on including an associated list in std::collection?

**URL:** <https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001>\
**Category:** language design\
**Created:** [December 8, 2023, 9:55pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001 "2023-12-08T21:55:21Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 8, 2023, 9:55pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/1 "2023-12-08T21:55:21Z")

</div>

I've had a discussion over at Rust community discord about what could theoretically be the `Dictionary` type, and realized that one of the options, that is probably the best for very small data sizes and has an advantage of only requiring ~~PartialEq~~ Eq for keys, is not included in the standard library.

---

<div class="post-metadata">

**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\
**Post date:** [December 8, 2023, 10:17pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/2 "2023-12-08T22:17:08Z")

</div>

What do you mean by "associated list", what would the API look like, and what are the benefits over the existing collections?

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 8, 2023, 10:18pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/3 "2023-12-08T22:18:54Z")

</div>

Basically a wrapper over `Vec<(K, V)>`, with a map-like API for insertion and removal. Benefit over both is not requiring either `Hash` nor ~~`Eq`~~ Cmp, and lack of indirection to the data. Tradeoff being, lookup and insertion are O(n) in size.

---

<div class="post-metadata">

**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\
**Post date:** [December 8, 2023, 11:17pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/4 "2023-12-08T23:17:48Z")

</div>

> [@HjVT](#):
>
> Benefit over both is not requiring either `Hash` nor `Eq`

How would it work without `Eq`? Do you mean `Ord`?

---

<div class="post-metadata">

**Author:** ![ExpHP](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/exphp/32/6208_2.png) [@ExpHP](https://internals.rust-lang.org/u/ExpHP)\
**Post date:** [December 8, 2023, 11:18pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/5 "2023-12-08T23:18:41Z")

</div>

Why would it only require PartialEq? Wouldn't that allow it to e.g. fill up with many `NaN` keys?

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [December 9, 2023, 12:13am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/6 "2023-12-09T00:13:10Z")

</div>

There's lots of possible spots in the trade-off spectrum, but not all of them need to be in `alloc`.

I think a `FlatMap<K, V>` being in a crate -- the same way a `SmallVec<T>` is just in a crate -- is fine.

Especially since `.iter().find(…)` works pretty well even without a wrapper.

---

<div class="post-metadata">

**Author:** ![tgross35](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tgross35/32/9550_2.png) [@tgross35](https://internals.rust-lang.org/u/tgross35)\
**Post date:** [December 9, 2023, 12:24am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/7 "2023-12-09T00:24:41Z")

</div>

I think the term VecMap is a little better because “dictionaries” in a lot of languages are our HashMap.

There is a crate that provides this [vecmap - Rust](https://docs.rs/vecmap-rs/latest/vecmap/)

I have definitely used this in the past, more lightweight than a HashMap and less indirection than a BTree. It wouldn’t be bad to have something easy to drop into place.

That being said, the implementation is so basic I’m not sure it merits a place in std. For `Ord` things, [`binary_search_by_key`](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search_by_key) already gives you the position to insert if lookup fails. For `!Ord` things, `.iter().find(…)` works. It’s trivial to write a few lines of code wrapper around either of these things to suite your application’s needs, without std needing to be opinionated about to Ord or not to Ord.

Maybe an example of these patterns in the book somewhere is a better fit than a new data type? Or maybe we could add methods to a `impl Vec<(K, V)>` without adding a new type, such as `get_or_insert`.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 9, 2023, 12:35am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/8 "2023-12-09T00:35:05Z")

</div>

As a previous art in adding methods to `Vec`, there's [`assoc`](https://docs.rs/assoc/latest/assoc/)

---

<div class="post-metadata">

**Author:** ![epage](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/epage/32/3171_2.png) [@epage](https://internals.rust-lang.org/u/epage)\
**Post date:** [December 9, 2023, 3:36am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/9 "2023-12-09T03:36:50Z")

</div>

For another example implementation to demonstrate different trade offs: [https://github.com/clap-rs/clap/blob/master/clap\_builder/src/util/flat\_map.rs](https://github.com/clap-rs/clap/blob/master/clap_builder/src/util/flat_map.rs)

This is a `(Vec<K>, Vec<V>)`

- Better cache locality for key lookups
- Smaller binary size because you are more likely to share monomorphized `Vec` code

---

<div class="post-metadata">

**Author:** ![dhardy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/dhardy/32/2399_2.png) [@dhardy](https://internals.rust-lang.org/u/dhardy)\
**Post date:** [December 10, 2023, 6:38pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/10 "2023-12-10T18:38:48Z")

</div>

There's also [linear-map](https://crates.io/crates/linear-map) which (according to Cargo) is more popular, but old and unmaintained (thus e.g. `fn Entry::or_default` is missing).

Something I have used, if a little niche. However, it's simple and a decent choice of "map" type when the length is known to be very small, so... either including or not including seems fine IMO.

---

<div class="post-metadata">

**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\
**Post date:** [December 11, 2023, 2:05pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/11 "2023-12-11T14:05:19Z")

</div>

> [@epage](#):
>
> For another example implementation to demonstrate different trade offs: [https://github.com/clap-rs/clap/blob/master/clap\_builder/src/util/flat\_map.rs](https://github.com/clap-rs/clap/blob/master/clap_builder/src/util/flat_map.rs)

And on another axis this gets very close to various DataFrame/Series implementations.

---

<div class="post-metadata">

**Author:** ![zackw](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zackw/32/2071_2.png) [@zackw](https://internals.rust-lang.org/u/zackw)\
**Post date:** [December 12, 2023, 6:41pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/12 "2023-12-12T18:41:46Z")

</div>

Nitpick: the term for this in Lisp is "associat **ion** list" or "pairlist", not "associated list". And I think "associated list" sounds too much like "associated type" for clarity.

"The key type only needs to be `Eq`, not `Ord` or `Hash`" seems like a solid reason to add this to the stdlib: if you know you need a map where the keys only have to be `Eq`, but you don't know what this is usually called, and you have to hunt for something in `crates.io`, it could be quite hard to find. I don't know if it's a solid _enough_ reason, especially considering the `Vec<(K,V)>` vs `(Vec<K>, Vec<V>)` tradeoffs.

---

<div class="post-metadata">

**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\
**Post date:** [December 12, 2023, 7:39pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/13 "2023-12-12T19:39:12Z")

</div>

I will note that it's also possible to make a variant which uses a single allocation while holding keys and values in a more optimal way. Essentially `Box<([K; n], [V; n])>`

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 13, 2023, 1:14am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/14 "2023-12-13T01:14:56Z")

</div>

Im not too sure it's actually more optimal, having worked on and benchmarked a similarly laid out container, my gut tells me it will be within margin of more naive 2 Vec approach. While complexity of bookkeeping forsuch an allocation is not insignificant.

---

<div class="post-metadata">

**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\
**Post date:** [December 13, 2023, 4:55am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/15 "2023-12-13T04:55:27Z")

</div>

What bookkeeping? All you have to do is store two pointers, one capacity, and one length which is practically the same as the `(Vec<K>, Vec<V>)` case. All of the tricky stuff you only have to deal with on reallocation.

That said, I don't expect it to be much faster unless you keep the whole structure within a single cache line or something.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 13, 2023, 5:24am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/16 "2023-12-13T05:24:10Z")

</div>

Capacity is a bit tricky to decide. Also keys and values could easily have different alignment requirements.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [December 13, 2023, 5:46am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/17 "2023-12-13T05:46:16Z")

</div>

> [@HjVT](#):
>
> Also keys and values could easily have different alignment requirements.

It's not that big of a deal. You can do

```rust
use std::alloc::{Layout, LayoutError};
pub fn layout<K, V>(cap: usize) -> Result<(Layout, usize), LayoutError> {
    let a = Layout::array::<K>(cap)?;
    a.extend(Layout::array::<V>(cap)?)
}

```

to get the allocation size & alignment needed and the offset to the array of values.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 13, 2023, 5:59am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/18 "2023-12-13T05:59:12Z")

</div>

But this ignores possible over-allocation.

---

<div class="post-metadata">

**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\
**Post date:** [December 13, 2023, 4:14pm UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/19 "2023-12-13T16:14:52Z")

</div>

> [@HjVT](#):
>
> Capacity is a bit tricky to decide.

Why? The capacity can just be treated like length. Same for both component arrays.

> [@HjVT](#):
>
> But this ignores possible over-allocation.

What do you mean by over-allocation? Rust allocators don't return the size of the actual allocation, so all you can assume is that it's at least the size you asked for.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [December 14, 2023, 1:45am UTC](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001/20 "2023-12-14T01:45:34Z")

</div>

Unstable `Allocator` trait in fact does return length.

[Next page](https://internals.rust-lang.org/t/what-would-be-your-opinion-on-including-an-associated-list-in-std-collection/20001.md?page=2)