Generic structs in Rust - Time & Space Complexity

Time Complexity: Generic structs

O(1)

Understanding Time Complexity

Let's see how the time it takes to run code with generic structs changes as we use more data.

We want to know how the program's work grows when the input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Container<T> {
    items: Vec<T>,
}

impl<T> Container<T> {
    fn count_items(&self) -> usize {
        self.items.len()
    }
}

This code defines a generic struct holding a list of items and a method to count them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the length of the vector.
• How many times: The length is retrieved once without looping.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	1 (length check)
100	1 (length check)
1000	1 (length check)

Pattern observation: The operation count stays the same no matter how many items are in the container.

Final Time Complexity

Time Complexity: O(1)

This means the time to count items does not grow with more items; it stays constant.

Common Mistake

[X] Wrong: "Counting items in a generic struct always takes longer if there are more items."

[OK] Correct: The length method just returns a stored number, so it takes the same time no matter the size.

Interview Connect

Understanding how generic structs work with time helps you explain your code clearly and shows you know how data size affects speed.

Self-Check

"What if the count_items method instead summed a value from each item? How would the time complexity change?"

Practice

1. What does the <T> mean in the definition of a generic struct in Rust?

easy

A. It specifies a fixed type that the struct must always use.

B. It declares a placeholder type that can be replaced with any type when used.

C. It is used to define a function inside the struct.

D. It marks the struct as unsafe to use.

Solution

1. Step 1: Understand generic type parameters

   The <T> syntax declares a generic type parameter named T, which acts as a placeholder for any type.

2. Step 2: Recognize its purpose in structs

   This allows the struct to be flexible and work with any data type specified when creating an instance.

3. Final Answer:

   It declares a placeholder type that can be replaced with any type when used. -> Option B

4. Quick Check:

   Generic type parameter = placeholder type [OK]

Hint: Generic <T> means flexible type placeholder [OK]

Common Mistakes:

• Thinking <T> fixes the type permanently
• Confusing <T> with function syntax
• Assuming <T> makes the struct unsafe

2. Which of the following is the correct syntax to define a generic struct named Container with one generic type parameter T?

easy

A. struct Container<T> { value: T }

B. struct Container { T value }

C. struct Container<T> (value: T);

D. struct Container<T> = { value: T };

Solution

1. Step 1: Recall Rust struct syntax with generics

   Generic structs use struct Name<T> { field: T } syntax.

2. Step 2: Check each option

   struct Container<T> { value: T } matches the correct syntax with curly braces and generic parameter T. Options A, B, and D have syntax errors or wrong struct declaration styles.

3. Final Answer:

   struct Container<T> { value: T } -> Option A

4. Quick Check:

   Correct generic struct syntax = struct Container<T> { value: T } [OK]

Hint: Use struct Name<T> { field: T } for generic structs [OK]

Common Mistakes:

• Omitting angle brackets around T
• Using parentheses instead of braces
• Trying to assign struct with '='

3. What will be the output of this Rust code?

struct Pair<T> {
    first: T,
    second: T,
}

fn main() {
    let pair = Pair { first: 5, second: 10 };
    println!("{} and {}", pair.first, pair.second);
}

medium

A. 5 and 10

B. Pair { first: 5, second: 10 }

C. Compilation error due to missing type annotation

D. Runtime error

Solution

1. Step 1: Understand struct instantiation with generics

   The struct Pair is instantiated with integers 5 and 10, so T is inferred as i32.

2. Step 2: Analyze the println! macro output

   The macro prints the values of pair.first and pair.second separated by " and ".

3. Final Answer:

   5 and 10 -> Option A

4. Quick Check:

   Printing struct fields = 5 and 10 [OK]

Hint: Generic type inferred from values; prints fields directly [OK]

Common Mistakes:

• Expecting struct debug print without {:?}
• Thinking type annotation is mandatory here
• Assuming runtime error without reason

4. Identify the error in this generic struct code and choose the fix:

struct Wrapper<T> {
    value: T
}

fn main() {
    let w: Wrapper = Wrapper { value: 42 };
}

medium

A. Wrapper struct must have a lifetime parameter

B. Missing semicolon after struct field declaration

C. Cannot assign integer to generic type T

D. Missing generic type parameter in variable declaration: use Wrapper<i32>

Solution

1. Step 1: Check struct usage with generics

   The variable w is declared as Wrapper without specifying the generic type <T>, which is required.

2. Step 2: Fix by specifying the type

   Adding <i32> to Wrapper in the declaration fixes the error: let w: Wrapper<i32> = ....

3. Final Answer:

   Missing generic type parameter in variable declaration: use Wrapper<i32> -> Option D

4. Quick Check:

   Specify generic type when declaring variables [OK]

Hint: Always specify generic type when declaring variables [OK]

Common Mistakes:

• Forgetting to add <T> in variable type
• Thinking semicolon is missing after field
• Assuming lifetime needed without context

5. Given this generic struct and function, what is the output?

struct Container<T> {
    item: T,
}

impl<T> Container<T> {
    fn new(item: T) -> Self {
        Container { item }
    }

    fn describe(&self) -> String {
        match &self.item {
            i if i.is::<i32>() => "Integer container".to_string(),
            _ => "Other container".to_string(),
        }
    }
}

fn main() {
    let c = Container::new(100);
    println!("{}", c.describe());
}

hard

A. Integer container

B. Other container

C. Compilation error due to is::<i32>() usage

D. Runtime panic

Solution

1. Step 1: Analyze the use of is::<i32>() in match

   The method is::<i32>() does not exist on generic references in Rust; this causes a compilation error.

2. Step 2: Understand Rust type checking limitations

   Rust does not support runtime type checking like is::<i32>() on generic types without special traits or macros.

3. Final Answer:

   Compilation error due to is::<i32>() usage -> Option C

4. Quick Check:

   Rust generics lack runtime type checks like is::<Type>() [OK]

Hint: Rust generics can't check type at runtime without traits [OK]

Common Mistakes:

• Assuming is::<Type>() works on generics
• Expecting output without compilation errors
• Ignoring Rust's static typing rules