☕ DSA Java Articles

Topics › Basics › Learn STL/Java-Collections or similar thing in your | language

STL

Easy TUF ID 1218 A2Z

Java source ↗ Edit this article ↗

Problem

The sheet asks you to learn the C++ Standard Template Library before touching real problems, because every later solution is written in its vocabulary: vector, pair, set, map, priority_queue, sort, lower_bound, next_permutation. Editorials and video explanations use those names even when you code in Java.

This article is the translation table. For each STL container and algorithm it names the Java equivalent, points out where the behaviour differs, and shows working Java code. Three STL algorithms have no direct Java counterpart (lower_bound, upper_bound, next_permutation), so they are implemented by hand; you will reuse them often. The companion article Java Collections goes deeper into the Java side.

The STL has four kinds of pieces: containers (data structures), iterators (positions inside containers), algorithms (functions over iterator ranges) and functors (comparators). Java has containers and algorithms too; iterators exist but are rarely written by hand, and functors are lambdas or Comparators.

Containers

vector is ArrayList

A dynamic array with amortised O(1) append and O(1) indexed access. Insert or erase in the middle is O(n) in both languages.

static List<Integer> vectorDemo() {
    List<Integer> v = new ArrayList<>();         // vector<int> v;
    v.add(1); v.add(2); v.add(3);                // v.push_back(1); ...        -> [1, 2, 3]
    v.remove(v.size() - 1);                      // v.pop_back();              -> [1, 2]
    v.add(0, 0);                                 // v.insert(v.begin(), 0);    -> [0, 1, 2]
    v.set(1, 10);                                // v[1] = 10;                 -> [0, 10, 2]
    v.remove(0);                                 // v.erase(v.begin());        -> [10, 2]
    v.addAll(List.of(7, 8));                     // v.insert(v.end(), {7, 8}); -> [10, 2, 7, 8]
    return v;
}

Differences: Java lists hold boxed Integers, so for raw speed on primitives use int[] and Arrays helpers. remove(int) removes by index while remove(Object) removes by value; v.remove(Integer.valueOf(2)) is the value form. vector<vector<int>> becomes List<List<Integer>> or int[][].

deque, list, stack, queue are ArrayDeque (and LinkedList)

ArrayDeque gives O(1) push and pop at both ends and is the recommended implementation for stacks and queues. LinkedList corresponds to std::list but is slower in practice; use it only when you need to splice in the middle through an iterator.

static List<Integer> dequeDemo() {
    Deque<Integer> dq = new ArrayDeque<>();      // deque<int> dq;
    dq.addLast(1);                               // dq.push_back(1);   -> [1]
    dq.addFirst(2);                              // dq.push_front(2);  -> [2, 1]
    dq.addLast(3);                               // dq.push_back(3);   -> [2, 1, 3]
    dq.addFirst(4);                              // dq.push_front(4);  -> [4, 2, 1, 3]
    dq.removeLast();                             // dq.pop_back();     -> [4, 2, 1]
    dq.removeFirst();                            // dq.pop_front();    -> [2, 1]
    return new ArrayList<>(dq);
}

std::stack and std::queue are adapters over a deque; in Java you use the Deque interface directly. push/pop/peek work at the head (stack), offer/poll/peek work tail-to-head (queue). Avoid java.util.Stack: it is a synchronised legacy class.

static List<Integer> stackAndQueueDemo() {
    Deque<Integer> st = new ArrayDeque<>();      // stack<int> st;
    Deque<Integer> q = new ArrayDeque<>();       // queue<int> q;
    for (int x = 1; x <= 3; x++) {
        st.push(x);                              // st.push(x);
        q.offer(x);                              // q.push(x);
    }
    List<Integer> out = new ArrayList<>();
    while (!st.isEmpty()) out.add(st.pop());     // st.top(); st.pop();   -> 3, 2, 1
    while (!q.isEmpty()) out.add(q.poll());      // q.front(); q.pop();   -> 1, 2, 3
    return out;
}

One trap: ArrayDeque rejects null elements, while LinkedList accepts them.

priority_queue is PriorityQueue, with the opposite default

