Comparing and sorting text¶

Level: 201 · working knowledge

One line: == and < on a string compare UTF-8 bytes — fast, total, and identical on every machine. None of those words is alphabetical, which is why "Zebra" < "apple" is true and why a sorted list of Polish names comes back wrong in a way no test written in English will catch.

let header = "Content-Type";
let ascii = header.eq_ignore_ascii_case("content-type");   // true — ASCII data, no allocation
let mapped = header.to_lowercase() == "content-type";      // true — the whole table, two Strings
let exact = header == "content-type";                      // false — bytes, and only bytes

Three questions, and the last one is what == and sort() ask. The rest of this page is the gap between that and what you meant.

Lexicographic is not alphabetical¶

The two words get used as synonyms, and they are not. Lexicographic order compares two sequences element by element, taking the first difference — that is a rule about sequences, and it needs nothing but a way to order the elements. Alphabetical order is what a language's dictionary does, and it varies by language.

Rust orders strings lexicographically by their bytes, and std says so in the doc comment above the impl:

This is not necessarily the same as "alphabetical" order, which varies by language and locale.

— core/src/str/traits.rs, on impl Ord for str

The implementation is one line, and it is worth seeing, because it explains every surprise on this page at once:

impl Ord for str {
    fn cmp(&self, other: &str) -> Ordering {
        self.as_bytes().cmp(other.as_bytes())   // that is the whole thing
    }
}

PartialEq is the same shape — self.as_bytes() == other.as_bytes(). A String comparison is a byte comparison, so it is memcmp-fast, it is a total order so sort and BTreeMap accept it, and it gives the same answer on every machine in the world.

Because UTF-8 is ordered — a scalar value's encoding always sorts above the encoding of every smaller scalar value, which the run below checks over all 1,112,064 of them — byte order is code point order. So sort() gives you the Unicode code charts, in chart order: ASCII capitals, then ASCII lowercase, then everything else in the order the committee happened to assign it.

The verified output¶

Verified output of comparing_strings.rs — regenerated by tools/run_examples.py, never hand-typed.

1. `==` and `<` ask the bytes, and nothing else
   "Zebra" < "apple"  = true
   'Z' = 90, 'a' = 97   <- 90 < 97, so the capital wins
   a.cmp(b)                    = Less
   a.as_bytes().cmp(b.as_bytes()) = Less   <- the same call

2. Lexicographic is not alphabetical
   Adamczyk
   Echo
   Zawadzki
   zebra
   éclair
   Łukasiewicz
   żaba
   Three blocks, in this order: capitals, lowercase ASCII, then
   everything above U+007F. No alphabet is arranged that way.

3. ...but it IS code point order, which is worth knowing
   every scalar value encodes above the one before it: true
   So sorting bytes and sorting code points give the same order.
   That is a property of UTF-8, not of Rust — and it is why the
   answer is reproducible everywhere while still being wrong for a reader.

4. Two ways to ignore case, and what each one misses
   left                   right                     ascii  lowercase
   Content-Type           content-type               true       true
   ŁÓDŹ                   łódź                      false       true
   eq_ignore_ascii_case folds 26 letters and allocates nothing.
   to_lowercase() knows the whole table and allocates two Strings.

5. Lowercasing is not folding — the German ß
   "STRASSE".to_lowercase() = "strasse"
   "straße".to_lowercase() = "straße"
   equal after lowercasing?  false
   equal after UPPERcasing?  true
   Case mapping is not symmetric: 'ß' uppercases to "SS", and
   nothing lowercases "ss" back to 'ß'. Caseless matching wants case
   FOLDING, which std does not have.

6. ...so "uppercase both sides instead" is not the fix either
   'İ'.to_lowercase() = "i\u{307}" (2 chars)
   "İ".to_lowercase() == "i"  = false
   'ı'.to_uppercase() = "I"
   "ı".to_uppercase() == "I".to_uppercase() = true
   Turkish 'ı' and 'i' are different letters, and uppercasing merges
   them. Case mapping is locale-independent here by design: `str` has
   no locale, so it cannot have the Turkish answer or the other one.

