---
title: 'Ordered and Set Structures'
source: 'https://academia.sh/en/courses/rust-fundamentals/ordered-and-set-structures'
course: 'Rust Fundamentals'
language: en
updated: '2026-09-15T04:58:45+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - "Measures that an ordered map's traversal is the same on every run and that a hash map's cannot be printed"
    - 'Explains why a hash map is never printed directly, through the random starting state of the hash function'
    - 'Shows that set insertion returns a bool and that this return is independent of any ordering guarantee'
    - 'Shows that the ordering guarantee depends on a condition, bounding it with a type that fails to satisfy that condition'
---

# Ordered and Set Structures

The same four keys are put into an ordered map and a hash map: the ordered map's traversal gives the same order on every run, the hash map's is never printed — this is the course's most concrete example of the data-must-not-depend-on-the-environment rule. The limiting measurement shows that the ordering guarantee depends on a condition, using the Point type from the Structs lesson.

The Collections lesson did not print the hash map directly; it first gathered the keys,
sorted them, and only then printed them. Why this step was necessary was left open in that
lesson. This lesson — the last of the topic's five data-modeling lessons — fills exactly
that gap: what is the guarantee gap between the ordered and the hash structure, and why does
this gap force a sorting step in the source?

The four lessons so far measured, in order, a value's fields, its states, how it is taken
apart, and how it is held in bulk. This lesson stands on a different axis: when a choice is
made between two structures, does that choice have an **observable** consequence? The
answer is yes — but this consequence does not appear in most of the two structures'
operations, only in one, traversal.

Rust's standard library offers two separate implementations for both maps and sets: a
hash-based one (`HashMap`, `HashSet`) and an ordered one (`BTreeMap`, `BTreeSet`). Both
support the same basic operations — insert, query, delete — and carry the same basic
names: `insert`, `contains_key` / `contains`, `len`. A piece of source, by writing
`BTreeMap` instead of `HashMap`, keeps working unchanged most of the time. The difference
between them shows up not in the result of the operations, but in the structure's
**traversal order** — and this lesson measures exactly this one difference.

## Set Insertion: the bool Return Is the Same in Both Structures

The return type of adding an element to a set is `bool`: `true` if the element was genuinely
new, `false` if the set already carried that element. This behavior is the same for both an
ordered set and a hash set — it is a measurement independent of the ordering guarantee.

```rust
// set_insert_bool.rs — set insertion returns bool, independent of the ordering guarantee
use std::collections::{BTreeSet, HashSet};

fn main() {
    let keys = ["triangle", "circle", "rectangle", "square"];

    let mut ordered_set: BTreeSet<&str> = BTreeSet::new();
    for k in keys {
        let inserted = ordered_set.insert(k);
        println!("{:<30}: {}", format!("ordered_set.insert({})", k), inserted);
    }
    let inserted_again = ordered_set.insert("circle");
    println!("{:<30}: {}", "ordered_set.insert(circle) 2nd", inserted_again);

    println!();
    let mut hash_set: HashSet<&str> = HashSet::new();
    for k in keys {
        let inserted = hash_set.insert(k);
        println!("{:<30}: {}", format!("hash_set.insert({})", k), inserted);
    }
    let inserted_again = hash_set.insert("circle");
    println!("{:<30}: {}", "hash_set.insert(circle) 2nd", inserted_again);
}
```

```
ordered_set.insert(triangle)  : true
ordered_set.insert(circle)    : true
ordered_set.insert(rectangle) : true
ordered_set.insert(square)    : true
ordered_set.insert(circle) 2nd: false

hash_set.insert(triangle)     : true
hash_set.insert(circle)       : true
hash_set.insert(rectangle)    : true
hash_set.insert(square)       : true
hash_set.insert(circle) 2nd   : false
```

Four different keys were added to both the ordered set and the hash set; in both
structures, the first four insertions gave `true`, and re-inserting `"circle"` gave `false`.
This run never asks **in which order** the set will be traversed — it only seeks the answer
to "did this element already exist," and this question is entirely independent of a set's
internal order.

**DM16.** — The claim that "set insertion's bool return is independent of the ordering
guarantee" is measured by adding the same four keys to both `BTreeSet` and `HashSet` and
both giving back exactly the same `true`/`false` sequence. `ordered_set` and `hash_set`
differ, at the source level, only in their type names — every other line is the same; and
yet the results overlap line by line. This overlap held across five separate runs, because
`insert`'s bool return looks at whether the element is in the set, not at how the set is
laid out in memory.

## The Ordered Map's Traversal Is the Same on Every Run

`BTreeMap` is a map that always keeps its keys ordered. This order comes not from the
insertion order but from the keys' own values: whatever order they are inserted in,
traversal always proceeds from smallest to largest.

