# C++ Fundamentals: `const` with Pointers, and `map` vs `unordered_map` You are in a C++ fundamentals screening round. After the coding question, the interviewer probes your understanding of the language with two short questions. Answer each precisely, with concrete examples, and be ready to justify the trade-offs. ### Constraints & Assumptions - Standard C++ (C++11 or later); answers should hold for a typical implementation (e.g., libstdc++ / libc++) of the standard library. - "`map`" and "`unordered_map`" refer to `std::map` and `std::unordered_map` from the `<map>` and `<unordered_map>` headers. - The interviewer is looking for precise mechanics and the reasoning behind the trade-offs, not just a memorized one-liner. ### Clarifying Questions to Ask - For the pointer question: should I also cover the third combination (`const int* const`) and the right-to-left reading rule, or only the two named declarations? - For the container question: do you want the asymptotic complexities, the underlying data structures, or the practical "when would you pick each" guidance — or all three? - Should I mention iterator/reference invalidation behavior, since that often drives the choice in real code? ### Part 1 Explain the difference between `const int*` and `int* const`. State precisely what is immutable in each case, what you are still allowed to do, and give a short code snippet showing which assignments compile and which do not. Also explain how to read such declarations in general (including `const int* const`). ```hint Reading rule Read pointer declarations **right to left**, and remember that `const` binds to the token on its **left** — unless `const` is the left-most token, in which case it binds to the type on its right. So `const int*` $\equiv$ `int const*`. ``` ```hint What is frozen In one case the *pointee* (the `int` being pointed at) is read-only; in the other the *pointer variable itself* is read-only (cannot be re-seated). Ask: "which assignment fails to compile — `*p = ...` or `p = ...`?" ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2 Explain the difference between `std::map` and `std::unordered_map`. Cover the underlying data structure, the complexity of the core operations, ordering guarantees, the requirements they place on the key type, and when you would choose one over the other. ```hint Two axes Frame it along two axes: (1) **how elements are organized** — a balanced search tree (ordered) vs a hash table (unordered) — and (2) what that buys/costs you: ordering & worst-case bounds vs raw average-case speed. ``` ```hint Key requirements Think about what each container needs *from the key type*: one needs a way to **order** keys, the other needs a way to **hash and compare** keys for equality. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - In Part 1, what does `const int* const p` mean, and where must it be initialized? What about a `const` member function — what does the trailing `const` make immutable? - For `unordered_map`, what happens to iterators and to references/pointers to existing elements when an insertion triggers a rehash? How does `load_factor`/`max_load_factor` relate to this? - If you needed the keys iterated in sorted order *and* fast average lookups, how would you get both? (e.g., maintain both structures, or sort on demand — discuss the trade-offs.) - How would an adversary degrade an `unordered_map` to $O(n)$ per operation, and how do real implementations or you as the author defend against it?