Lexicographic comparison

Why this matters

A program often has to put words in order. A contact list is shown alphabetically. A search returns results sorted by name. A program checks whether a word comes before another word in a dictionary. Each of these needs a rule that says which of two strings is first. That rule is called lexicographic order, from the Greek word for a dictionary.

The rule looks simple, but it has two surprises. First, the computer compares characters by their numeric codes, so uppercase letters come before lowercase ones. A list sorted by plain comparison can look wrong to a person. Second, the comparison works on the text itself, so "10" comes before "9". This lesson explains both surprises and shows how to get the order you want.

The lesson builds on std::string, std::vector, for loops and the idea of passing values to functions. It uses std::sort and std::ranges::sort, which put a list into order.

The idea: compare one character at a time

A dictionary compares two words by looking at their first letters. If the first letters differ, the word with the earlier letter comes first. If the first letters are the same, it looks at the second letters, and so on. If one word runs out of letters while the other still has some, the shorter word comes first.

Take apple and banana:

• The first letters are a and b.
• a comes before b, so apple comes before banana.

Take apple and apples:

• The first five letters are the same.
• apple ends there, and apples has one more letter.
• The shorter word comes first, so apple comes before apples.

This is the whole method. Compare the characters one position at a time. The first position where the two strings differ decides the order. A computer does exactly this, with one extra detail: it does not know what a letter is. It compares numbers.

Characters are numbers

Every character is stored as a number. The most common older table of these numbers is called ASCII, which is short for American Standard Code for Information Interchange. ASCII gives the capital letters A to Z the numbers 65 to 90, and the lowercase letters a to z the numbers 97 to 122. The digits 0 to 9 are 48 to 57.

The next program prints the number behind some characters. The int('A') part converts a character to its number.

#include <iostream>
 
int main() {
    std::cout << "A=" << int('A') << " Z=" << int('Z') << "\n";
    std::cout << "a=" << int('a') << " z=" << int('z') << "\n";
    std::cout << "0=" << int('0') << " B=" << int('B') << "\n";
}

A=65 Z=90
a=97 z=122
0=48 B=66

The number for B is 66, and the number for a is 97. Since 66 is less than 97, the string "B" comes before "a" in the comparison. This is why capital letters appear before lowercase ones when a list is sorted by plain comparison. The ordering is not about the alphabet. It is about the numbers.

Digits have lower numbers than letters. The number for 0 is 48 and the number for 9 is 57. When you compare "10" and "9", the computer looks at the first character. '1' is 49 and '9' is 57, so "10" comes first, even though 10 is larger than 9 as a number. The comparison works on text, not on the values the text stands for.

Example 1: comparing with less-than and compare()

C++ strings can be compared with the < operator, and the std::string type has a method called compare that gives a number. A method is a function that belongs to an object, and you call it with a dot. The compare method returns a negative number when the first string comes first, zero when they are equal, and a positive number when the first string comes after.

#include <iostream>
#include <string>
 
int main() {
    std::cout << std::boolalpha;
    std::cout << "B before a: " << (std::string("B") < std::string("a")) << "\n";
    std::cout << "apple before banana: " << (std::string("apple") < std::string("banana")) << "\n";
    std::cout << "apple before apples: " << (std::string("apple") < std::string("apples")) << "\n";
    std::cout << "Zebra before apple: " << (std::string("Zebra") < std::string("apple")) << "\n";
    std::cout << "\"10\" before \"9\": " << (std::string("10") < std::string("9")) << "\n";
 
    std::cout << "compare(apple, banana) = " << std::string("apple").compare("banana") << "\n";
    std::cout << "compare(apple, apple) = " << std::string("apple").compare("apple") << "\n";
    std::cout << "compare(banana, apple) = " << std::string("banana").compare("apple") << "\n";
}

B before a: true
apple before banana: true
apple before apples: true
Zebra before apple: true
"10" before "9": true
compare(apple, banana) = -1
compare(apple, apple) = 0
compare(banana, apple) = 1

std::boolalpha makes true and false print as words instead of as 1 and 0. The first five lines show the rules from the last section. Each comparison ends at the first position where the strings differ, or at the end of the shorter string.

The compare method returns a number. The C++ standard promises only the sign, so you should test with < 0, == 0 or > 0, and not depend on the exact number. The sign is the part that matters.

Example 2: strcmp for C strings

Before std::string, C++ programs stored text as a C string. A C string is an array of characters that ends with a zero byte, which is a hidden character with the number 0. The zero byte marks where the text stops. String literals such as "hi" are C strings. The function std::strcmp compares two C strings. It is declared in the <cstring> header.

#include <cstring>
#include <iostream>
 
