skip to content

In a Rust `Cache<K, V>`, why put bounds like `K: Eq + Hash` on impl blocks instead of the struct, and how does a `dump()` method exist only for displayable caches?

level: seniorimportance: should knowfreq 35%

answer

  1. each impl block has its own bounds
  2. methods appear only when bounds hold
  3. how HashMap::new avoids key bounds
  4. struct bounds spread to every user

basics

~20 s

Bounds on an impl block apply only to that block's methods, so new and len stay bound-free while insert needs K: Eq + Hash and dump needs Display. Bounds on the struct itself must be restated by every impl and every generic user.

solid answer

~50 s

Each `impl` block carries its own bounds, and its methods exist for a given `Cache<K, V>` only when those bounds hold. `impl<K, V> Cache<K, V>` can give every cache `new` and `len`; `impl<K: Eq + Hash, V>` adds `insert` and `get`; `impl<K: Display, V: Display>` adds `dump`. Calling `dump` on a `Cache<u32, Vec<u8>>` fails with E0599, "the method `dump` exists for struct `Cache<u32, Vec<u8>>`, but its trait bounds were not satisfied", naming `Vec<u8>: std::fmt::Display`. std's `HashMap` is laid out the same way: `new` and `len` live in blocks without key bounds, `insert` under `K: Eq + Hash, S: BuildHasher`. Putting `K: Eq + Hash` on the struct instead forces every `impl` and every generic function or type that mentions `Cache<K, V>` to restate it, and the API Guidelines call adding a bound to a struct generally a breaking change for consumers. `#[derive(Clone)]` is itself a conditional impl, requiring `K: Clone, V: Clone`.

code

rust · 43 lines
rust
use std::collections::HashMap;
use std::fmt::Display;
use std::hash::Hash;

struct Cache<K, V> {
    entries: HashMap<K, V>,
}

impl<K, V> Cache<K, V> {
    fn new() -> Self {
        Cache { entries: HashMap::new() }
    }
    fn len(&self) -> usize {
        self.entries.len()
    }
}

impl<K: Eq + Hash, V> Cache<K, V> {
    fn insert(&mut self, key: K, value: V) {
        self.entries.insert(key, value);
    }
    fn get(&self, key: &K) -> Option<&V> {
        self.entries.get(key)
    }
}

impl<K: Display, V: Display> Cache<K, V> {
    fn dump(&self) {
        for (k, v) in &self.entries {
            println!("{k} = {v}");
        }
    }
}

fn main() {
    let mut prices: Cache<String, f64> = Cache::new();
    prices.insert("tea".to_string(), 2.5);
    prices.dump();

    let mut blobs: Cache<u32, Vec<u8>> = Cache::new();
    blobs.insert(7, vec![1, 2]);
    println!("{} {:?}", blobs.len(), blobs.get(&7));
}

go deeper

for a junior

Recall that an impl block can declare its own bounds, and that its methods exist only for types meeting them.

for a middle

Explain how E0599 reports a method whose impl-block bounds are not satisfied, and how derives add bounds on every type parameter.

for a senior

Lay out generic types the way HashMap is laid out: no bounds on the struct, minimal bounds per impl block, and manual impls where a derive over-constrains.

for a principal

Guard public types against bound creep: a struct bound is a semver commitment for every consumer, so require a stated reason, such as an associated type or Drop, before accepting one.

