Skip to content
Software Testing · First Principles

Collections — Empty, One, Many, Duplicates, Order

The numbers page walked the number line and found the bugs living at its landmarks. The strings page did the same for text and discovered that “empty,” “huge,” and “not what you assumed” break code that only ever saw the tidy middle case. A collection — a list, an array, a set, a map — is the natural next target, because a collection has both of those axes at once: a size (how many elements) and a shape (what those elements are and how they relate).

Most code that touches a collection was written and tested against a comfortable handful of elements — three users, five orders, a dozen rows. That is the interior again. The bugs are at the edges of the size axis (none, one, an unbounded flood) and in the assumptions about shape (all distinct, already sorted, iterated in a fixed order). This page teaches you to attack a collection at every size that matters and to distrust every ordering your code silently relies on.

The three canonical sizes: zero, one, many

Section titled “The three canonical sizes: zero, one, many”

For any collection input, there is a short, non-negotiable list of sizes to test. Not “a typical list” — that is one point in a huge space where nothing changes. The sizes where behaviour changes are:

        ∅            [x]           [x, y, z, ...]        [ ... 10^7 elements ]
        │             │                  │                       │
     EMPTY        SINGLETON            MANY                     HUGE
   zero elements  exactly one       two or more            enough to strain
                                                            memory & time
  • Zero (empty). The collection with no elements. This is the single most-skipped and most-productive test in all of software. An empty list makes loops run zero times, makes first() and last() undefined, makes max() and average() answer a question that has no answer, and makes every “there is at least one” assumption false.
  • One (singleton). Exactly one element. This is where “first” and “last” become the same element, where a “compare adjacent pairs” loop has no pair to compare, and where a delimiter-joining routine that puts commas between elements has zero commas to insert. Singletons expose code that only works because there was always a neighbour.
  • Many. Two or more. This is the case everyone tests, and it is still worth being deliberate: two is the smallest “many,” and it is where an off-by-one in a pairwise loop first shows up.
  • Huge. Not a different behaviour but a different resource regime. Ten million elements do not change what the operation computes; they change whether it finishes, and whether it fits in memory. Huge is where an O(n²) algorithm that looked instant on twelve rows takes an hour, and where “load the whole thing into a list first” runs the process out of RAM. We give huge its own treatment below.

The discipline is simple and it never gets old: for every collection your code accepts or produces, write the empty test and the singleton test first, before the happy-path “many” test. They are the two most likely to be broken and the two most likely to be forgotten.

# A minimum viable suite for anything that consumes a collection:
def test_empty():      assert summarize([]) == ...        # zero elements
def test_singleton():  assert summarize([x]) == ...       # exactly one
def test_many():       assert summarize([x, y, z]) == ... # the "normal" case

Off-by-one and the fencepost

Section titled “Off-by-one and the fencepost”

The classic collection bug is the off-by-one, and its most famous shape is the fencepost error: to build a fence 10 metres long with posts every metre, you need 11 posts, not 10 — one more post than sections. Code that confuses “number of gaps” with “number of posts” runs its loop one time too many or one time too few.

   post ─┬─ post ─┬─ post ─┬─ post
         │        │        │
       section  section  section


   3 sections  →  4 posts.   Off by exactly one.

The three places a fencepost hides in collection code:

  • The last element. A loop written for i in 0..len (exclusive) is correct; for i in 0..=len (inclusive) reads one past the end and either crashes or reads garbage. The last valid index is len - 1, and the empty collection has no valid index at all — which is why len - 1 on an empty list is itself a bug (0 - 1 underflows, or is -1, or panics).
  • The first element. Code that “skips the header” or “starts from the second element” quietly assumes there is a first element to skip. On an empty input it skips into the void.
  • The pair-wise loop. Comparing each element to the next one (a[i] vs a[i+1]) must stop at len - 1, not len, or the final comparison reads off the end. On a singleton there are zero pairs, and the loop body must run zero times — a fact only the singleton test proves.
// Sum each element with the next: pairwise differences of a series.
fn diffs(xs: &[i64]) -> Vec<i64> {
    let mut out = Vec::new();
    // Correct upper bound: xs.len().saturating_sub(1) — NOT xs.len().
    for i in 0..xs.len().saturating_sub(1) {
        out.push(xs[i + 1] - xs[i]);
    }
    out
}


#[test]
fn diffs_at_the_edges() {
    assert_eq!(diffs(&[]), vec![]);          // empty: no elements, no diffs
    assert_eq!(diffs(&[7]), vec![]);         // singleton: no pair to diff
    assert_eq!(diffs(&[1, 4, 9]), vec![3, 5]); // many: n-1 diffs, never n
}

Notice that the empty and singleton tests are what make the boundary xs.len() - 1 versus xs.len() visible. Without them, a plain 0..xs.len() on the three-element case looks fine right up until it indexes xs[3] and panics — or worse, on an unsigned length, 0usize - 1 wraps to a gigantic number and the loop tries to run four billion times.

Duplicates, uniqueness, and the empty aggregate

