# Räkna ord med ranges och views 2 december 2025 | https://www.ribomation.se/blog/2025/rakna-ord-med-ranges-och-views/ Har du också undrat över hur många gånger orden _Caesar_, _Cleopatra_ och _Hamlet_ förekommer i William Shakespeares samlade verk. Tja, kanske inte... 😏 Men att räkna ordförekomster och presentera resultat på ett trevligt sätt är en ganska bra programmeringsövning. Jag avser här att använda Shakespeares samlade verk som indata. Häng med på en underhållande artikel om modern C++ med ranges och views. Denna artikel tar vid där min förra artikel slutade och fortsätter med C++20/23 ranges och views, genom att stegvis skriva ett litet program som behandlar en textfil, läser in alla ord och håller reda på hur många gånger respektive ord förekommer och skriver ut en HTML-fil med de 100 mest förekommande orden, där ordstorleken är proportionell mot dess frekvens och där varje ord har en slumpmässigt vald färg. Jag kommer att visa programkoden i delar, men den kompletta källkoden finns i en GitHub repo, du finner i länksamlingen i slutet på artikeln. I grova drag är programmet strukturerat på följande vis: 1. Öppna infilen och koppla till ett par av WordIterator-objekt. Jag visar koden för WordIterator senare i artikeln. 2. Bygg en första range-pipeline där orden läses, filtreras och normaliseras till gemener, samt ackumuleras i en hash-map. 3. Kopiera över alla _{word, count}_ par till en vector för att sortera dem i fallande frekvensordning. 4. Bygg en andra range-pipeline där ord-frekvens paren görs till HTML `span` taggar, där ordstorlek sätts proportionellt mot frekvens. 5. Blanda taggarna i slumpmässig ordning, så att slutresultatet ser litet intressantare ut, än stort till smått. 6. Skriv ut resultatet på en HTML-fil Parametrar ---------- Följande in-parametrar styr programmet ```cpp auto filename = fs::path{"../data/shakespeare.txt"}; auto min_length = 6U; auto max_words = 100U; auto max_font = 200U; auto min_font = 40U; for (auto k = 1; k < argc; ++k) { auto arg = string{argv[k]}; if (arg == "--file"s) { filename = fs::path{argv[++k]}; } else if (arg == "--min"s) { min_length = std::stoul(argv[++k]); } else if (arg == "--max"s) { max_words = std::stoul(argv[++k]); } } ``` Valideringen av indata kunde vara bättre, men duger för ett enkelt demo-program som detta. Typdefinitioner --------------- Följande typ- och import-definitioner används i programmet ```cpp namespace r = std::ranges; namespace v = std::ranges::views; namespace c = std::chrono; namespace fs = std::filesystem; using WordCount = std::pair; using namespace std::string_literals; using std::string; ``` Containrar ---------- I programmet används följande containrar. Först en hash-map (`std::unordered_map`), som populeras från inlästa ord. Sedan en `std::vector` för sortering varpå de N mest frekventa orden sparas i en annan vector. Denna blir start på en pipeline, som omvandlar varje par till en text-sträng i form av en HTML span-tag. Inläsning --------- ```cpp auto freqs = std::unordered_map{}; freqs.reserve(10'000); auto in = std::ifstream{filename}; if (not in) {...} r::for_each(r::subrange{WordIterator{in}, WordIterator{}} | v::filter(drop_small_words) | v::transform(to_lower_case) | v::filter(drop_modern_words) , count_words ); ``` Vi börjar med att deklarera en hash-map för ord-frekvenser och blåsa upp den lite på måfå för att minska ned antalet interna minnesallokeringar. Infilen öppnas och ett par av WordIterator objekt i en subrange bildar starten på en pipeline. Jag återkommer till min egen-definierade iterator-klass senare. Just nu räcker det med att veta den läser ett ord i taget (_sekvens av bokstäver_). En (range-) pipeline inleds vanligtvis med en STL container. Om man inte har detta, men däremot ett par av iteratorer, så kan man skapa ett range-objekt med att instansiera `std::ranges::subrange`, vilket vi gör här ovan. Det finns tre steg i denna pipeline, som sedan fungerar som indata för `for-each` funktionen, där inlästa ord ackumuleras i hash-map:en. Det första steget filtrerar bort korta ord, via följande lambda. ```cpp auto drop_small_words = [min_length](string const& word) -> bool { return word.size() >= min_length; }; ``` Det andra steget normaliserar orden till bara gemener (_små bokstäver_), via följande lambda. ```cpp auto to_lower_case = [](string word) -> string { for (char& c: word) { auto ch = static_cast(c); c = static_cast(std::tolower(ch)); } return word; }; ``` Här skickar vi string-objektet _by-value_, dvs en kopia, vilket tillåter oss att ändra varje bokstav med `std::tolower()` och returnera det modifierade ordet. Alternativet hade varit att skicka in ordet som en konstant referens och populera ett lokalt string objekt. Typomvandlingen mellan signed och unsigned char motiveras med följande kommentar på cppreference.com > Like all other functions from ``, the behavior of `std::tolower` is undefined if the argument's value is neither representable as `unsigned char` nor equal to _EOF_. To use these functions safely with plain chars (or signed chars), the argument should first be converted to `unsigned char`: > `char my_tolower(char ch) {` >    `return static_cast(std::tolower(static_cast(ch)));` > `}` Det tredje steget filtrerar bort några ord som finns i indata-filen och upplyser om att texten finns på `gutenberg.org`. Vi kan ju vara ganska säkra på att William inte använde ord som "_electronic_" i hans skådespels-manus. 😏 ```cpp auto drop_modern_words = [](string const& word) -> bool { static auto const modern_words = std::unordered_set{ "electronic"s, "distributed"s, "copies"s, "copyright"s, "gutenberg"s }; return not modern_words.contains(word); }; ``` Till slut, sker ackumuleringen i en lambda som utgör `for_each` funktionens applikations-logik. ```cpp auto count_words = [&freqs](string const& word) { ++freqs[word]; }; ``` Uttrycket `freqs[word]` hittar det `std::pair` objekt som har word som nyckel (`.first`) och returnerar referensen till dess värde (`.second`), vilken då inkrementeras. Finns inte pair-objekt, så skapas det ett nytt, med ordet som nyckel och där värdet initieras med default-konstruktorn (för ett numeriskt värde blir det 0). Sortering --------- Vi använder en hash-map för ackumuleringen eftersom den är den snabbaste containern för återkommande uppslag och insättning. Men det går inte att sortera en dylik, så därför behöver vi hälla över alla ord-frekvens par till en container som går att sortera, vilket i vårt fall är en std::vector. Vi "behöver inte" sortera samtliga par, det räcker med de par vi är intresserade av, vilket är de N mest frekventa orden. Funktionen `partial_sort` i standard-biblioteket löser detta på ett elegant sätt, genom att peka ut hur många element man vill ha sorterade. Denna funktion har funnits med länge, men här använder jag dess moderna version, som tar en range som input, en iterator som pekar på antalet element, samt en komparator som styr hur elementen ska sorteras. ```cpp auto sortable = std::vector(freqs.begin(), freqs.end()); auto by_count_desc = [](auto const& a, auto const& b) { return a.second > b.second; }; r::partial_sort(sortable, sortable.begin() + max_words, by_count_desc); ``` Ska man vara petig med robust kod, så borde man validera `max_words` och säkerställa att uttrycket `sortable.begin() + max_words` inte pekar utanför vektorn. Detta kan man ordna genom att sätta brytpunkten till den minsta av `max_words` och vektorlängden. Här nedan visar jag uppdaterade kodrader avseende kodfragmentet ovan. ```cpp //... auto N = std::min(max_words, sortable.size()); //... r::partial_sort(sortable, sortable.begin() + N, by_count_desc); ``` HTML-taggar ----------- I programmets sista fas, ska vi omvandla ord-frekvens par till text-strängar med HTML span taggar. Det första vi behöver göra är att spara de par vi är intresserade av, vilket jag gör med en liten pipeline. ```cpp auto items = sortable | v::take(max_words) | r::to>(); ``` Här bör kanske invändas att man skulle kunna kapa ned sortable med anropet `sortable.resize(max_words)`. Men då missar vi den eleganta pipeline:n ovan. 😎 Själva transformeringen från par till text gör med ytterligare en liknande pipeline. ```cpp auto tags = items | v::transform(to_span_tag) | r::to>(); ``` Transformations-lambdan ser ut så här. ```cpp auto to_span_tag = [scale, min_cnt, min_font, &rnd_color](WordCount const& wc) { auto const& word = wc.first; auto freq = wc.second; auto size = static_cast(scale * (freq - min_cnt)) + min_font; auto colr = rnd_color(); return std::format( R"({})", size, colr, word, freq, word); }; ``` Jag använder mig av `std::format` för att returnera en span-tag, eftersom den funktionen gör det enkelt att patcha in text-fragment på olika ställen i en text-mall. Första argumentet är en text-mall i form av en så kallad _raw-string_ (`R"(...text goes here...)"`), så man slipper skriva back-slash före varje citationstecken, vilka det finns flera av i en typisk HTML tagg. Ordstorleken (_font-size_) beräknas genom att frekvensen multipliceras med en skalfaktor, vilken definieras på följande vis. ```cpp auto max_cnt = items.front().second; auto min_cnt = items.back().second; auto scale = static_cast(max_font - min_font) / (max_cnt - min_cnt); ``` Här utgår vi från att indata-filen innehåller flera olika ord, vilket gör att vi hoppar över att kontrollera för eventuell division med noll. Det vill säga de två cnt variablerna har samma värde. Varje ord färgläggs med en slumpmässigt genererad HTML-color, med hjälp av följande lambda. ```cpp auto R = std::default_random_engine{std::random_device{}()}; auto rnd_color = [&R]() { auto B = std::uniform_int_distribution{0, 255}; return std::format("#{:02X}{:02X}{:02X}", B(R), B(R), B(R)); }; ``` Lambdan genererar tre slumpmässiga byte-värden i intervallet _{0,255}_ och formaterar dessa i hex-format, samt returnerar dem i HTML RGB-color format, som t.ex. `#BA3A0A`. _Summa summarum_; ett indata par som `std::pair<"othello", 325>` omvandlas till text-strängen ```cpp othello ``` Generering av HTML-fil ---------------------- Innan vi skriver ut alla HTML taggar, blandar vi om dessa i slumpmässig ordning, så att resultatet ser intressantare ut än att alla ord radas upp från det största till det minsta. ```cpp r::shuffle(tags, R); ``` Först skapar vi filnamnet genom att ta indata-filens namn och byta ut filändelsen mot `.html` och sen öppnar vi utfilen. ```cpp auto outfile = fs::path{filename.stem().string() + ".html"s}; auto out = std::ofstream{outfile}; if (not out) {...} ``` Sen skriver vi ut början på en HTML-fil. ```cpp out << R"( Word Frequencies )" << std::format("