## Bounds belong to impl blocks A generic struct such as `struct Cache<K, V> { entries: HashMap<K, V> }` can carry **no bounds at all**. Its methods are then split across several `impl` blocks, each declaring exactly the bounds its methods need: | `impl` block | Bounds | Methods it adds | |---|---|---| | `impl<K, V> Cache<K, V>` | none | `new`, `len` | | `impl<K: Eq + Hash, V> Cache<K, V>` | key can be hashed and compared | `insert`, `get` | | `impl<K: Display, V: Display> Cache<K, V>` | both printable | `dump` | This is a **conditional impl**: the methods of a block exist for a particular instantiation only when its bounds hold for that instantiation's types. The Rust Book shows the same pattern with a `Pair<T>` whose `cmp_display` method exists only when `T: Display + PartialOrd`. ## What callers see For a `Cache<String, f64>`, every block applies, so `insert` and `dump` both work. For a `Cache<u32, Vec<u8>>`: - `new`, `len`, `insert` and `get` work, because `u32: Eq + Hash`; - `dump` is rejected with **E0599**: "the method `dump` exists for struct `Cache<u32, Vec<u8>>`, but its trait bounds were not satisfied"; - the note points at the unmet bound, "trait bound `Vec<u8>: std::fmt::Display` was not satisfied", and at the `impl` line that introduced it. Nothing happens at run time: a method whose bounds do not hold is simply absent for that type, and the compiler says why. ## The standard library does the same `std::collections::HashMap` is declared with no bound on `K` or `V`. In the 1.99.1 sources: - `HashMap::new` sits in `impl<K, V> HashMap<K, V, RandomState>`, with no key bound, so an empty map of any key type can be created; - `len` sits in an `impl` block whose only bound is on the allocator parameter, not on `K` or `V`; - `insert` and `reserve` sit in an `impl<K, V, S, A> HashMap<K, V, S, A>` block whose `where` clause requires `K: Eq + Hash` and `S: BuildHasher` (plus the allocator bound), because they need to hash; - `Clone` for `HashMap` is a conditional trait impl, requiring `K: Clone`, `V: Clone` and `S: Clone`. ## Why not bound the struct Writing `struct Cache<K: Eq + Hash, V>` looks tidier, but it costs every user of the type: 1. **Every `impl` must restate it.** A bare `impl<K, V> Cache<K, V>` then fails with **E0277**, "the trait bound `K: Eq` is not satisfied", with the note "required by a bound in `Cache`", even for a `len` method that never hashes. 2. **Every generic user must restate it.** A function taking `Cache<K, V>` or a struct holding one has to repeat `K: Eq + Hash` for its own signature to be well-formed. 3. **It is a compatibility hazard.** The Rust API Guidelines (C-STRUCT-BOUNDS) say generic data structures should not use bounds that can be derived or add no semantic value, and that adding a bound to a data structure is generally a breaking change, because every consumer must start satisfying it. The Guidelines list three exceptions where a bound on the struct is required: the struct refers to an associated type of the trait, the bound is `?Sized`, or the struct has a `Drop` impl that needs the bound, since a `Drop` impl's bounds must also appear on the struct. ## Derives are conditional impls too `#[derive(Clone)]` on `Cache<K, V>` generates an impl bounded by `K: Clone` and `V: Clone`. So a `Cache<u32, Handle>` where `Handle` is not `Clone` cannot call `.clone()`: rustc reports E0599 with "type parameter would need to implement `Clone`" and adds the hint to consider manually implementing the trait to avoid undesired bounds. Here the bound is genuinely needed, because cloning a `HashMap<K, V>` clones every key and value. It becomes over-restrictive for a field like `Arc<T>`, which is `Clone` for any `T`; there a hand-written `impl<T> Clone` is the fix. ## Conditional trait impls The same mechanism works for traits: `impl<K: Display, V: Display> fmt::Display for Cache<K, V>` makes `Cache` printable only when both parameters are, and std's `impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A>` is the familiar precedent. An impl for every `T` that meets a bound, regardless of the type, is a blanket impl, whose overlap rules are covered with coherence.

  • Why does `#[derive(Clone)]` on `Cache<K, V>` refuse to clone a `Cache<u32, Handle>` when `Handle` is not `Clone`?
    The derive generates `impl<K: Clone, V: Clone> Clone for Cache<K, V>`, so `clone` exists only when both parameters are `Clone`. rustc reports E0599 and notes the type parameter would need to implement `Clone`. For a `HashMap` field that bound is real, since cloning the map clones every value; for an `Arc<T>` field it is not, and a manual impl removes it.
  • If the struct is declared `Cache<K: Eq + Hash, V>`, what happens to a plain `impl<K, V> Cache<K, V>` holding only `len`?
    It fails with E0277, "the trait bound `K: Eq` is not satisfied" and the same for `Hash`, each noted as required by a bound in `Cache`. The impl must restate `K: Eq + Hash` even though `len` never hashes, and so must every generic function or type that names `Cache<K, V>`.
  • Can a trait implementation be conditional on the parameters, the way a method block is?
    Yes. `impl<K: Display, V: Display> fmt::Display for Cache<K, V>` makes the cache printable, and gives it `to_string`, only when both parameters are `Display`. std's `impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A>` works the same way.

  • Bounds must go on the struct, or the impl blocks cannot use them.
  • Calling a method from a bounded impl block on the wrong types panics at run time.
  • Adding a trait bound to a public struct later is a compatible change.
  • derive(Clone) makes any Cache<K, V> cloneable, whatever K and V implement.
  • Splitting methods across several impl blocks adds run-time overhead.