# From C++ — the same containers under different names, and the three places the mapping lies

You know what a hash map is. What you need is the spelling, and the two names that map to nothing you
have used. Then the places where the obvious translation is wrong at run time rather than at compile
time. Every example below is the elevator: `corpus/elevator/`, floors 1..10, three lifts.

## The mapping table

| C++ | Java | The one thing that differs |
|---|---|---|
| `std::vector<T>` | `ArrayList<T>` | Grows the same way. No `reserve`, but `new ArrayList<>(64)` is the same idea |
| `std::deque<T>` | `ArrayDeque<T>` | Not a chunked array. A circular buffer, so no stable element addresses |
| `std::queue<T>` | `ArrayDeque<T>` | Same class. `addLast` / `poll` are the two ends |
| `std::stack<T>` | `ArrayDeque<T>` | Same class again. `push` / `pop` both work on the **head** |
| `std::list<T>` | `LinkedList<T>` | Exists, and is almost never what you want. `ArrayDeque` beats it at both ends |
| `std::unordered_map<K,V>` | `HashMap<K,V>` | Keys need `equals` and `hashCode`, not `operator<` or a hasher |
| `std::map<K,V>` | `TreeMap<K,V>` | Keys need `Comparable`, or a `Comparator` passed to the constructor |
| `std::unordered_set<T>` | `HashSet<T>` | A `HashMap` with a dummy value, and it says so in its source |
| `std::set<T>` | `TreeSet<T>` | A `TreeMap` with a dummy value, same relationship |
| `std::priority_queue<T>` | `PriorityQueue<T>` | Java's is a **min**-heap by default; C++'s is a max-heap |
| `std::multimap` / `multiset` | nothing | `Map<K, List<V>>` and `Map<T, Integer>`, built by hand |
| `std::array<T, N>` | `T[]` | A real array, but generics cannot make one — J8 |
| `std::pair` | nothing worth using | A `record`, named after what it is. `Map.Entry` for map entries only |
| `T*` element access | index or iterator only | No pointer into a container, so no invalidation rules to memorise |

Two classes in there deserve one sentence and no more. **`Vector` and `Stack` exist, they are
synchronized on every method, and nobody should use either.** `Vector` predates `ArrayList` and
`Stack` extends it, which is why `Stack.get(0)` returns the *bottom* while `pop()` returns the top;
use `ArrayList` and `ArrayDeque` instead.

## `ArrayDeque` answers three C++ classes, and that is the useful fact here

There is no separate queue class worth using and no separate stack class worth using. `ArrayDeque`
is both, and it is also `std::deque`. So the shape of your code no longer tells a reader which one
you meant — the method names do, and that is where the mapping bites.

**`push` and `pop` operate on the head.** `push` is `addFirst`, `pop` is `removeFirst`. So
`ArrayDeque` is a stack from the front, and if you reach for `push` because `std::queue::push`
appends, your order silently inverts. Real output from `worked/`:

```
  addLast 2,5,9  toString [2, 5, 9]  drained [2, 5, 9]
  push    2,5,9  toString [9, 5, 2]  drained [9, 5, 2]
```

The elevator has a place where that matters. `takeOutOfService` hands back the calls a withdrawn
lift can no longer answer, and every one is re-placed on another lift. The re-dispatch worklist is
the one genuine deque in this problem. And when two callers pressed opposite directions at the same
floor, the contract says the lift keeps one stop and the **first** direction to arrive:

```
  two callers on floor 7, UP first then DOWN:
    directionCalledFor(7)             UP
    same two calls, drained by push   DOWN
    pendingStops in both cases        [7]
```

`pendingStops` is identical either way, so no assertion about pending stops catches this. The lift
answers with the wrong direction, and a later re-dispatch picks the wrong lift for it.