The {} most frequent words of {}

", max_words, filename.string()); ``` Span-taggarna är ju redan klara, så det är enkelt att bara dumpa ut dem härnäst, samt skriva ut HTML avslutningen. ```cpp for (auto&& tag: tags) out << tag << "\n"; out << "\n"; std::println("written result to '{}'", outfile.string()); ``` Tidsmätning ----------- I början av koden läste jag av klockan och likaså i slutet, för att beräkna förfluten tid. ```cpp auto start_time = c::high_resolution_clock::now(); //...program goes here... auto end_time = c::high_resolution_clock::now(); auto elapsed_time = c::duration_cast(end_time - start_time); std::println("Elapsed time was {} ms", elapsed_time.count()); ``` Programutskrift --------------- Kompilerar man och kör programmet kan det se ut så här. ```shell $ g++ -std=c++23 -Wall word-count.cxx -o word-count $ ./word-count --file data/shakespeare.txt Loading 5.33 MB from 'data/shakespeare.txt' written result to 'shakespeare.html' Elapsed time was 969 ms ``` HTML-resultatet --------------- Öppnar vi den skapade HTML-filen i en webbläsare kan det se ut så här. Jag har markerat orden _caesar_ (525 förekomster) och _cleopatra_ (263 förekomster). Emellertid, förekommer ordet _hamlet_ inte bland de 100 mest förekommande utan är på en blygsam plats med 117 förekomster (vilket man kan se genom att öka på `max_words`). ![De 100 mest förekommande orden i Shakespeares samlade verk](/blog/2025/rakna-ord-med-ranges-och-views/word-freqs-1315w.jpeg "De 100 mest förekommande orden i Shakespeares samlade verk") Klassen WordIterator -------------------- För att läsa in orden från infilen har jag använt en egen-utvecklad iterator-klass, som returnerar ett ord (_sekvens av bokstäver_) i taget. Den finns i en separat header-fil för att enkelt kunna återanvändas i något annat projekt. ```cpp class WordIterator { public: using iterator_category = std::input_iterator_tag; //... explicit WordIterator(std::istream& is); WordIterator() = default; reference operator*() const; pointer operator->() const; WordIterator& operator++(); WordIterator operator++(int); friend bool operator==(WordIterator const& a, WordIterator const& b); friend bool operator!=(WordIterator const& a, WordIterator const& b); private: // ... static bool is_letter(char c); void read_next(); }; ``` Den börjar med ett antal standardiserade publika typ-alias, vilka behövs för att andra funktioner ska kunna välja lämplig realisering i compile-time. ```cpp using iterator_category = std::input_iterator_tag; using value_type = std::string; using reference = const std::string&; using pointer = const std::string*; using difference_type = std::ptrdiff_t; ``` Den har två konstruktorer, där den första knyter till början av en öppen data-ström och den andra representerar filslut (_eof_). ```cpp explicit WordIterator(std::istream& is) : input{&is} { read_next(); } WordIterator() = default; ``` Detta leder oss till det privata innehållet i ett iterator-objekt. ```cpp std::istream* input{nullptr}; std::string current_word{}; bool at_eof{true}; ``` Indata-strömmen utgörs av en pekare (och inte referens), eftersom pekaren behöver vara null-ställd för eof-iteratorn, vilket inte skulle kompilera om vi hade haft en referens. Sedan har vi en ackumulator-sträng för aktuellt ord, samt en boolsk flagga för att signallera filslut. Vidare, så har den en föreskriven uppsättning av operatorer för att kunna iterera över den datamängd den är skapad för. ```cpp // element access reference operator*() const { return current_word; } pointer operator->() const { return ¤t_word; } // increment WordIterator& operator++() { read_next(); return *this; } WordIterator operator++(int) { auto tmp = *this; ++(*this); return tmp; } // comparison friend bool operator==(WordIterator const& a, WordIterator const& b) { return a.input == b.input && a.at_eof == b.at_eof; } friend bool operator!=(WordIterator const& a, WordIterator const& b) { return !(a == b); } ``` Själva inläsningen görs av funktionen `read_next`. ```cpp void read_next() { if (input == nullptr) { at_eof = true; return; } current_word.clear(); for (char ch; input->get(ch) && not is_letter(ch);) {} if (input->gcount()) input->unget(); if (current_word.empty() && input->eof()) { at_eof = true; input = nullptr; return; } for (char ch; input->get(ch) && is_letter(ch);) { current_word.push_back(ch); } at_eof = false; } static bool is_letter(char c) { auto ch = static_cast(c); return std::isalpha(ch) || ch == '\''; } ``` Givet att vi har en inström, så nollställer vi aktuellt ord och skannar förbi alla icke-bokstäver, tills första bokstaven i ett ord. Eftersom vi i det läget har läst en bokstav _för mycket_, så puttar vi tillbaka denna i strömmen. Om vi inte har nått slutet, så börjar vi samla på oss bokstäver tills vi har läst en icke-bokstav. Eftersom, vi vet efter detta att det finns minst ett ord kvar så sätter vi filsluts-flaggan till false. Konverteringen i funktionen `is_letter` till `unsigned char`, tarvar en liten utläggning. Så här står det på `cppreference.com` > Like all other functions from ``, the behavior of `std::isalpha` is undefined if the argument's value is neither representable as `unsigned char` nor equal to `EOF`. To use these functions safely with plain chars (or signed chars), the argument should first be converted to `unsigned char`. Alternativ inläsning -------------------- Måste man verkligen skriva en egen iterator-klass. Självklart inte. Alternativet här är att förlita sig på ett par av `std::istream_iterator` objekt, samt strippa bort icke-bokstäver, som första steg i vår inläsnings-pipeline. Så här skulle det kunna se ut. ```cpp auto strip_non_letters = [](string const& word) { auto result = string{}; result.reserve(word.size()); auto is_letter = [](char c) -> bool { auto ch = static_cast(c); return std::isalpha(ch) || ch == '\''; }; for (char c: word) if (is_letter(c)) result += c; return result; }; auto in_iter = std::istream_iterator{in}; auto eof_iter = std::istream_iterator{}; auto read_words_pipeline = r::subrange{in_iter, eof_iter} | v::transform(strip_non_letters) | v::filter(drop_small_words) | v::transform(to_lower_case) | v::filter(drop_modern_words); r::for_each(read_words_pipeline, count_words); ``` Kör vi programmet med denna alternativa inläsning, ser det ut så här ```shell Loading 5.33 MB from '../data/shakespeare.txt' written result to 'shakespeare.html' Elapsed time was 3794 ms ``` Som jämförelse, visar jag hur det såg ut med min word-iterator. ```shell Loading 5.33 MB from 'data/shakespeare.txt' written result to 'shakespeare.html' Elapsed time was 969 ms ``` Oj oj oj, nästan fyra gånger så lång exekveringstid. 😮 Här har vi extra string allokeringar i `strip_non_letters`, samt att `std::istream_iterator` har en högre intern overhead, jämfört med min egen iterator. Det lönar sig att tänka på underliggande implementation. Alternativ 2 finns med som kommenterad kod i programkoden på GitHub, så att du kan experimentera själv med koden och prova dig fram.