7. Same letter, two spellings
   café and café print the same and are 5 bytes vs 6
   composed == decomposed              = false
   lowercased on both sides            = false
   No comparison in std repairs this. It is normalization, and it
   belongs to the unicode-normalization crate.

8. Sorting with a key, and paying for it once
   sort_by_key        allocated 20 Strings for 8 words
   sort_by_cached_key allocated 8 Strings for 8 words
   both orders: true
   ["Alpha", "Bravo", "charlie", "delta", "echo", "Foxtrot", "golf", "Hotel"]
   Case-insensitive is as far as a key gets you. A key that sorts
   Ł between L and M is a collation table, and that is a crate.

Which comparison you want¶

you want	ask	costs
exactly these bytes	`==`	nothing — it is `memcmp`
an ASCII token, case-insensitively	`eq_ignore_ascii_case`	nothing — folds `A`–`Z`, stops at the first difference
human text, case-insensitively	`to_lowercase` on both sides	two `String`s, and it is still not right
caseless matching, properly	case folding	not in std — a crate
two spellings of one letter to match	normalization	not in std — a crate
a language's alphabetical order	collation	not in std — a crate, and a table per language

The first two rows are the ones to reach for, and the boundary between them is the data, not the size: eq_ignore_ascii_case is correct for HTTP header names, scheme names, hex digits and file extensions, because those are defined over ASCII. It is wrong for anything a person typed.

The bottom three rows are three separate jobs std does not do, and each one fails differently.

Case folding is not case mapping¶

Lowercasing both sides is the folklore fix, and it has a counterexample you can type:

"STRASSE".to_lowercase() == "straße".to_lowercase();   // false
"STRASSE".to_uppercase() == "straße".to_uppercase();   // true

ß uppercases to SS — case mapping is not one character in, one character out, which Meet the char shows first. But nothing maps ss back down to ß, so the operation is not reversible and lowercasing loses the match that uppercasing keeps.

The right operation is neither. Case folding is a third mapping, defined by Unicode for exactly this purpose: fold both sides and compare, where ß folds to ss and the question of what anything "looks like" never arises. std has no case folding — to_lowercase and to_uppercase are case mapping, meant for display.

So uppercase both sides instead?¶

No, and the reason is a different language:

"ı".to_uppercase() == "I".to_uppercase();   // true — and in Turkish those are two letters

Turkish dotless ı and dotted i are as distinct as n and m; uppercasing merges them. Going the other way, İ (U+0130) lowercases to i plus a combining dot — two chars, three bytes — so "İ".to_lowercase() == "i" is false.

Neither is a bug. str has no locale, so it cannot have the Turkish answer or the non-Turkish one; std picks the locale-independent mapping and documents it. A program that needs the Turkish rule needs something that knows it is in Turkey.

The same letter, spelled twice¶

"café" == "cafe\u{301}";   // false — 5 bytes against 6

One is é (U+00E9); the other is e followed by a combining acute accent. They render identically, they are the same letter to a reader, and no comparison in std makes them equal — because this is not a comparison problem. It is normalization, a rewrite of one string into a canonical form, and it belongs to unicode-normalization ↗.

This is not an exotic case: macOS filesystems hand you decomposed text and most other sources hand you composed text, so the two spellings meet in ordinary programs that never touch an unusual alphabet.

Sorting, and paying for the key once¶

sort_by_key runs its key function inside the comparisons: std documents the cost as O(m · n · log n) where the key itself is O(m), so an allocating key allocates on that curve rather than once per element. sort_by_cached_key promises "at most once per element" and sorts the stored keys:

words.sort_by_key(|w| w.to_lowercase());          // 20 Strings for 8 words
words.sort_by_cached_key(|w| w.to_lowercase());   // 8

