Unit-like structs in Rust - Time & Space Complexity

Time Complexity: Unit-like structs

O(n)

Understanding Time Complexity

Let's explore how the time it takes to run code with unit-like structs changes as we use more of them.

We want to know how the program's work grows when we create or use many unit-like structs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Marker;

fn create_markers(n: usize) -> Vec<Marker> {
    let mut v = Vec::new();
    for _ in 0..n {
        v.push(Marker);
    }
    v
}

This code creates a list of n unit-like structs called Marker.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that runs n times to create and add Marker structs.
• How many times: Exactly n times, once for each struct created.

How Execution Grows With Input

As n grows, the number of times we create and add structs grows the same way.

Input Size (n)	Approx. Operations
10	10 creations and insertions
100	100 creations and insertions
1000	1000 creations and insertions

Pattern observation: The work grows directly in step with n. Double n, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create n unit-like structs grows in a straight line with n.

Common Mistake

[X] Wrong: "Creating unit-like structs is instant and does not add to time as n grows."

[OK] Correct: Even though unit-like structs hold no data, creating and storing many of them still takes time proportional to how many you make.

Interview Connect

Understanding how simple data structures like unit-like structs affect performance helps you explain your code choices clearly and confidently.

Self-Check

"What if we changed the loop to create two unit-like structs per iteration? How would the time complexity change?"

Practice

1. What is a unit-like struct in Rust?

easy

A. A struct that can only be used inside functions.

B. A struct with exactly one field.

C. A struct that holds only unit type values.

D. A struct without any fields, used as a marker.

Solution

1. Step 1: Understand struct definitions

   Structs in Rust can have fields or no fields. A unit-like struct has no fields.

2. Step 2: Identify the purpose of unit-like structs

   They are used as markers or labels without storing data.

3. Final Answer:

   A struct without any fields, used as a marker. -> Option D

4. Quick Check:

   Unit-like struct = marker struct [OK]

Hint: No fields means unit-like struct, used as marker [OK]

Common Mistakes:

• Thinking unit-like structs must have fields
• Confusing unit-like structs with tuple structs
• Assuming unit-like structs hold unit type values

2. Which of the following is the correct syntax to declare a unit-like struct named Marker in Rust?

easy

A. struct Marker;

B. struct Marker();

C. struct Marker {}

D. struct Marker[];

Solution

1. Step 1: Recall unit-like struct syntax

   Unit-like structs are declared with just the name and a semicolon, no parentheses or braces.

2. Step 2: Compare options

   struct Marker; matches the syntax: struct Marker;

3. Final Answer:

   struct Marker; -> Option A

4. Quick Check:

   Unit-like struct syntax = struct Name; [OK]

Hint: Unit-like struct ends with semicolon, no braces [OK]

Common Mistakes:

• Using parentheses like tuple structs
• Using braces like normal structs
• Adding square brackets which are invalid

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

struct Flag;

impl Flag {
    fn is_set(&self) -> bool {
        true
    }
}

fn main() {
    let f = Flag;
    println!("{}", f.is_set());
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand the struct and method

   Flag is a unit-like struct with a method is_set that always returns true.

2. Step 2: Trace the main function

   We create an instance f of Flag and call f.is_set(), which returns true, printed as "true".

3. Final Answer:

   true -> Option B

4. Quick Check:

   Method returns true, output is true [OK]

Hint: Unit-like structs can have methods returning values [OK]

Common Mistakes:

• Expecting a compilation error due to no fields
• Thinking unit-like structs cannot have methods
• Confusing output with false or panic

4. Identify the error in this Rust code using a unit-like struct:

struct Label;

fn main() {
    let l = Label();
    println!("Label created");
}

medium

A. Unit-like structs must have at least one field.

B. Missing semicolon after struct declaration.

C. Unit-like structs cannot be instantiated with parentheses.

D. The println! macro is used incorrectly.

Solution

1. Step 1: Check struct instantiation

   Unit-like structs are instantiated without parentheses, just by name.

2. Step 2: Identify the error

   The code uses Label() which is invalid; it should be Label.

3. Final Answer:

   Unit-like structs cannot be instantiated with parentheses. -> Option C

4. Quick Check:

   Instantiate unit-like struct without () [OK]

Hint: Instantiate unit-like structs by name only, no () [OK]

Common Mistakes:

• Adding parentheses when creating unit-like struct instances
• Forgetting semicolon after struct declaration (not in this code)
• Misusing println! macro syntax

5. Given this code, what is the output?

struct Marker;

impl Marker {
    fn label(&self) -> &'static str {
        "Unit Marker"
    }
}

fn main() {
    let markers = vec![Marker, Marker];
    for m in markers {
        println!("{}", m.label());
    }
}

hard

A. Unit Marker\nUnit Marker

B. Compilation error due to vector of unit-like structs

C. Unit Marker printed once

D. Runtime panic due to missing fields

Solution

1. Step 1: Understand vector of unit-like structs

   Unit-like structs can be stored in vectors as they are zero-sized but valid types.

2. Step 2: Trace the loop and method calls

   The loop prints the label for each Marker instance, which returns "Unit Marker" twice.

3. Final Answer:

   Unit Marker\nUnit Marker -> Option A

4. Quick Check:

   Two markers print label twice [OK]

Hint: Unit-like structs can be stored and iterated like normal structs [OK]

Common Mistakes:

• Assuming unit-like structs cannot be stored in collections
• Expecting compilation error due to zero-sized type
• Thinking only one print occurs