Project 3: Dynamic Array

Build a vector-style dynamic array with resizing, push/pop, and bounds checks.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 1 week
Language C
Prerequisites Project 2, malloc/free
Key Topics Amortized growth, ownership, APIs

1. Learning Objectives

By completing this project, you will:

  1. Implement a resizable array with capacity management.
  2. Understand amortized time complexity.
  3. Design a C API for generic containers.
  4. Handle memory growth and shrink safely.

2. Theoretical Foundation

2.1 Core Concepts

  • Capacity vs size: Capacity is allocated space; size is used elements.
  • Amortized analysis: Doubling capacity makes average push O(1).
  • Ownership: The array owns its buffer; elements may be owned by user.

2.2 Why This Matters

Dynamic arrays are the most common building block in modern systems. This project teaches how efficient containers work under the hood.

2.3 Historical Context / Background

C has no built-in containers. Systems libraries implement dynamic arrays with manual resizing and careful memory management.

2.4 Common Misconceptions

  • “Realloc always moves memory”: It can extend in place.
  • “Capacity equals size”: They are separate.

3. Project Specification

3.1 What You Will Build

A Vec-style container that supports:

  • vec_init, vec_free
  • vec_push, vec_pop
  • vec_get, vec_set
  • vec_reserve, vec_shrink

3.2 Functional Requirements

  1. Start with a small capacity and grow as needed.
  2. Provide bounds-checked accessors.
  3. Support element sizes via void * and size_t elem_size.
  4. Return errors on allocation failures.

3.3 Non-Functional Requirements

  • Performance: Doubling strategy for growth.
  • Reliability: No memory leaks or invalid writes.
  • Usability: Clear documentation for ownership.

3.4 Example Usage / Output

Vec v;
vec_init(&v, sizeof(int));
int x = 10;
vec_push(&v, &x);
int *p = vec_get(&v, 0);
// *p == 10
vec_free(&v);

3.5 Real World Outcome

You can reuse this container for arrays of any type and reason about its resizing behavior. You understand why push is “usually” constant time.

4. Solution Architecture

4.1 High-Level Design

Vec { data, size, capacity, elem_size } -> API functions -> tests

4.2 Key Components

Component Responsibility Key Decisions
Vec struct Store metadata Size/capacity fields
Resizer Grow/shrink buffer realloc strategy
Accessors Read/write elements Bounds checks

4.3 Data Structures

typedef struct {
    void *data;
    size_t size;
    size_t capacity;
    size_t elem_size;
} Vec;

4.4 Algorithm Overview

Key Algorithm: Push

  1. If size == capacity, grow to max(1, capacity * 2).
  2. Copy element into buffer at data + size * elem_size.
  3. Increment size.

Complexity Analysis:

  • Push: Amortized O(1)
  • Get/Set: O(1)

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -O2 -g -o test_vec test_vec.c vec.c

5.2 Project Structure

vec/
├── src/
│   ├── vec.c
│   └── vec.h
├── tests/
│   └── test_vec.c
└── README.md

5.3 The Core Question You’re Answering

“How do you grow a contiguous buffer without breaking existing data?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. realloc semantics
    • What happens when realloc fails?
    • When does it move memory?
  2. Element size
    • How do you compute the byte offset for an index?
  3. Ownership
    • Who frees the elements inside the vector?

5.5 Questions to Guide Your Design

Before implementing, think through these:

  1. Will vec_get return a pointer or copy into user buffer?
  2. Should vec_pop return the element or just remove it?
  3. When should you shrink capacity?

5.6 Thinking Exercise

Amortized Growth

If you start with capacity 1 and double each time, how many total copies occur after 1,000 pushes?

5.7 The Interview Questions They’ll Ask

Prepare to answer these:

  1. “Why is doubling capacity efficient?”
  2. “What does realloc do if it cannot grow in place?”
  3. “How do you store elements of any type in C?”

5.8 Hints in Layers

Hint 1: Start with fixed capacity Implement push/pop without resizing.

Hint 2: Add resizing Use realloc when size hits capacity.

Hint 3: Add bounds checks Return an error if index is out of range.

5.9 Books That Will Help

Topic Book Chapter
Arrays and pointers “The C Programming Language” Ch. 5
Data structures “Algorithms in C” Arrays chapter

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

  • Core struct and init/free

Tasks:

  1. Implement vec_init and vec_free.

Checkpoint: No leaks in basic tests.

Phase 2: Core Functionality (2-3 days)

Goals:

  • Push and get

Tasks:

  1. Implement vec_push with resize.
  2. Implement vec_get.

Checkpoint: Push 1,000 items without failure.

Phase 3: Polish & Edge Cases (1-2 days)

Goals:

  • Pop and shrink

Tasks:

  1. Add vec_pop and optional shrink.

Checkpoint: Size and capacity behave predictably.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Growth factor 1.5x vs 2x 2x Simple and common
Shrinking Aggressive vs conservative Conservative Avoid thrashing

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests API correctness Push/get/set
Stress Tests Large pushes 100k items
Edge Cases Empty pop Return error

6.2 Critical Test Cases

  1. Push past capacity: Buffer grows correctly.
  2. Out-of-bounds get: Returns error.
  3. Pop from empty: Safe failure.

6.3 Test Data

Integers, structs, small strings

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Forgetting elem_size Corrupt data Store element size
Using realloc incorrectly Leaks Assign to temp first
Off-by-one access Crashes Check bounds

7.2 Debugging Strategies

  • Use valgrind to catch invalid writes.
  • Add asserts for size/capacity invariants.

7.3 Performance Traps

Shrinking too often makes push/pop expensive. Shrink only when size is far below capacity.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add vec_clear.
  • Add vec_insert at index.

8.2 Intermediate Extensions

  • Add iterator-style traversal.
  • Add vec_reserve.

8.3 Advanced Extensions

  • Implement small-buffer optimization.
  • Add thread-safe variant.

9. Real-World Connections

9.1 Industry Applications

  • Runtime systems: Dynamic arrays are everywhere.
  • Embedded: Often reimplemented due to constraints.
  • klib: Minimal C containers.

9.3 Interview Relevance

Dynamic array resizing and amortized analysis are common interview topics.

10. Resources

10.1 Essential Reading

  • “Algorithms in C” - Arrays chapter
  • “The C Programming Language” - Ch. 5

10.2 Video Resources

  • Data structures lectures (arrays and amortized analysis)

10.3 Tools & Documentation

  • man 3 realloc: Reallocation behavior
  • Linked List: Alternative dynamic container.
  • Hash Table: Uses dynamic arrays internally.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain amortized O(1).
  • I know how realloc behaves.
  • I can define ownership of elements.

11.2 Implementation

  • Vector resizes correctly.
  • No memory leaks or overflows.
  • API is documented.

11.3 Growth

  • I can add insertion and deletion features.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Supports init, push, get, free.

Full Completion:

  • Adds pop, reserve, and bounds checks.

Excellence (Going Above & Beyond):

  • Implements iterators and small-buffer optimization.

This guide was generated from C_PROGRAMMING_COMPLETE_MASTERY.md. For the complete learning path, see the parent directory.