Rust Associated Types or Generics?

Associated types and generic parameters are two ways to name a type in a trait. The deciding question is who chooses the type.

The associated-type shape

degree needs one letter, G. The node type is read off G itself, written G::Node. It is never a separate parameter:

trait Graph {
    type Node;
    type Edge;
    fn neighbours(&self, node: Self::Node) -> Vec<Self::Node>;
}
fn degree<G: Graph>(graph: &G, node: G::Node) -> usize {
    graph.neighbours(node).len()
}

The same graph as a generic trait

Make the trait generic instead. Every helper must then carry N and E as its own parameters. Each helper must also repeat them in the bound. One type could now implement GraphG several ways — power you pay for in every signature:

trait GraphG<N, E> {
    fn neighbours(&self, node: N) -> Vec<N>;
}
fn degree_g<G, N, E>(graph: &G, node: N) -> usize
where
    G: GraphG<N, E>,
{
    graph.neighbours(node).len()
}

Associated constants ride along

A trait may also fix a value per type: an associated constant. Each implementor states it once, and generic code reads it as S::SIDES:

trait ShapeInfo {
    const SIDES: u32;
    fn name(&self) -> &'static str;
}
fn report<S: ShapeInfo>(shape: &S) {
    println!("{} has {} sides", shape.name(), S::SIDES);
}
report(&Triangle);
report(&Square);

Awareness: an associated type with a lifetime

Since Rust 1.65, an associated type may itself be generic — here over a lifetime. These generic associated types are how an iterator can hand out references into itself. Ordinary code rarely defines one, but library traits use them:

trait LendingIterator {
    type Item<'a>
    where
        Self: 'a;
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

Example

trait Graph {
    type Node;
    type Edge;
    fn neighbours(&self, node: Self::Node) -> Vec<Self::Node>;
}

struct CityMap {
    links: Vec<(u32, u32)>,
}

impl Graph for CityMap {
    type Node = u32;
    type Edge = (u32, u32);
    fn neighbours(&self, node: u32) -> Vec<u32> {
        let mut found = Vec::new();
        for &(a, b) in &self.links {
            if a == node {
                found.push(b);
            }
            if b == node {
                found.push(a);
            }
        }
        found
    }
}

fn degree<G: Graph>(graph: &G, node: G::Node) -> usize {
    graph.neighbours(node).len()
}

fn main() {
    let map = CityMap { links: vec![(1, 2), (2, 3), (1, 3), (3, 4)] };
    println!("neighbours of 3: {:?}", map.neighbours(3));
    println!("degree of 3 = {}", degree(&map, 3));
    println!("degree of 4 = {}", degree(&map, 4));
}

Key points

The deciding question is who chooses the type.
The implementor chooses once, for an associated type.
Or the caller chooses at each use, for a generic parameter.
Many impls for one type means a generic parameter: String implements From<&str>, From<char> and more — one impl per source type
Exactly one sensible choice per type means an associated type.
A given map has one kind of node.
A given iterator has one kind of item.
With an associated type, callers read it through the implementor — G::Node — so no extra letters travel through every signature
With a generic trait, the letters are part of the trait name.
They must be repeated everywhere.
Graph<N, E> follows you into each function.
Operator traits mix both on purpose.
Add<RHS = Self> is generic over the right-hand side, with Self as the default.
Its Output is an associated type.

In this example, Graph leaves two blanks: Node and Edge. CityMap fills them in once. Node is u32. Edge is a pair of u32. Its neighbours method walks the links both ways. It collects 2, 1 and 4 for node 3, in link order. degree is the payoff of the design. It is generic only over G. It takes the node as G::Node. That is a type it reads off the graph itself. Node 3 has three neighbours. Node 4 has one. So the prints read degree of 3 = 3 and degree of 4 = 1. Had Graph been generic, degree would have needed N and E parameters of its own. Those would exist for a second impl of CityMap. That second impl could never exist.

Note

When in doubt, count the impls.

If a second impl for the same type would make sense one day, choose the generic parameter.

If it would be nonsense, choose the associated type.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

trait Graph {
    type Node;
    type Edge;
    fn neighbours(&self, node: Self::Node) -> Vec<Self::Node>;
}

struct CityMap {
    links: Vec<(u32, u32)>,
}

impl Graph for CityMap {
    type Node = u32;
    type Edge = (u32, u32);
    fn neighbours(&self, node: u32) -> Vec<u32> {
        let mut found = Vec::new();
        for &(a, b) in &self.links {
            if a == node {
                found.push(b);
            }
            if b == node {
                found.push(a);
            }
        }
        found
    }
}

fn degree<G: Graph>(graph: &G, node: G::Node) -> usize {
    graph.neighbours(node).len()
}

fn main() {
    let map = CityMap { links: vec![(1, 2), (2, 3), (1, 3), (3, 4)] };
    println!("neighbours of 3: {:?}", map.neighbours(3));
    println!("degree of 3 = {}", degree(&map, 3));
    println!("degree of 4 = {}", degree(&map, 4));
}

Exercise

You are designing a Converter trait, and one struct should convert from many different input types. Which tool fits?

An associated type Input A generic parameter: trait Converter<From> An associated constant A marker trait