ReviseAlgo Logo

Arrays and Strings

Arrays

Fixed-size arrays in C++

Interview: Basic data structure

Arrays in C++

Arrays are contiguous blocks of memory storing fixed numbers of same-type elements. Being contiguous makes them cache-friendly — sequential access patterns benefit from CPU cache prefetching, making arrays among the fastest data structures for iteration.

Array Decay to Pointer

Arrays decay to a pointer to their first element when passed to functions. The size information is lost — the function receives only a T*. This is a major C heritage pitfall. Always use std::array or pass size explicitly to avoid this.

Stack vs Heap Arrays

Fixed-size arrays declared locally live on the stack (fast, auto-freed). Dynamic arrays (new int[n]) live on the heap (flexible size, must be manually deleted). Prefer std::vector over raw dynamic arrays for automatic memory management.

Interview Corner

Q: Why are arrays cache-friendly compared to linked lists?

A: Array elements are stored contiguously. When you access one element, the CPU loads an entire cache line (typically 64 bytes = 16 ints) into L1 cache. Subsequent sequential accesses hit the cache (near-zero cost). Linked list nodes are scattered across heap memory — each access may cause a cache miss, requiring expensive main memory fetch (~100ns vs ~1ns for cache hit).

Q: What happens when you access an array out of bounds in C++?

A: Undefined behavior — the standard places no requirement on what happens. The program may read garbage, corrupt adjacent memory, crash with a segfault, or appear to work correctly. Use std::array::at() for bounds-checked access (throws std::out_of_range). Enable AddressSanitizer during development to catch these bugs.

Common Pitfalls

  • Using sizeof on a decayed pointer: void f(int arr[]) { sizeof(arr); } gives the size of a pointer (8 bytes), not the array.
  • Variable-length arrays (VLAs): int arr[n] with runtime n is a C99 feature, not standard C++. Some compilers accept it as an extension, but it's non-portable. Use std::vector instead.

Best Practices

  • Prefer std::array<T, N> over raw arrays for fixed-size — it doesn't decay, carries its size, and works with STL algorithms.
  • Use std::vector<T> for dynamic sizing with automatic memory management.