Section titled “Duplicates, uniqueness, and the empty aggregate”

The second axis is shape, and the first shape question is always: can elements repeat, and does your code assume they can’t?

A list [a, b, a] breaks any code that treated the collection as a set. Deduplication (dedup), set membership, “group by,” and counting all behave differently depending on whether duplicates are present, adjacent, or scattered. Two traps recur:

  • dedup that only removes adjacent duplicates. Rust’s Vec::dedup, Unix uniq, and many stream operators collapse only consecutive equal elements. On [a, a, b, a] they yield [a, b, a], not [a, b]. If you need true uniqueness you must sort first (or use a set). The test that catches this is the non-adjacent duplicate: [a, b, a].
  • Set semantics silently drop data. Converting a list to a set to “clean it up” also discards multiplicity and order. If a later step counts occurrences or preserves input order, you have introduced a bug that the happy-path all-distinct test will never reveal.

Then there is the aggregate on an empty collection — the question the numbers page raised and this page must answer, because it is where “empty” and “arithmetic” collide:

Aggregate of an EMPTY collection — what is the right answer?


  count([])     →  0            (unambiguous: there are zero things)
  sum([])       →  0            (the identity of addition — safe, standard)
  product([])   →  1            (the identity of multiplication — surprises people)
  max([])       →  undefined    (no element; must error or return Option::None)
  min([])       →  undefined    (same — there is no smallest of nothing)
  average([])   →  0 / 0        (a DECISION: error? null? NaN? zero? — pick and test it)

sum([]) is 0 and count([]) is 0 because those are the identity elements — adding nothing changes nothing. But average([]) is sum/count = 0/0, which has no correct value; it is a decision the author must make and a test must pin down. Returning 0 is a lie (the average of no data is not zero). Raising an error is defensible. Returning null/None is defensible. The one thing you must not do is let 0/0 reach the CPU and produce a silent NaN or a crash. The test is the specification of what “average of nothing” means in your system:

def average(xs):
    if not xs:
        return None          # our decision: "no data" is None, not 0, not NaN
    return sum(xs) / len(xs)


def test_average_of_empty_is_none():
    assert average([]) is None      # the boundary that has no arithmetic answer
    assert average([4]) == 4.0      # singleton: average of one is that one
    assert average([2, 4]) == 3.0   # many, for contrast

Ordering assumptions: the ground that shifts under you

Section titled “Ordering assumptions: the ground that shifts under you”

The most insidious collection bugs are not about size or duplicates. They are about order — specifically, code that works only because the input happened to arrive in a convenient order, and nothing in the code or its tests ever said so out loud.

Three ordering assumptions to hunt down:

  • “It happened to be sorted.” A binary search, a merge, a “detect the first item over the threshold” scan — all silently require sorted input. During development the test data was hand-written in order, so the code passed. In production the input arrives in insertion order, or reverse order, or shuffled, and the algorithm returns a wrong answer without crashing. The fix is to either sort explicitly (and test with deliberately unsorted input) or assert the precondition. Always test order-dependent code with a shuffled input, because that is the input the tidy test data hid from you.
  • Unstable sorts reorder “equal” elements. A sort is stable if elements the comparator considers equal keep their original relative order. Many default sorts are not stable (or are only stable for some types). If you sort a list of orders by date and expect same-date orders to stay in insertion order, an unstable sort may silently swap them — a bug that appears only when two keys tie. Test with deliberate ties to expose it.
  • Hash maps have undefined iteration order. Iterating a HashMap / dict / Set gives elements in an order that is not the insertion order and, in many runtimes, is randomised per run for security. Code that builds output by iterating a hash map and expects a stable order will produce different results on different runs — and a test that happened to pass once will flake later. If you need a stable order, use an ordered map (BTreeMap, LinkedHashMap, an insertion-ordered dict) or sort the keys explicitly before iterating. The test that catches the assumption asserts the exact expected order, so a randomised iteration fails it immediately.
   input: [ (2, "b"), (1, "a"), (2, "c") ]   sorted by the number key


   STABLE sort   →  [ (1,"a"), (2,"b"), (2,"c") ]   "b" before "c" (as input)
   UNSTABLE sort →  [ (1,"a"), (2,"c"), (2,"b") ]   tie order NOT preserved


   The only test that tells them apart is one with a TIE (two 2s).

Huge collections force the resource question

Section titled “Huge collections force the resource question”

Every operation on a collection has to answer one question that a small test never asks: does it stream, or does it load everything into memory? The size axis has a far edge — “huge” — and at that edge behaviour that was invisible becomes fatal.

Two failures live here:

  • Memory. Code that does list(everything), SELECT * into an array, or read().splitlines() on a file holds the entire collection in RAM at once. On twelve rows that is nothing; on ten million rows it is an out-of-memory crash. The alternative — a stream, iterator, generator, or cursor — processes one element (or one page) at a time and uses bounded memory regardless of input size. The test is to run the operation against an input far larger than any single test row: a generated ten-million-element source, and a memory ceiling that the streaming version stays under and the buffering version blows through.
  • Time. An algorithm that is O(n²) — a nested loop, a “for each element, scan all the others” dedup — is imperceptible at n = 12 (144 operations) and catastrophic at n = 100,000 (ten billion operations). The huge test is what turns an asymptotic footgun into a failing test instead of a production incident.
