Part 4: Templates, STL & Standard Library

1. Templates — compile-time generics

• Function templates deduced from args; class templates need explicit <T> usually.

template <typename T>
T max(T a, T b) { return a > b ? a : b; }

template <typename T, typename U>
struct Pair { T first; U second; };

• Instantiation happens at compile time — no runtime dispatch.
• Specialization: template <> ... for a specific type.
• decltype, auto, and deduction from trailing return types let you write generic code tersely.

2. Concepts (C++20)

template <typename T>
concept Numeric = std::is_arithmetic_v<T>;
template <Numeric T> T add(T a, T b) { return a + b; }

• Constraint-based overloads, better error messages that apply constraints at the call site.

3. STL containers — choose wisely

Container	Properties
vector	dynamic array, contiguous, O(1) push_back amortised
deque	double-ended, O(1) push/pop both ends
list	doubly-linked, O(1) insert/erase if you have an iterator
set/map	sorted, O(log n) find/insert
unordered_set/unordered_map	hash-based, avg O(1)
array	fixed-size, stack-friendly, std::array
string	contiguous buffer of chars

• vector is the default. If you just push_back, vector wins classically.
• Erasing from vector is O(n) (shift); prefer swap-and-pop when order doesn’t matter.

4. Iterators & algorithms

• Iterators model access: begin()/end(), rbegin/rend, cbegin/cend.
• Algorithms over hand loops: std::sort, std::find, std::count, std::accumulate, std::for_each, std::transform.
• Algorithm + lambda = clean, expressive code.

std::vector<int> v = {5, 2, 9, 1};
std::sort(v.begin(), v.end());          // [1 2 5 9]
auto found = std::find(v.begin(), v.end(), 5);
bool none_zero = std::none_of(v.begin(), v.end(), [](int x){ return x == 0; });

• Invalidation: inserting/erasing can invalidate iterators (vector reallocates; map all stable except erased).
• Range-based for (const auto& x : v) uses iterators internally.

5. string & iostreams

• std::string: size(), substr, find, append, stoi, to_string, s.resize.
• Line/structured input: cin >> x skips whitespace; getline reads a whole line.
• std::getline(cin, line) — line-based; mixing >> with getline leaves newline residue.

6. Interview checkpoint

• vector vs list — when each wins.
• unordered_map vs map; hashing requirements.
• Algorithm + lambda over manual loops.
• Iterator invalidation on vector push_back/erase.
• Template vs runtime polymorphism difference.