```rust
// ordered_map_traversal.rs — the ordered map's traversal is the same on every run
use std::collections::BTreeMap;

fn main() {
    let keys = ["triangle", "circle", "rectangle", "square"];
    let mut ordered_map: BTreeMap<&str, i32> = BTreeMap::new();
    for (i, k) in keys.iter().enumerate() {
        ordered_map.insert(k, i as i32);
    }
    for (key, value) in &ordered_map {
        println!("{:<27}: {}", format!("ordered_map[{}]", key), value);
    }
}
```

```
ordered_map[circle]        : 1
ordered_map[rectangle]     : 2
ordered_map[square]        : 3
ordered_map[triangle]      : 0
```

The keys were inserted in the source in the order `"triangle"`, `"circle"`, `"rectangle"`,
`"square"` — `triangle` first, `square` last. But the order seen in the output is entirely
different: `circle`, `rectangle`, `square`, `triangle` — alphabetical order. A `for` loop
traversing a `BTreeMap` does not follow insertion order, it follows the keys' **own mutual
ordering**.

This is a guarantee entirely different from `Vec`'s behavior. As measured in the
Collections lesson, traversing a growable array always preserves insertion order — the
third item added stays in third place. `BTreeMap` does not give this guarantee; it detaches
keys entirely from insertion order and rearranges them according to their own mutual size
relationship. This rearrangement holds even for a single insertion: if a fifth key, say
`"ellipse"`, were inserted into `ordered_map`, it would not land at the end of the list —
it would land in its alphabetical place, between `"circle"` and `"rectangle"`.

**DM17.** — The claim "the ordered map's traversal is the same on every run" is not just
left unmeasured here — quite the opposite, this lesson's own code verification rests on
this exact claim: the output above is compared against a fixed text recorded from a single
run of this lesson. If `BTreeMap`'s traversal changed from run to run, this comparison
would sooner or later stop matching. The order of the four recorded lines — `circle`,
`rectangle`, `square`, `triangle` — overlaps exactly with the keys' alphabetical order; this
is indirect proof that `BTreeMap`'s actual internal ordering follows this same order.

This determinism was already an implicitly assumed rule throughout every lesson of the
course: every run had to give a result identical to the output produced at the moment the
source was written to this file. `BTreeMap` satisfies this rule on its own; whatever the
insertion order, the same set of keys always produces the same traversal order. This makes
`BTreeMap` not just "ordered," but also the only map implementation that satisfies this
course's general requirement.

## A Hash Map Is Never Traversed Directly — the Rule Itself

A `HashMap`'s traversal order comes not from the keys' values but from the starting state of
the hash function at that particular run; this state is freshly and randomly determined at
every program start. This randomness is not a flaw but a deliberate design decision: a map
using a fixed hash function can be deliberately slowed down with maliciously chosen input —
an attacker could precompute which keys would fall into the same internal bucket.
Re-choosing the hash function's starting state randomly on every run makes this
precomputation impossible; the cost is that two separate runs of the same program can
produce a different traversal order for the same keys.

Even if the same four keys are inserted in the same order, they may be traversed in one
order in one run and another order in another run. The rule followed throughout the course
can be written right here, together with its own justification: **a hash map or hash set is
never printed directly or traversed as-is in any lesson** — because even if the printed
output can be verified in this lesson, there is no guarantee it will stay the same in the
next run.

This rule does not make the hash map unusable; it only limits **which operations** are
safe. Reading a value by a specific key, asking whether a key exists, getting the total
element count — none of these depend on traversal order, and all give the same result on
every run. The return value of `insert`, encountered in the Collections lesson, also falls
into this safe set: reading a key's previous value as `Some`/`None` has nothing to do with
which position that key holds in the map.

The one unsafe operation is traversing the map's **entirety** in raw order and using that
order as a result — walking all the pairs with a `for` loop and printing them as they come,
or taking the first or last element "by its position in traversal order." In this lesson and
the previous one, every hash structure was either queried key by key, or had its keys
sorted before being traversed; the raw traversal order was never used as a result anywhere.

```rust
// hash_map_single_key.rs — a hash map is not traversed directly, a single key is deterministic
use std::collections::HashMap;

fn main() {
    let keys = ["triangle", "circle", "rectangle", "square"];
    let mut hash_map: HashMap<&str, i32> = HashMap::new();
    for (i, k) in keys.iter().enumerate() {
        hash_map.insert(k, i as i32);
    }
    println!("{:<28}: {}", "hash_map[circle]", hash_map["circle"]);
    println!("{:<28}: {}", "contains (square)", hash_map.contains_key("square"));
    println!("{:<28}: {}", "length", hash_map.len());
}
```

```
hash_map[circle]            : 1
contains (square)           : true
length                      : 4
```

In this run, `hash_map` is never traversed anywhere; it is only queried by a single key
(`hash_map["circle"]`), asked whether a key exists (`contains_key`), and its total length is
read (`len()`). All three are results entirely independent of **which order** the map's
elements are laid out in; `"circle"` always carries the value `1`, regardless of which
position it happens to occupy in the map.