Nested-loop dedup, operations ≈ n²:


   n = 12          →            144 ops   (instant)
   n = 1,000       →      1,000,000 ops   (a blink)
   n = 100,000     → 10,000,000,000 ops   (minutes — the "why is it hanging?")


The behaviour is identical; only the scale reveals the O(n²). A huge-input
test makes the scale a first-class test case instead of a 2 a.m. surprise.

Under the hood — why “many” hides both bugs

Section titled “Under the hood — why “many” hides both bugs”

A single “many” test with, say, five elements is a double blind spot. It is large enough that the empty and singleton edges are gone from view, and small enough that neither the O(n²) time cost nor the buffering memory cost is measurable. That is the worst of both worlds: it feels like a real test, so it lulls you, while covering none of the four sizes that actually change behaviour. This is exactly why the discipline is zero, one, many, and huge as four distinct cases — each guards a different failure mode (correctness at the empty/singleton edges; resource limits at the huge edge), and no single mid-size example covers any of them well.

The architect’s lens

Section titled “The architect’s lens”
  • Why does it exist? Because a collection carries two independent risk axes — its size (zero, one, many, huge) and its shape (duplicates, ordering) — and code is almost always written and tested against a comfortable middle that exercises neither axis at its edges.
  • What problem does it solve? It replaces “a list of three worked” with explicit checks at empty, singleton, and huge, plus deliberate duplicates, ties, and shuffled input — catching the fencepost crash, the 0/0 average, the unstable-sort reorder, the randomised-map flake, and the out-of-memory blowup before production meets them.
  • What are the trade-offs? More cases per collection, and the huge/streaming tests need generated inputs and resource assertions that are heavier than a plain unit test. The cost is real but small next to a len - 1 panic on an empty list or an O(n²) that hangs prod.
  • When should I avoid it? Never skip empty and singleton — they are cheap and high-yield. Scale the huge and streaming tests to reach: a fixed-size, trusted, always-small collection does not need a ten-million-element stress test, but anything fed by a file, a query, or a network must be assumed unbounded.
  • What breaks if I remove it? You ship code that works on the demo’s three rows and detonates on the real world’s zero rows or ten million: a loop that reads past the end, an average of nothing that returns NaN, output whose order flips between runs, and a “load it all into a list” that runs the box out of memory.

Check your understanding

Section titled “Check your understanding”
  1. Name the three canonical collection sizes to always test, plus the fourth that tests a different concern, and say what concern that fourth one guards.
  2. What is a fencepost error? Give the correct upper bound for a loop that compares each element to the next one, and explain why the singleton input is the case that proves it.
  3. sum([]) is 0 and count([]) is 0, but average([]) has no correct numeric value. Why, and what are the defensible choices for what average([]) should return?
  4. Give three distinct ordering assumptions that collection code silently makes, and for each name the specific kind of test input that exposes it.
  5. What single question does a “huge” input force that a small test never asks, and what are the two concrete failure modes at that far edge of the size axis?
Show answers
  1. Zero (empty), one (singleton), and many — the three sizes where correctness behaviour changes. The fourth is huge, which guards not correctness but resources: whether the operation finishes in reasonable time (an O(n²) that hangs) and fits in memory (buffering the whole thing vs streaming).
  2. A fencepost error confuses the number of gaps with the number of posts — a 10-section fence needs 11 posts — producing a loop that runs one time too many or too few. A pairwise “each element vs the next” loop must stop at len - 1 (indices 0 .. len-1), not len, or the last iteration reads off the end. The singleton proves it because a one-element list has zero pairs, so a correct loop must run its body zero times; an off-by-one runs it once and indexes past the end.
  3. sum([]) = 0 and count([]) = 0 because those are the identity elements — aggregating nothing yields the identity. average([]) = sum/count = 0/0, which is mathematically undefined, so there is no correct number to return. Defensible choices: raise an error, or return null/None (“no data”). Returning 0 is a lie, and letting 0/0 reach the CPU (silent NaN or a crash) is the one unacceptable option — the choice must be pinned by a test.
  4. (a) “It happened to be sorted” — code like binary search or a threshold scan that requires sorted input; exposed by a shuffled/unsorted input. (b) Unstable sort reordering equal elements; exposed by an input with deliberate ties (two elements with equal sort keys). (c) Undefined hash-map iteration order; exposed by a test that asserts the exact expected order, which fails under randomised or non-insertion iteration.
  5. It forces “does this stream, or does it load everything into memory?” The two failure modes are memory (buffering the whole collection into RAM causes an out-of-memory crash where a streaming/iterator version uses bounded memory) and time (an O(n²) algorithm that is instant on a dozen elements takes minutes or hours on hundreds of thousands).