Two more differences worth having: `ArrayDeque` rejects `null` with a `NullPointerException`, and it
has two families of end operations. `poll` and `peek` return `null` on empty; `pop` and
`removeFirst` throw `java.util.NoSuchElementException`. C++ gave you neither — `front()` on an empty
deque is undefined behaviour.

## Declare the interface, construct the implementation

```java
private final NavigableMap<Integer, Integer> stops = new TreeMap<>();
private final Map<Integer, Direction> hallCalls = new HashMap<>();
private final Set<Integer> served;
```

The left of each `=` is the narrowest type that answers the questions this field is asked. The right
is today's implementation. That split is the same idea as the corpus's policy seams, one level
down, and it buys two specific things.

**Swapping the implementation is one line.** `hallCalls` is a `HashMap` because every lookup is by
exact floor. If a requirement arrives that needs the nearest hall call above a floor, the field
becomes `NavigableMap` plus `new TreeMap<>()`, and no caller changes. Declare it `HashMap` and every
method signature that passed it around has to be edited too.

**The declaration states the guarantee.** `NavigableMap` on `stops` says "this thing is ordered and
that is load-bearing". `Map` on `hallCalls` says "order is not promised, do not rely on it". A
reviewer, and an interviewer, reads the field declarations first.

The exception is worth stating so it does not look like a rule with no edges. Declare the concrete
type when you need a method the interface does not have. `ArrayDeque` implements `Deque`, and `Deque`
has everything, so `Deque<Call>` is right. There is no `NavigableList`, so a field needing
`ArrayList.ensureCapacity` is declared `ArrayList`.

## `TreeMap` only earns its place when you need order, and then it earns it enormously

The cost first, so the choice is honest. `TreeMap` is `O(log n)` where `HashMap` is `O(1)`, it
allocates a node per entry, and it throws `NullPointerException` on a null key where `HashMap`
accepts one. On ten floors none of that is measurable, and the constant factor argument is not why
you choose either.

You choose `TreeMap` when the question you ask is about neighbours. Here is `ElevatorApi`'s entire
direction-order rule, against a `NavigableMap<Integer, Integer>` of pending stops:

```java
    public Integer nextStop(int currentFloor, Direction direction) {
        if (stops.isEmpty()) {
            return null;
        }
        if (stops.containsKey(currentFloor)) {
            return currentFloor;      // finish where you are before you move
        }
        return switch (direction) {
            case UP -> onwardOr(stops.ceilingKey(currentFloor), stops.lastKey());
            case DOWN -> onwardOr(stops.floorKey(currentFloor), stops.firstKey());
            case IDLE -> nearest(currentFloor);
        };
    }
```

Four queries, no loop, no sort, no index arithmetic. Real output from `worked/`, with stops pending
at 2, 5 and 9:

```
  pendingStops()                    [2, 5, 9]
  nextStopAtOrAbove(4)  ceilingKey   5
  nextStopAtOrAbove(5)  ceilingKey   5
  nextStopAtOrAbove(10) ceilingKey   null
  highestStopAtOrBelow(4) floorKey   2
  highestStopAtOrBelow(1) floorKey   null
  owedBelow(5)          headMap      1
  nextStop(4, UP)                    5
  nextStop(4, DOWN)                  2
  nextStop(4, IDLE)                  5
  nextStop(10, UP) turns round       9
```

The names, against the `std::map` calls you already use:

| The question | Java | C++ |
|---|---|---|
| Next stop at or above me | `ceilingKey(f)` | `lower_bound(f)` |
| Next stop strictly above me | `higherKey(f)` | `upper_bound(f)` |
| Highest stop at or below me | `floorKey(f)` | `--upper_bound(f)`, with the begin check |
| The two ends of the run | `firstKey()`, `lastKey()` | `begin()`, `--end()` |
| Everything below me | `headMap(f, false)` | the range `[begin, lower_bound(f))` |
| Everything above me | `tailMap(f, false)` | the range `(upper_bound(f), end)` |
| The entry, not the key | `ceilingEntry(f)` | dereference the iterator |