(The 20 is what this compiler's sort happened to ask for; only the 8 is promised, and only as an upper bound. std also notes the opposite case: for a cheap key — a field access, an integer — sort_by_key is the faster of the two, because the temporary Vec<(K, usize)> costs more than the re-evaluation saves.)

That is the mechanism for any sort you can express as a key, and case-insensitive is about as far as a key you write yourself will get you. The kata below writes one that really does file Ł between L and M, and then breaks it twice: the same four words need two different tables to come out right in German and in Swedish, and no per-character table at all can express Czech ch as one letter between H and I.

Collation is a data problem, not an algorithm problem. The Unicode Collation Algorithm (UTS #10 ↗) defines the machinery, CLDR ↗ supplies the per-language tailoring, and in Rust the implementation is icu_collator ↗ from ICU4X. std has none of it, and does not pretend to.

If you are coming from another language¶

Python. The default is the same and the escape hatches are worse.

Python		Rust
`sorted(names)` — by code point	same order, same surprise	`.sort()` — by UTF-8 byte, which is code point order
`a.lower() == b.lower()`	the same folklore fix	`a.to_lowercase() == b.to_lowercase()`
`a.casefold() == b.casefold()`	Python has folding; Rust does not	needs a crate
`locale.strxfrm`	process-global, not thread-safe, needs the locale installed	no equivalent, and no pretence of one
PyICU	the real answer	`icu_collator` — the same library underneath

str.casefold() is the one line of this table Python wins outright: it is the correct caseless comparison, it is in the standard library, and "straße".casefold() == "STRASSE".casefold() is True. Everything below it is a wash — strxfrm is a global-state trap that Rust simply does not offer, and both languages end at ICU.

What Python lacks is the word. Rust's doc comment says outright that its order is not alphabetical; Python's == documents nothing, because there is nothing to choose between. .NET calls this mode ordinal and makes every string API take it as a parameter, and Comparison has a mode ↗ is the Python page that borrows the name. Two of its measurements land on this table: Python has a third caseless answer in re.IGNORECASE, which agrees with casefold() on neither of the two rows above it, and locale.strxfrm — the strxfrm of the row below — raises on a string with an embedded NUL rather than comparing it, where .NET's culture-sensitive comparison is documented to ignore the NUL and call the strings equal. Rust, having neither API, has neither behaviour to get wrong.

ABAP (Not machine-checked — CI cannot run ABAP.) The same two orders exist, and ABAP puts them one keyword apart.

ABAP		Rust
`SORT itab BY field`	binary order of the internal representation	`.sort()` — byte order
`SORT itab BY field AS TEXT`	locale collation, from the text environment	no equivalent in std
`TRANSLATE lv TO UPPER CASE`	case mapping, same limits	`.to_uppercase()`
`lv1 = lv2` after both translated	the same folklore fix, with the same `ß` hole	the same hole

What changes: AS TEXT makes the locale-aware order available, which std does not — but it also makes it implicit, taken from the current text environment, so the same program sorts differently for two users and neither of them asked. Rust's position is that a locale-dependent answer should come from something you named. Which of those you prefer is a real argument; what is not is the assumption that SORT and SORT … AS TEXT are the same order with different performance.

Practice¶

One question, three answers — then a key that is actually Polish. Write same_word(a, b) three ways — byte equality, eq_ignore_ascii_case, and lowercasing both sides — and run all three over Content-Type/content-type, STRASSE/straße, ŁÓDŹ/łódź, and café spelled composed and decomposed. For each row, say which answer is right and which of the three (if any) gives it.

Then sort a list of Polish surnames three ways: sort(), sort_by_key(|n| n.to_lowercase()), and a two-level key of your own — base letter first, original text as the tiebreaker — that files Ć next to C, Ł between L and M, and Ż after Z.

Finish by breaking your own key twice. Write two more base-letter tables — one German, where ä ö ü are variants of their base vowels, and one Swedish, where å ä ö are three further letters after Z — and sort the same four words with each. Then run the Polish key over chata, hora, irsky and say why no per-character table can give the Czech answer.

Solution

comparing_strings_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

//! Kata solution: one `same_word` written three ways, then a two-level sort key
//! that puts 'Ł' between L and M — and the one row of the table that has to
//! change between German and Swedish.
//!
//!   rustc --edition 2024 comparing_strings_kata.rs -o /tmp/csk && /tmp/csk

/// Byte equality: what `==` does.
fn exact(a: &str, b: &str) -> bool {
    a == b
}

/// Folds `A`-`Z` only, and allocates nothing.
fn ascii_caseless(a: &str, b: &str) -> bool {
    a.eq_ignore_ascii_case(b)
}

/// Folds the whole Unicode case-mapping table, at the price of two `String`s.
fn mapped_caseless(a: &str, b: &str) -> bool {
    a.to_lowercase() == b.to_lowercase()
}

/// The Polish primary weight: the base letter, with case and accent discarded.
fn polish_base(c: char) -> char {
    match c {
        '\u{105}' | '\u{104}' => 'a',            // ą Ą
        '\u{107}' | '\u{106}' => 'c',            // ć Ć
        '\u{119}' | '\u{118}' => 'e',            // ę Ę
        '\u{142}' | '\u{141}' => 'l',            // ł Ł
        '\u{144}' | '\u{143}' => 'n',            // ń Ń
        '\u{f3}' | '\u{d3}' => 'o',              // ó Ó
        '\u{15b}' | '\u{15a}' => 's',            // ś Ś
        '\u{17A}' | '\u{179}' | '\u{17C}' | '\u{17B}' => 'z', // ź Ź ż Ż
        other => lowered(other),
    }
}

/// German: the umlauts are variants of their base vowel.
fn german_base(c: char) -> char {
    match c {
        '\u{e4}' | '\u{c4}' => 'a', // ä Ä
        '\u{f6}' | '\u{d6}' => 'o', // ö Ö
        '\u{fc}' | '\u{dc}' => 'u', // ü Ü
        other => lowered(other),
    }
}

/// Swedish: å ä ö are three more letters, and they come after Z. `{`, `|` and
/// `}` are the three code points immediately above 'z', so they stand in for
/// "a letter past the end of the alphabet" without inventing a wider type.
fn swedish_base(c: char) -> char {
    match c {
        '\u{e5}' | '\u{c5}' => '{', // å Å
        '\u{e4}' | '\u{c4}' => '|', // ä Ä
        '\u{f6}' | '\u{d6}' => '}', // ö Ö
        other => lowered(other),
    }
}

fn lowered(c: char) -> char {
    c.to_lowercase().next().unwrap_or(c)
}

/// A two-level key, which is the smallest honest shape a collation key has:
/// compare base letters first, and only break a tie with the original text.
fn key(word: &str, base: fn(char) -> char) -> (String, String) {
    (word.chars().map(base).collect(), word.to_lowercase())
}

fn main() {
    println!("Round 1 -- one question, three answers");
    let pairs = [
        ("Content-Type", "content-type", "ASCII token"),
        ("STRASSE", "stra\u{df}e", "German \u{df}"),
        ("\u{141}\u{d3}D\u{179}", "\u{142}\u{f3}d\u{17a}", "Polish diacritics"),
        ("caf\u{e9}", "cafe\u{301}", "one accent, two spellings"),
    ];
    println!("   {:<16} {:<16} {:>7} {:>7} {:>8}  {}", "a", "b", "==", "ascii", "lowered", "what it is");
    for (a, b, note) in pairs {
        println!(
            "   {:<16} {:<16} {:>7} {:>7} {:>8}  {note}",
            format!("{a:?}"),
            format!("{b:?}"),
            exact(a, b),
            ascii_caseless(a, b),
            mapped_caseless(a, b)
        );
    }
    println!("   Row 2 is the one to look at: every answer is `false`, and the right");
    println!("   answer is `true`. Caseless matching is case FOLDING, and std has");
    println!("   none -- '\u{df}' folds to \"ss\", which no case MAPPING will do for you.");
    println!("   Row 4 is not a case question at all; the two spellings differ before");
    println!("   any case rule is applied, and no comparison in std repairs that.");

    println!("\nRound 2 -- three orders over one list");
    let names = [
        "\u{141}ukasiewicz",
        "Lewandowski",
        "Zawadzki",
        "\u{17B}eromski",
        "Adamczyk",
        "\u{106}wik\u{142}a",
    ];

    let mut byte_order = names;
    byte_order.sort();
    println!("   sort()                     {byte_order:?}");

    let mut lowered_order = names;
    lowered_order.sort_by_key(|n| n.to_lowercase());
    println!("   sort_by_key(to_lowercase)  {lowered_order:?}");

    let mut collated = names;
    collated.sort_by_cached_key(|n| key(n, polish_base));
    println!("   sort_by_cached_key(key)    {collated:?}");
    println!("   Only the third is Polish: '\u{106}' next to C, '\u{141}' between L and M, '\u{17B}'");
    println!("   after Z. The first two agree with each other and with nobody else.");

    println!("\nRound 3 -- the same list, two languages, one row of the table");
    let words = ["Zetter", "\u{c4}pfel", "Apfel", "\u{d6}ver"];
    let mut german = words;
    german.sort_by_cached_key(|w| key(w, german_base));
    println!("   german_base   {german:?}");
    let mut swedish = words;
    swedish.sort_by_cached_key(|w| key(w, swedish_base));
    println!("   swedish_base  {swedish:?}");
    println!("   Neither is a bug. German files '\u{c4}' under A; Swedish makes it the");
    println!("   27th letter. The two keys differ in three match arms and produce");
    println!("   two different, correct orders for the same four words.");

    println!("\nRound 4 -- what a per-character table cannot say at all");
    let czech = ["chata", "hora", "irsky"];
    let mut czech_sorted = czech;
    czech_sorted.sort_by_cached_key(|w| key(w, polish_base));
    println!("   by character  {czech_sorted:?}");
    println!("   Czech sorts 'ch' as ONE letter between H and I, so the answer wanted");
    println!("   is [\"hora\", \"chata\", \"irsky\"]. No mapping from char to char can");
    println!("   express a two-character letter, so the shape of the key is wrong");
    println!("   here, not its contents.");
    println!("   The order is not a property of the string. It is a property of the");
    println!("   LANGUAGE -- which is why correct collation ships as data (CLDR, ICU)");
    println!("   rather than as an algorithm you can derive.");
}

Verified output of comparing_strings_kata.rs — regenerated by tools/run_examples.py, never hand-typed.

Round 1 -- one question, three answers
   a                b                     ==   ascii  lowered  what it is
   "Content-Type"   "content-type"     false    true     true  ASCII token
   "STRASSE"        "straße"           false   false    false  German ß
   "ŁÓDŹ"           "łódź"             false   false     true  Polish diacritics
   "café"           "cafe\u{301}"      false   false    false  one accent, two spellings
   Row 2 is the one to look at: every answer is `false`, and the right
   answer is `true`. Caseless matching is case FOLDING, and std has
   none -- 'ß' folds to "ss", which no case MAPPING will do for you.
   Row 4 is not a case question at all; the two spellings differ before
   any case rule is applied, and no comparison in std repairs that.

Round 2 -- three orders over one list
   sort()                     ["Adamczyk", "Lewandowski", "Zawadzki", "Ćwikła", "Łukasiewicz", "Żeromski"]
   sort_by_key(to_lowercase)  ["Adamczyk", "Lewandowski", "Zawadzki", "Ćwikła", "Łukasiewicz", "Żeromski"]
   sort_by_cached_key(key)    ["Adamczyk", "Ćwikła", "Lewandowski", "Łukasiewicz", "Zawadzki", "Żeromski"]
   Only the third is Polish: 'Ć' next to C, 'Ł' between L and M, 'Ż'
   after Z. The first two agree with each other and with nobody else.

Round 3 -- the same list, two languages, one row of the table
   german_base   ["Apfel", "Äpfel", "Över", "Zetter"]
   swedish_base  ["Apfel", "Zetter", "Äpfel", "Över"]
   Neither is a bug. German files 'Ä' under A; Swedish makes it the
   27th letter. The two keys differ in three match arms and produce
   two different, correct orders for the same four words.

Round 4 -- what a per-character table cannot say at all
   by character  ["chata", "hora", "irsky"]
   Czech sorts 'ch' as ONE letter between H and I, so the answer wanted
   is ["hora", "chata", "irsky"]. No mapping from char to char can
   express a two-character letter, so the shape of the key is wrong
   here, not its contents.
   The order is not a property of the string. It is a property of the
   LANGUAGE -- which is why correct collation ships as data (CLDR, ICU)
   rather than as an algorithm you can derive.

Po polsku¶

Porównywanie tekstu (string comparison) w Ruście to porównywanie bajtów UTF-8 — == i < sprowadzają się do jednej linijki w core: self.as_bytes().cmp(other.as_bytes()). Stąd bierze się cała reszta. Porządek leksykograficzny (lexicographic) to reguła o ciągach: porównaj element po elemencie i zdecyduj na pierwszej różnicy. Porządek alfabetyczny (alphabetical, a ściślej collation — uporządkowanie językowe) to reguła o języku. Angielska dokumentacja std mówi to wprost, i warto to zapamiętać jako parę pojęć, bo po polsku bywają mylone równie chętnie.

Dla polskiego czytelnika konsekwencja jest natychmiastowa: sort() na liście nazwisk wyrzuci Ćwikła, Łukasiewicz i Żeromski na sam koniec, za Zawadzki, bo Ł to U+0141, a Z to U+005A. Nie naprawi tego to_lowercase() — po zmniejszeniu liter ł nadal ma numer 322. Polska norma stawia ą tuż za a, ł za l, a ż za z, i żeby to uzyskać, potrzebny jest klucz sortowania (sort key): najpierw litera bazowa, potem oryginał jako rozstrzygnięcie remisu. Kata na tej stronie każe taki klucz napisać — a potem pokazuje, że ta sama tablica jest poprawna dla niemieckiego i błędna dla szwedzkiego, i że czeskiego ch jako jednej litery nie da się w niej wyrazić w ogóle. To jest właśnie powód, dla którego prawdziwe uporządkowanie językowe jest danymi (CLDR, ICU), a nie algorytmem.

Druga pułapka jest cichsza i dotyczy porównywania „bez uwzględniania wielkości liter". eq_ignore_ascii_case obejmuje tylko 26 liter ASCII, więc ŁÓDŹ i łódź uzna za różne; to_lowercase() na obu stronach zna całą tablicę Unicode i uzna je za równe — ale niemieckie STRASSE i straße przegapi, bo poprawną operacją jest tu case folding (składanie wielkości liter), którego w std nie ma. Trzecia to normalizacja: ó bywa jednym znakiem (NFC) albo o z osobnym znakiem diakrytycznym (NFD — typowe dla danych z macOS-a), a dla == to dwa różne łańcuchy wyglądające identycznie.

Szukaj po polsku: sortowanie polskich znaków diakrytycznych · porządek leksykograficzny a alfabetyczny · klucz sortowania · normalizacja Unicode NFC NFD · rust unicode collation icu · rust eq_ignore_ascii_case · rust casefold