Both are binary heaps with O(log n) push and pop and O(1) peek. C++ pops the largest element by default; Java pops the smallest. To get C++ behaviour pass Collections.reverseOrder(); for the C++ min-heap spelling priority_queue<int, vector<int>, greater<int>> use Java’s default.

static List<Integer> priorityQueueDemo(int[] values) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // priority_queue<int>
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();                           // priority_queue<int, vector<int>, greater<int>>
    for (int v : values) {
        maxHeap.offer(v);
        minHeap.offer(v);
    }
    List<Integer> out = new ArrayList<>();
    while (!maxHeap.isEmpty()) out.add(maxHeap.poll());   // largest first
    while (!minHeap.isEmpty()) out.add(minHeap.poll());   // smallest first
    return out;
}

set, multiset, unordered_set are TreeSet, TreeMap of counts, HashSet

std::set is a balanced tree: sorted, unique, O(log n) operations, with lower_bound/upper_bound. Java’s TreeSet is the same structure; ceiling(x) is lower_bound(x) (first element >= x) and higher(x) is upper_bound(x) (first element > x), both returning null instead of end(). floor and lower are the mirror images. unordered_set is HashSet with O(1) average operations and no order. Java has no multiset; a TreeMap<value, count> is the standard replacement.

static List<String> setDemo(int[] values) {
    TreeSet<Integer> set = new TreeSet<>();                      // set<int>: sorted, unique
    Set<Integer> uset = new HashSet<>();                         // unordered_set<int>: hashed, unique
    TreeMap<Integer, Integer> multiset = new TreeMap<>();        // multiset<int>: sorted, duplicates kept as counts
    for (int v : values) {
        set.add(v);
        uset.add(v);
        multiset.merge(v, 1, Integer::sum);
    }
    List<String> out = new ArrayList<>();
    out.add("set=" + set);
    out.add("unordered_set.size=" + uset.size());
    out.add("multiset=" + multiset);
    out.add("set.lower_bound(4)=" + set.ceiling(4));             // first element >= 4, null when none
    out.add("set.upper_bound(4)=" + set.higher(4));              // first element > 4, null when none
    out.add("multiset.count(4)=" + multiset.getOrDefault(4, 0));
    return out;
}

map, unordered_map are TreeMap, HashMap

Same split: tree versus hash. The idiom m[key]++ has a subtle C++ behaviour (reading a missing key inserts it with value 0); Java’s merge(key, 1, Integer::sum) increments or creates, and getOrDefault reads without inserting.

static List<String> mapDemo(String[] words) {
    TreeMap<String, Integer> map = new TreeMap<>();              // map<string, int>: keys kept sorted
    Map<String, Integer> umap = new HashMap<>();                 // unordered_map<string, int>: hashed
    for (String w : words) {
        map.merge(w, 1, Integer::sum);                           // map[w]++;
        umap.merge(w, 1, Integer::sum);
    }
    List<String> out = new ArrayList<>();
    out.add("map=" + map);
    out.add("umap.size=" + umap.size());
    out.add("count(zzz)=" + map.getOrDefault("zzz", 0));         // reads without inserting, unlike C++ operator[]
    out.add("firstKey=" + (map.isEmpty() ? "none" : map.firstKey()));
    return out;
}

pair is a record

pair<int,int> becomes a two-field record. C++ sorts pairs by first then second; in Java you say so with a chained Comparator. For the fastest code, int[][] with a comparator lambda is also common.

static List<Pair> sortPairs(int[][] raw) {
    List<Pair> pairs = new ArrayList<>();
    for (int[] p : raw) pairs.add(new Pair(p[0], p[1]));
    pairs.sort(Comparator.comparingInt(Pair::first).thenComparingInt(Pair::second));
    return pairs;
}

Algorithms

sort, reverse, min_element, max_element, accumulate, count, find

STL algorithms take iterator ranges; Java’s live in Collections (for lists) and Arrays (for arrays). Arrays.sort(int[]) is a dual-pivot quicksort; Collections.sort and List.sort are a stable TimSort. Note the long accumulator for accumulate: 0LL in C++.