Three details the C++ versions do not have. **Absent is `null`, not an end iterator**, so
`ceilingKey(10)` above returns `null` rather than something you must compare against `end()`. On an
empty map, `firstKey()` throws `java.util.NoSuchElementException` while `ceilingKey` returns `null`
— the neighbour queries are the null-safe family. And **`headMap` is a live view, not a copy**:
writing through it writes through to the map, and a key outside its range is refused with
`java.lang.IllegalArgumentException: key out of range`.

Writing `nextStop` against an `ArrayList` instead means a scan, a comparison and two edge cases per
branch. That is where a candidate loses ten minutes in a round, and it is the reason to know these
seven method names cold.

## The trap that actually bites: the factory that hands back a view

`List.of`, `Map.of`, `Set.of` and `Arrays.asList` all look like constructors and none of them
returns something you can write to. Nothing warns you at compile time. Real output, caught and
printed by `worked/Main.java`:

```
  pendingStops().add(9)             java.lang.UnsupportedOperationException (no message)
    top frames of pendingStops().add(9):
      at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
      at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)
      at Main.lambda$theViewsThatThrow$1(Main.java:191)
  Arrays.asList(...).add(5)         java.lang.UnsupportedOperationException (no message)
  Arrays.asList(...).set(0, 2)      no throw
  Set.of(...).add(5)                java.lang.UnsupportedOperationException (no message)
  Map.of(...).put(5, DOWN)          java.lang.UnsupportedOperationException (no message)
```

**The exception carries no message.** Uncaught, that is the whole of what you get:

```
Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:142)
	at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:147)
	at Probe2.main(Probe2.java:18)
```

The frame naming `ImmutableCollections` is the only clue, and `Arrays.asList` does not even give you
that — its trace reads `at java.base/java.util.AbstractList.add(AbstractList.java:155)` and never
mentions `Arrays`. So recognise the two traces, because the exception itself tells you nothing.

Three shapes, and they differ:

| What you wrote | `add` | `set` | Why |
|---|---|---|---|
| `List.of(...)` | throws | throws | Genuinely immutable, and shares no array with you |
| `Arrays.asList(...)` | throws | **works** | A fixed-size view **over your array**; writes reach the array |
| `Collections.unmodifiableList(l)` | throws | throws | A read-only wrapper; changes to `l` still show through |

`Arrays.asList` is the one that surprises people twice. It is fixed-size rather than immutable, and
it wraps the array you passed rather than copying it. If you need a mutable list from a fixed one,
`new ArrayList<>(List.of(...))` is the copy.

## `Map.of` has two more edges

**Duplicate keys are refused, at construction.** Two hall calls for floor 7 in one literal:

```
  Map.of(7, UP, 7, DOWN)            java.lang.IllegalArgumentException: duplicate key: 7
```

`Set.of` matches it with `duplicate element: 7`. A `HashMap` would have taken the second value
quietly, so this is the safer behaviour — provided the keys are literals you control.

**Null is refused, key or value.** `Map.of(7, null)` and `List.of(2, null, 9)` both throw
`java.lang.NullPointerException` with no message. `HashMap` and `ArrayList` both accept nulls, so
this bites when you build a `Map.of` from parsed input.

**And the iteration order is deliberately randomised between JVM runs.** The same program, twice, no
recompile:

```
  Set.of(2,5,7,9,10) iterates       [7, 9, 10, 2, 5]
  Map.of(...).keySet() iterates     [7, 9, 10, 2, 5]
```

```
  Set.of(2,5,7,9,10) iterates       [10, 2, 5, 7, 9]
  Map.of(...).keySet() iterates     [10, 2, 5, 7, 9]
```

A per-JVM salt is mixed into the layout on purpose, to stop anybody depending on the order. A test
that asserts on the order of a `Map.of` keySet passes locally, passes in CI, and fails on some later
run with no change to blame. Do not iterate `Map.of` or `Set.of` for anything observable. If you
need ascending, say so: `new TreeSet<>(Set.of(...))`, or `List.copyOf` of a `TreeMap`'s keys.

