Ordered and Set Structures

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.

// 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.

// 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.

// 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.