[NEWBE] Does Rust have an "abstract map" trait?

Nothing turned up when searching for "rust abstract map trait" in Qwant. Looking at the BTreeMap docu, I fail to see something like that?

If I have a function that needs a map of KeyType to ValueType, I'd prefer not to fix the code on a specific map implementation, and instead have something like fun<M: AbstractMap<K, V>>(map: &M).

Sorry in advanced, in case it turns out that I'm blind on this issue.

The standard library doesn't include such a trait. It's possible you could find a crate that provides one, but I don't know of such a crate.

1 Like

Thanks for the reply. It's a little surprising to me. Wouldn't such a thing be useful?

Well I've never actually found the need for such a trait, but in either case there are lots of useful things that aren't in the standard library.

1 Like

In reality, collection interfaces (or, God forbid, entire hierarchies of them!) are a lot less useful than some people coming from other languages having them (e.g. Java, Python, Swift) assume.

Since a collection almost always implies a particular data structure, with a specific set of requirements and guarantees, one has to pretty much know the concrete type of the data structure in order to use it correctly and efficiently. For instance, while BTreeMap and HashMap are very similar in their API, there are obvious and important differences which are better not hidden behind a trait. For example, BTreeMap guarantees to sort keys, while HashMap doesn't. Thus, switching an implementation from BTreeMap to HashMap can actually break downstream code.


If you really-really want to be container-agnostic, create a newtype wrapper that privately hides either a HashMap or a BTreeMap and expose the necessary methods only in the public interface.

7 Likes

Thanks for the answer, but I don't really agree with the statement. I think it is possible to have a set of features that makes sense for the vast majority of associative map implementations on one hand, and on the other it makes sense to write code in a way that is agnostic to specific implementations, made explicit by such generic traits. Writing your own wrapper might be a good idea in a closed ecosystem. That said, as a newbie I don't want to complain in any way about rust or more informed opinions, I'm just surprised at the moment.

1 Like

I'm sure there are valid use-cases for a map trait, but in practice it is pretty rare.

What do you think should be in it?

  • map.get(&key)? Seems like the logical place to start. Well, the signature of HashMap::get isn't object-safe, though, and has different bounds than BTreeMap::get. Perhaps the trait should be generic over the query type Q, and each map should implement it for as many Qs as possible. Or maybe get should just take a &K, but then we have to convert a &str to String just to look it up. Or, obviously, we could just forego object safety entirely, which makes the idea of a trait less useful overall. :thinking:
  • map.insert(key, val)? Hmm, I guess we can't implement this trait for shared references or immutable collections. It would still work if implemented on a reference to a concurrent map.
  • map.get_mut(&key)? Wouldn't work if implemented on a reference to a concurrent map.
  • map[key]? Index exists.
  • map.into_iter()? IntoIterator exists.
  • map.iter() and iter_mut()? Not possible without GATs.
  • map.keys() and values()? Not possible without GATs.
  • map.entry(key)? Not possible without GATs.
  • map.append(&mut other_map)? BTreeMap has an efficient custom implementation of this; HashMap doesn't. Is it worth adding to Map, or is that uncommon enough that efficiency doesn't matter? We could make it a provided method, but that would require extend (Extend exists) and either drain (not possible without GATs) or default + into_iter (both exist).

The answer to many questions about why something isn't in the standard library is "nobody really knows or agrees on what it should do." There are a lot of decisions that go into making a sufficiently expressive, sufficiently general interface to be useful in a wide variety of contexts. Moreover, unlike in (say) Java, in Rust you can always write your own trait and add it to someone else's type. This doesn't completely obviate the usefulness of standard collections traits, but it greatly reduces the pressure on library authors to conform to them (both on the implementing and using sides).

18 Likes

Hm, you're using terms that I do not understand, unfortunately - object-safe, different bounds, GATs. I think I can follow the point with concurrent maps, which can be quite special. But, focusing on the most obvious one, I'm not able to follow you on map.get(&key), for example. Probably I don't understand Rusts type system entirely yet, but so far I can't see why any map shouldn't be able to deliver something like a nonmutable reference to the value for the key (if it exists) that is bound to the map (same life time, implying a nonmutable reference on the map)?

Thanks for the elaborated answer, by the way. And sorry for not having the brain to understand it entirely.

Being object-safe is required for trait objects. You can read more about it here.

GATs are Generic Associated Types, and they are used when writing generic code with types that make use of them. You can read more about it here.

Sounds fixable; you could Self: Sized bound the usual get, and add 2 additional versions that are

  • only accepting &K
  • accepting a trait object of some type &dyn BorrowFrom<K> that comes from a trait with an implementation T: BorrowFrom<K> where K: Borrow<T>

Covered by IntoIter for &Self and &mut Self,

in general, missing GATs for lifetimes only can be worked around:


Of course, the remaining points still stand :slight_smile:

Regarding GAT workarounds, it's true "not possible" is overstating a bit, but I suspect we can agree that it would be premature to stabilize any of those into std, since they will be obsoleted by planned language improvements (hopefully in the next year :crossed_fingers:).

@hcs, perhaps it wasn't clear, but the issues I mentioned are mostly not about whether any map type can implement them, but about the challenge of making the trait maximally useful so people will want to use it and not just roll their own. Anything that can reasonably be considered a "map" can implement fn get(&self, key: &K) -> &V. But that isn't necessarily the best signature for get, because it may force you to write less performant code in some cases unnecessarily, which makes Map not zero-cost. There are workarounds, but of course they all have their own tradeoffs. This is the kind of thing that would most likely have to be ironed out in a crate of collections traits before it would have a chance at inclusion in std.

Oh, I agree that it's absolutely a bad idea to put and stabilize a trait like that in std. On a more general note (ignoring e.g. the GATs issue), we don't even have a trait for numbers in std; how could be believe we can make one for maps and get it right the first time? I was mostly thinking about what could reasonably be used e.g. in some third-party crate that aims to become a common interface for map types.

Let's see how Java implements it. The java.util.AbstractMap<K, V> doesn't have any generic bounds on its type parameters. What happens if you .put() some key into the TreeMap which can't be compared? It throws ClassCastException. I don't think we can implement it similar to the Java without runtime type information.

3 Likes

Eve if we could (e.g. by having RTTI over trait bounds), it would be an entirely wrong direction to panic. That would pretty much defeat the advantages of a strong type system.

7 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.