## The trap one level down: `HashSet<Integer>` looks sorted

This is the trap that survives review, because the evidence supports it. `Integer.hashCode()`
returns the value, and a `HashSet` puts a key in bucket `hash & (tableSize - 1)`. With floors 1..10
and a default table of 16, every floor lands in its own bucket in order:

```
  10-floor building, added 9,2,7,4   [2, 4, 7, 9]
```

So `pendingStops()` backed by a `HashSet` satisfies the contract's "ascending" every single time you
run it against the building `Entry.create()` builds. Now the same code in a twenty-floor tower,
where 19 and 3 collide because `19 & 15 == 3`:

```
  20-floor tower,   added 19,3,12,5  [19, 3, 5, 12]
  20-floor tower,   added 3,19,20,4  [3, 19, 20, 4]
  TreeSet of 19,3,12,5               [3, 5, 12, 19]
```

The threshold is exact: with the default capacity of 16, `HashSet<Integer>` iterates ascending only
while every value is distinct modulo the table size. It is never a guarantee, at any size. If a
caller can see the order, the type has to promise it.

## `PriorityQueue` — two differences, both silent

Java's `PriorityQueue` is a **min**-heap. `std::priority_queue` is a max-heap. So the direct
translation of C++ code inverts the priority, and neither compiler says a word. For largest-first,
pass `Comparator.reverseOrder()`.

And it is a heap, not a sorted container. `toString` and iteration show heap order:

```
  PriorityQueue toString                [2, 3, 7, 9, 5, 8]
  PriorityQueue poll order              [2, 3, 5, 7, 8, 9]
```

Only `poll` is ordered. C++ never let you iterate a `priority_queue` at all, so there was no way to
form this habit; Java lets you, and the result looks almost sorted.

## `EnumMap`, in one line

An enum key means `EnumMap`: an array indexed by `ordinal()`, no hashing, iterating in declaration
order. `worked/Main.java` prints `{UP=3, DOWN=1}` for a `Map<Direction, Integer>`. J10 covers why
that matters, and it is more than the array.

## The choosing rule, in the order to ask it

Ten seconds, top to bottom, first match wins:

1. **Key is an enum** → `EnumMap`. See J10
2. **You ask about order** — nearest above, ranges, first, last, sorted output → `TreeMap` / `TreeSet`
3. **You add and remove at both ends** → `ArrayDeque`
4. **You only ask "is it in there"** → `HashSet`
5. **Key to value, looked up by exact key** → `HashMap`
6. **Otherwise** → `ArrayList`

The reason the order matters is that rules 2 and 4 both look like rule 5 from inside a method. The
elevator has all three in one class: `stops` is asked for neighbours, so `TreeMap`; `hallCalls` is
asked for one exact floor, so `HashMap`; `served` is asked only for membership, so a `Set`.

### When the default is wrong

**Rule 6 is wrong when a caller can see the iteration order.** `ArrayList` keeps insertion order,
which is a promise you probably did not mean to make — the FIFO route at the top of this page is
that promise being kept faithfully.

**Rule 5 is wrong the moment you need "the entry nearest to k".** Reaching for a `HashMap` and
sorting its keys on each call is the tell. Two sorts per tick costs more than a `TreeMap`, and the
sort is a line of code that can be wrong.

**Rule 4 is wrong when the set is the answer rather than a filter.** `pendingStops()` returns a
`List`, ascending, because the operator's console draws it. A `HashSet` behind it satisfies the
contract on ten floors and breaks on twenty.

**Rules 2 and 3 are wrong when you have not been asked for order at all.** A `TreeMap` keyed by lift
id, holding lifts 1, 2 and 3, is a sorted structure over a dense range. The reference uses
`List.copyOf` and `lifts.get(liftId - 1)`, which is one array read.
