Choosing a data structure is choosing which operations will be fast. The book walks through the C++ standard library. This page gives the Java collection you’d use for each one, plus the places where Java behaves differently.
Data structure chunna = yeh chunna ki kaunse operations fast honge. Book C++ standard library dikhati hai; yeh page har ek ke liye woh Java collection deta hai jo tum use karoge — aur woh jagah bhi jahan Java alag behave karta hai.
4.1Dynamic arrays
ArrayList<E> is C++‘s vector: add at the end is amortised O(1) and get(i)/set(i, x) are O(1). Strings are immutable in Java. Build them with StringBuilder (repeated + in a loop is O(n²)), and note that substring(begin, end) takes an end index, not a length.
ArrayList<E> C++ ka vector hai: end pe add amortised O(1), get(i)/set(i, x) O(1). Java mein strings immutable hain — StringBuilder se banao (loop mein baar baar + O(n²) hai), aur substring(begin, end) mein end index dete hain, length nahi.
static List<Integer> dynamicArray() { List<Integer> v = new ArrayList<>(); // vector<int> v.add(3); // push_back v.add(2); v.add(5); v.remove(v.size() - 1); // pop_back (by index!) return v; // [3, 2]}static String strings() { String a = "hatti"; StringBuilder b = new StringBuilder(a).append(a); // Strings are immutable: build with StringBuilder b.setCharAt(5, 'v'); // hattivatti return b.substring(3, 3 + 4); // substring(begin, END), not (pos, length): "tiva"}My notesMere notes
4.2Set structures
TreeSetis C++‘sset: a balanced tree, kept sorted, with O(log n) operations.HashSetisunordered_set: hashing, O(1) on average, with no order.
Both ignore duplicates. Java has no multiset, so store counts in a TreeMap<Integer, Integer> and delete a key when its count reaches 0.
TreeSetC++ kasethai: balanced tree, hamesha sorted, O(log n) operations.HashSetunordered_sethai: hashing, average O(1), koi order nahi.
Dono duplicates ignore karte hain. Java mein multiset nahi hai — counts ko TreeMap<Integer, Integer> mein rakho, aur count 0 hote hi key hata do.
static boolean[] sets() { Set<Integer> hash = new HashSet<>(); // unordered_set: O(1) average TreeSet<Integer> tree = new TreeSet<>(); // set: ordered, O(log n) for (int x : new int[] {3, 2, 5, 5, 5}) { hash.add(x); tree.add(x); // duplicates are ignored } tree.remove(3); tree.add(4); return new boolean[] {hash.contains(3), tree.contains(3), tree.contains(4), tree.size() == 3};}/** Java has no multiset: count occurrences in a TreeMap instead. */static void addOne(TreeMap<Integer, Integer> ms, int x) { ms.merge(x, 1, Integer::sum);} /** Remove ONE copy of x (C++: s.erase(s.find(x))). */static void removeOne(TreeMap<Integer, Integer> ms, int x) { if (ms.merge(x, -1, Integer::sum) == 0) ms.remove(x);}My notesMere notes
4.3Map structures
TreeMap is map (sorted keys, O(log n)) and HashMap is unordered_map (O(1) on average). The big behavioural difference from C++ is reading a missing key:
- In C++,
m[key]inserts the key with a default value. - In Java,
getreturnsnull, and unboxing thatnullinto anintthrows aNullPointerException.
Use getOrDefault(key, 0), and merge(key, 1, Integer::sum) to increment a counter.
TreeMap = map (sorted keys, O(log n)), HashMap = unordered_map (average O(1)). C++ se sabse bada fark: missing key padhna.
- C++ mein
m[key]key ko default value ke saath insert kar deta hai. - Java mein
getnulldeta hai — aur usnullkointmein unbox karoge tohNullPointerException.
getOrDefault(key, 0) use karo, aur counter badhane ke liye merge(key, 1, Integer::sum).
static Map<String, Integer> maps() { Map<String, Integer> m = new HashMap<>(); // unordered_map; TreeMap for map m.put("monkey", 4); m.put("banana", 3); m.put("harpsichord", 9); m.merge("banana", 1, Integer::sum); // m["banana"]++ → 4 int missing = m.getOrDefault("aybabtu", 0); // C++ would INSERT the key here; Java doesn't m.put("check", missing); return m;}My notesMere notes
4.4Iterators and ranges
C++ moves iterators around a set (lower_bound, it--). Java’s TreeSet answers those questions directly, in O(log n), and returns null when there is no answer:
| C++ idea | Java TreeSet |
|---|---|
*s.begin() / last element | first() / last() |
lower_bound(x) (smallest ≥ x) | ceiling(x) |
upper_bound(x) (smallest > x) | higher(x) |
| previous element (largest ≤ x / < x) | floor(x) / lower(x) |
| a range of elements | subSet(a, true, b, false), headSet, tailSet |
The book’s “element nearest to x” becomes four lines with ceiling and floor:
C++ set pe iterators chalata hai (lower_bound, it--). Java ka TreeSet yahi sawaal seedha O(log n) mein jawab deta hai — aur jawab na ho toh null:
| C++ idea | Java TreeSet |
|---|---|
*s.begin() / aakhri element | first() / last() |
lower_bound(x) (≥ x mein sabse chhota) | ceiling(x) |
upper_bound(x) (> x mein sabse chhota) | higher(x) |
| pichhla element (≤ x / < x mein sabse bada) | floor(x) / lower(x) |
| elements ki range | subSet(a, true, b, false), headSet, tailSet |
Book ka “x ke sabse paas wala element” ceiling aur floor se chaar lines ka ho jaata hai:
/** The element of a non-empty set closest to x (ties go to the smaller one). */static int nearest(TreeSet<Integer> s, int x) { Integer up = s.ceiling(x); // smallest ≥ x (C++ lower_bound) Integer down = s.floor(x); // largest ≤ x if (up == null) return down; if (down == null) return up; return x - down <= up - x ? down : up;}- answer
set.ceiling(10) → 12
Every call is O(log n) on a TreeSet. A HashSet can only answer contains/add/remove, but in O(1) on average.
My notesMere notes
4.5Other structures
- Deque, stack and queue: use
ArrayDequefor all three. Usepush/pop/peekfor a stack,offer/poll/peekfor a queue, andaddFirst/addLast/pollFirst/pollLastfor a deque. Avoid the legacyStackclass andLinkedList, which are slower. - Priority queue: Java’s
PriorityQueueis a min-heap by default, the opposite of C++. For a max-heap, passCollections.reverseOrder(). Insert and remove are O(log n), and peeking is O(1). - Bitset:
java.util.BitSetstores one bit per element and supportsand,or,xorandcardinality(). Chapter 10 does more with bits.
- Deque, stack, queue: teeno ke liye
ArrayDeque. Stack ke liyepush/pop/peek, queue ke liyeoffer/poll/peek, deque ke liyeaddFirst/addLast/pollFirst/pollLast. PuraniStackclass aurLinkedListse bacho — slow hain. - Priority queue: Java ka
PriorityQueuedefault min-heap hai — C++ ka ulta! Max-heap ke liyeCollections.reverseOrder()do. Insert/remove O(log n), peek O(1). - Bitset:
java.util.BitSethar element ke liye ek bit rakhta hai, aurand,or,xor,cardinality()deta hai. Chapter 10 mein bits pe aur kaam.
static int[] stacksAndQueues() { Deque<Integer> stack = new ArrayDeque<>(); // stack: push / pop / peek at the front stack.push(3); stack.push(2); stack.push(5); int top = stack.pop(); // 5 Deque<Integer> queue = new ArrayDeque<>(); // queue: offer at the back, poll from the front queue.offer(3); queue.offer(2); queue.offer(5); int front = queue.poll(); // 3 Deque<Integer> d = new ArrayDeque<>(); // deque: both ends d.addLast(5); d.addLast(2); d.addFirst(3); // [3, 5, 2] d.pollLast(); // [3, 5] d.pollFirst(); // [5] return new int[] {top, front, d.peekFirst()};}static int[] priorityQueues() { PriorityQueue<Integer> min = new PriorityQueue<>(); // Java's default is a MIN-heap PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder()); // C++'s default for (int x : new int[] {3, 5, 7, 2}) { min.add(x); max.add(x); } return new int[] {min.poll(), max.poll(), max.peek()}; // 2, 7, 5}static String bitsets() { BitSet a = BitSet.valueOf(new long[] {0b0010110110L}); BitSet b = BitSet.valueOf(new long[] {0b1011011000L}); BitSet and = (BitSet) a.clone(); and.and(b); // a & b → 0010010000 return Long.toBinaryString(and.toLongArray()[0]) + " count=" + a.cardinality();}My notesMere notes
4.6Comparison to sorting
Problem: how many values appear in both lists A and B (n values each)? There are three approaches:
- a
TreeSet, which is O(n log n); - a
HashSet, which is O(n) on average; - sorting both lists and walking them with two pointers, which is O(n log n).
In the book’s C++ timings, sorting was the fastest by far, about 10× faster than the tree-based set at the same O(n log n). Sorting runs once with a tiny constant, while the tree pays a large constant on every operation. In Java the gap is even bigger, because the sets also box every number.
Problem: do lists A aur B (har ek mein n values) mein kitni values common hain? Teen approaches:
TreeSet— O(n log n);HashSet— average O(n);- dono lists sort karke two pointers se chalna — O(n log n).
Book ki C++ timings mein sorting sabse tez tha — same O(n log n) hote hue bhi tree wale set se ~10× tez. Sorting ek baar chalta hai aur uska constant chhota hai, jabki tree har operation pe bada constant bharta hai. Java mein yeh fark aur bada hai, kyunki sets har number ko box bhi karte hain.
static int withSorting(int[] a, int[] b) { // O(n log n), tiny constant: sort once, then walk int[] x = a.clone(), y = b.clone(); Arrays.sort(x); Arrays.sort(y); int i = 0, j = 0, count = 0; while (i < x.length && j < y.length) { if (x[i] == y[j]) { count++; i++; j++; } else if (x[i] < y[j]) i++; else j++; } return count;}