static List<String> algorithmDemo(int[] values) {
    List<Integer> list = new ArrayList<>();
    for (int v : values) list.add(v);
    Collections.sort(list);                                      // sort(v.begin(), v.end());
    String ascending = list.toString();
    list.sort(Collections.reverseOrder());                       // sort(v.rbegin(), v.rend());
    String descending = list.toString();
    Collections.reverse(list);                                   // reverse(v.begin(), v.end());
    long sum = 0;                                                // accumulate(v.begin(), v.end(), 0LL);
    for (int v : list) sum += v;
    List<String> out = new ArrayList<>();
    out.add("asc=" + ascending);
    out.add("desc=" + descending);
    out.add("reversedBack=" + list);
    out.add("min=" + Collections.min(list) + " max=" + Collections.max(list));   // *min_element, *max_element
    out.add("sum=" + sum);
    out.add("count(2)=" + Collections.frequency(list, 2));       // count(v.begin(), v.end(), 2);
    out.add("find(5)=" + list.indexOf(5));                       // find(...) - v.begin(), or -1 when absent
    return out;
}

lower_bound and upper_bound on arrays

Java’s Arrays.binarySearch tells you whether a value exists but, with duplicates, not which occurrence it found. The two STL bounds are the tools you really want: lowerBound returns the first index with a[i] >= x, upperBound the first with a[i] > x, both a.length when there is none. Their difference is the number of occurrences of x.

static int lowerBound(int[] a, int x) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

static int upperBound(int[] a, int x) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

The invariant: every index below lo fails the test, every index at or above hi passes it; the loop ends with lo == hi at the boundary. mid = lo + (hi - lo) / 2 avoids overflow of lo + hi.

static boolean binarySearch(int[] a, int x) {
    return Arrays.binarySearch(a, x) >= 0;
}

next_permutation

Used to enumerate all permutations in lexicographic order. Find the longest non-increasing suffix; the element just before it (a[i]) is the pivot. Swap it with the smallest suffix element larger than it, then reverse the suffix so it becomes the smallest arrangement. If there is no pivot the array is the last permutation; like the STL, reset it to the first one and return false.

static boolean nextPermutation(int[] a) {
    int n = a.length;
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;      // 1. a[i + 1..] is the longest non-increasing suffix
    if (i < 0) {
        reverse(a, 0, n - 1);                    //    the whole array is descending: wrap around to the first permutation
        return false;
    }
    int j = n - 1;
    while (a[j] <= a[i]) j--;                    // 2. rightmost element larger than a[i]
    swap(a, i, j);                               // 3. put the next larger value at position i
    reverse(a, i + 1, n - 1);                    // 4. make the suffix as small as possible
    return true;
}

swap and reverse are the two-line helpers std::swap and std::reverse on an index range; see the Java file. Starting from a sorted array and calling nextPermutation until it returns false visits all n! permutations exactly once; the tests count 24 for four elements.

Compiler builtins

__builtin_popcount(x), __builtin_ctz(x) and __builtin_clz(x) are Integer.bitCount, Integer.numberOfTrailingZeros and Integer.numberOfLeadingZeros (with Long versions for 64 bits). Unlike the C++ builtins, the Java versions are well defined for 0 (they return 32).

static int[] builtins(int x) {
    return new int[]{Integer.bitCount(x), Integer.numberOfTrailingZeros(x), Integer.numberOfLeadingZeros(x)};
}

Cheat sheet

STL Java Notes
vector<T> ArrayList<T>, int[] remove(int) is by index
deque, stack, queue ArrayDeque no nulls; push/pop at head
list LinkedList rarely worth it
priority_queue<T> PriorityQueue<>(reverseOrder()) Java default is a min-heap
set, map TreeSet, TreeMap ceiling/higher = lower_bound/upper_bound
unordered_set, unordered_map HashSet, HashMap merge for counting
multiset TreeMap<T, Integer> counts instead of copies
pair record chained Comparator
sort with comparator Arrays.sort(T[], cmp), List.sort no comparator sort for int[]; box or use int[][]
lower_bound, upper_bound, next_permutation hand-written above  

Edge cases and pitfalls