int main() {
    std::cout << "strcmp(B, a) = " << std::strcmp("B", "a") << "\n";
    std::cout << "strcmp(apple, apple) = " << std::strcmp("apple", "apple") << "\n";
    std::cout << "strcmp(banana, apple) = " << std::strcmp("banana", "apple") << "\n";
 
    char buf1[] = "hi";
    char buf2[] = "hi";
    std::cout << "strcmp equal: " << (std::strcmp(buf1, buf2) == 0) << "\n";
}

strcmp(B, a) = -1
strcmp(apple, apple) = 0
strcmp(banana, apple) = 1
strcmp equal: 1

strcmp follows the same rule as compare. It returns a negative number, zero, or a positive number. On this system the first result is -1, but the C standard only promises a negative value. Other C libraries can return a different negative number, so test the sign.

The most common mistake with strcmp is to treat its result as a true or false answer. Zero means the strings are equal, which is false in a yes-or-no test. So if (std::strcmp(word, "stop")) runs when the word is not stop. The right test is == 0. The mistakes section below shows this error again.

Example 3: sorting names without caring about case

Plain sorting puts every capital letter before every lowercase letter. The next program sorts six words with std::ranges::sort and then with a case-insensitive comparison.

#include <algorithm>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string>
#include <vector>
 
bool ci_less(const std::string& a, const std::string& b) {
    return std::ranges::lexicographical_compare(a, b, {},
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); },
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); });
}
 
void show(const char* label, const std::vector<std::string>& v) {
    std::cout << label << ":";
    for (const auto& s : v) std::cout << " " << s;
    std::cout << "\n";
}
 
int main() {
    std::vector<std::string> words = {"banana", "Apple", "cherry", "apricot", "Blueberry", "date"};
 
    auto plain = words;
    std::ranges::sort(plain);
    show("plain sort", plain);
 
    auto ci = words;
    std::ranges::sort(ci, ci_less);
    show("case-insensitive", ci);
}

plain sort: Apple Blueberry apricot banana cherry date
case-insensitive: Apple apricot banana Blueberry cherry date

The plain sort puts Apple and Blueberry first, because their first letters are capitals. The case-insensitive sort puts them among the other words.

The function ci_less is a predicate, which is a function that returns true or false and tells the sort whether the first item comes before the second. It works like this:

• std::ranges::lexicographical_compare walks through both strings one character at a time, like a dictionary.
• The two lambdas are small unnamed functions. A lambda is a short function written where it is used. Each one receives a character and returns its lowercase form. The lambdas are called projections. A projection changes each item before the comparison, and the comparison then uses the changed value. Here the items are the characters, and the change is lowercasing.
• std::tolower takes an int. The cast to unsigned char makes sure a character with a negative value is not passed to tolower. Passing a negative value is undefined behaviour, which means the language makes no promise about the result.

Now test the predicate on the three pairs that matter:

#include <algorithm>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string>
 
bool ci_less(const std::string& a, const std::string& b) {
    return std::ranges::lexicographical_compare(a, b, {},
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); },
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); });
}
 
int main() {
    std::cout << std::boolalpha;
    std::cout << "B before a, ignoring case: " << ci_less("B", "a") << "\n";
    std::cout << "Apple before apple: " << ci_less("Apple", "apple") << "\n";
    std::cout << "apple before Apple: " << ci_less("apple", "Apple") << "\n";
}

B before a, ignoring case: false
Apple before apple: false
apple before Apple: false

All three give false. B and a are different letters, but b is after a, so B is not before a. Apple and apple are equal once case is ignored, so neither comes before the other.

Ties and stable sorting

When two items are equal under the comparison, a sort may put them in any order. std::ranges::stable_sort keeps equal items in the order they were in before the sort. The next program shows the difference with a list that has several spellings of the same word.

#include <algorithm>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string>
#include <vector>
 
bool ci_less(const std::string& a, const std::string& b) {
    return std::ranges::lexicographical_compare(a, b, {},
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); },
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); });
}
 
int main() {
    std::vector<std::string> ties = {"apple", "Banana", "Apple", "banana", "APPLE"};
    std::ranges::stable_sort(ties, ci_less);
    for (const auto& s : ties) std::cout << s << " ";
    std::cout << "\n";
}

apple Apple APPLE Banana banana 

The three spellings of apple keep their input order: apple, then Apple, then APPLE. The same holds for Banana and banana. Use stable_sort when the order of equal items matters, for example when a list was already sorted by date and you sort it again by name.

Comparing for equality without case

Sometimes you do not need an order, only a yes or no answer to "are these the same, ignoring case?". Two strings are equal under a comparison when neither comes before the other. The next function uses that rule.

#include <algorithm>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string>
 
bool ci_less(const std::string& a, const std::string& b) {
    return std::ranges::lexicographical_compare(a, b, {},
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); },
        [](char c) { return std::tolower(static_cast<unsigned char>(c)); });
}
 
bool same_ignoring_case(const std::string& a, const std::string& b) {
    return !ci_less(a, b) && !ci_less(b, a);
}
 