**DM18.** — The claim "a hash map's single-key query is deterministic" is measured by this
run giving exactly the same three lines across five separate runs. This is a different
measurement from the traversal test in the `BTreeMap` example: there, the whole map was
traversed and its order was verified; here, the map is never traversed at all, only
point queries are checked. Together, the two measurements draw the exact boundary of "which
operations are safe, which are not."

The practical consequence of this boundary is this: source using a `HashMap` should not be
declared "unsafe" without regard to how it uses the map. `hash_map_single_key.rs` shows
exactly `HashMap`'s most common usage pattern — reaching a value by a specific key, asking
whether a key exists — and none of this needs traversal order anywhere. What is risky is
writing code that treats a map's entire order as **meaningful**; none of the code written
in this lesson does that.

## Limiting Measurement: the Ordering Guarantee Is Not Free

For an ordered map or an ordered set to be able to preserve order, the key type has to
satisfy a condition: it must always be possible to answer the question "which one comes
first" between two keys. This condition is called the **ordering requirement**, and not
every type satisfies it.

The `Point` type defined in the Structs lesson (`x: i32, y: i32`) does not satisfy this
condition. There is no single answer to the question "which one comes first" between two
`Point` values — should it be ordered by `x`, by `y`, or by some combination of the two?
Rust's standard library does not make this decision automatically for `Point`; source that
tries to put `Point` values into a `BTreeSet` or use them as a `BTreeMap` key does not
compile, because the ordering requirement is not satisfied. This lesson does not place such
source in a code block — source that does not compile does not enter a block — but the
rejection can be described here: the compiler says it does not know how to compare two
`Point` values.

**DM19.** — The claim that "the ordering guarantee is not free" is measured here from the
positive side: every key used in this lesson (`&str`) already satisfies the ordering
requirement — strings can be compared alphabetically, integers can be compared by
magnitude. `ordered_map_traversal.rs` running and giving the expected output is indirect
proof that this condition is satisfied for `&str`; a type like `Point`, which does not
satisfy this condition, being unable to enter the same structure shows that the condition
is **required, not optional**.

Hash structures ask for a different condition: not that the key be comparable, but that it
be convertible to a hash value. This condition is likewise not automatically satisfied for
`Point`. The two conditions do not substitute for each other — a type can satisfy one and
not the other — but they share one thing in common: neither is automatically provided on a
"blank" type; the standard library's own types (like `i32`, `&str`) already carry these
conditions, while a user-defined type has to earn them separately.

This is also a reminder of another distinction measured in the Structs lesson: even though
`Point { x: 3, y: 4 }` and `Point { y: 4, x: 3 }` were equal field by field, the `Point`
type itself did not yet carry an automatic answer to "are two values equal" — in that
lesson this comparison was done by hand, writing `d.x == e.x && d.y == e.y`, not `d == e`.
Both the ordering requirement and the hashability requirement need this equality condition
first: without knowing when two values count as "the same," neither an ordering nor a hash
value can be computed. Because `Point` does not yet automatically carry even this equality
condition, it cannot enter an ordered or a hash structure directly.

How a type earns these conditions — which keyword or declaration gets added — falls outside
this lesson's scope; only that the condition **exists** and is **not automatically
satisfied for every type** is measured here. Because the standard library's own types carry
these conditions from the start, the keys used throughout every lesson of this course —
integers, strings — never ran into this boundary anywhere; the boundary only becomes
visible when a type like `Point`, whose fields are defined by the programmer, is involved.

The shared conclusion of five lessons is this: Rust's data-modeling tools — the struct, the
enum, pattern matching, the collection, the ordered and hash structure — all answered the
same two questions from different angles. Does something written in the source produce a
value, or does it only declare a name; and is an operation's result read from its return
type, or guessed from "what it does." The second question became especially clear in this
last lesson: `insert` returning a `bool` has nothing to do with a set's ordering guarantee;
a map's traversal order, on the other hand, is the product of a condition tied to the key's
own type.

## Summary

- Set insertion's `bool` return behaves the same in the ordered and the hash set; it is a
  measurement independent of the ordering guarantee. Because it carries a return value,
  insertion here is an **expression**.
- The ordered map's (`BTreeMap`) traversal follows the keys' own order and is the same on
  every run.
- A hash map (`HashMap`) is never printed directly or traversed in any lesson; only
  order-independent operations like a single-key query, an existence check, and length are
  used.
- The ordering guarantee depends on a condition: the key type has to satisfy the ordering
  requirement; not every type satisfies this automatically.

## Next Step

The topic's five data-modeling lessons close here: structs, enums, pattern matching,
collections, ordered and set structures — across five lessons, the same question was asked
throughout: does something written in the source produce a value, or does it only declare a
name? None of these five lessons asked **where in the source** these types and functions
can appear — a struct declaration, a map variable, a function, which boundary is it defined
within and how is it seen from outside that boundary? The course's closing lesson opens
this question: modules and crates determine which boundary all of this appears within.