int main() {
    std::cout << std::boolalpha;
    std::cout << same_ignoring_case("Hello", "hELLO") << "\n";
    std::cout << same_ignoring_case("Hello", "Hell") << "\n";
}

true
false

"Hello" and "hELLO" are equal, so neither comes before the other. "Hell" comes before "Hello" because it is shorter, so the function returns false.

Common mistakes

Expecting capitals to sort in alphabetical position

With plain comparison, Zebra comes before apple, because Z (90) is less than a (97). Many people expect apple to come before Zebra. The fix is the case-insensitive comparison from Example 3. Do not change the data to make the sort look right.

Comparing C strings with ==

For two std::string values, == compares the text. For two C strings, such as char arrays, == compares addresses. An address is the place in memory where the array starts. Two arrays always have different addresses, even when they hold the same text:

#include <iostream>
 
int main() {
    char a[] = "hi";
    char b[] = "hi";
    std::cout << (a == b) << "\n";
}

warning: comparison between two arrays is deprecated in C++20 [-Warray-compare]
0

The result is 0, which means false, even though both arrays hold hi. Use std::strcmp(a, b) == 0 to compare the text, or use std::string. g++ 15 prints this warning even without -Wall, so keep warnings turned on.

Testing strcmp as a yes or no

As shown in Example 2, strcmp returns zero for equal strings. A test such as if (std::strcmp(word, "stop")) is true for every word except stop. Write == 0 in the test.

Assuming std::sort keeps equal items in order

std::ranges::sort and std::sort do not promise to keep equal items in their original order. The standard does not say which order equal items end in, so the result can differ between compilers. When order among equal items matters, use std::ranges::stable_sort.

Expecting numbers in text to sort as numbers

Strings that hold numbers are compared character by character. "10" comes before "9", and "100" comes before "20". To sort numbers by value, store them as int or double values, or convert them before sorting.

Passing a negative char to tolower

The tolower function expects a value between 0 and 255 or the special value EOF. A char can be negative on some systems. The cast to unsigned char in the predicate avoids that. Leaving it out is undefined behaviour, so it may work on your machine and fail on another.

Java's compareTo

The Java method compareTo makes the same comparison and returns the same kind of result. The Java track of the course covers it. One detail is useful when you read Java code next to C++ code: Java returns the difference between the first two characters that differ. "B".compareTo("a") gives -31, because 66 minus 97 is -31. The C++ compare method gave -1 in this lesson, and the exact value is not part of the rule.

Practice

Exercise 1. Sort the three words "Zoo", "apple" and "Apple" with std::ranges::sort, using the plain comparison. Write the order they end in.

Show the answer

The order is Apple, Zoo, apple. The capital letters A (65) and Z (90) come before the lowercase a (97). Among the capitals, A comes before Z.

Exercise 2. What does std::string("10") < std::string("9") return, and why?

Show the answer

It returns true. The first characters are '1' and '9'. The character '1' has the number 49 and '9' has the number 57, so "10" comes first. The comparison does not look at the values 10 and 9.

Exercise 3. The code below should print found when word is stop, but it prints found for every other word. Fix it.

#include <cstring>
#include <iostream>
 
int main() {
    const char* word = "go";
    if (std::strcmp(word, "stop")) {
        std::cout << "found\n";
    }
}

Show the answer

strcmp returns zero when the strings are equal, so the test needs == 0:

#include <cstring>
#include <iostream>
 
int main() {
    const char* word = "go";
    if (std::strcmp(word, "stop") == 0) {
        std::cout << "found\n";
    }
}

With word set to "go", this prints nothing.

Exercise 4. Write a function bool same_ignoring_case(const std::string& a, const std::string& b) that returns true when the two strings are the same, ignoring case. Use the ci_less predicate from Example 3. Test it with "Hello" and "hELLO".

Show the answer

The function is the one from the section on equality, with ci_less defined above it. Two strings are equal when neither comes before the other. The test prints true for "Hello" and "hELLO".

Exercise 5. Sort {"bob", "Alice", "alice", "Bob"} case-insensitively with std::ranges::stable_sort. Predict the order before you run the code. Then check your prediction.

Show the answer

The stable order is Alice, alice, bob, Bob. The two alice spellings keep their input order, with Alice first because it came first in the input. The two bob spellings also keep their input order, with bob first. The groups are in the order alice and then bob, because a comes before b.

Summary

• Lexicographic order compares strings one character at a time, like a dictionary. The first position where the characters differ decides the order.
• Characters compare by their numeric codes, so B (66) comes before a (97), and "10" comes before "9".
• compare on std::string and std::strcmp return a negative number, zero or a positive number. Test the sign, and use == 0 to check for equality.
• A case-insensitive predicate lowercases each character before comparing. Pass it to std::ranges::sort or std::ranges::stable_sort.
• Use stable_sort when equal items must keep their original order.
• For C strings, == compares addresses, not text. Use std::strcmp or std::string.