string কখন ব্যবহার করবে, আর কখন না

Kenji একটা helper লিখেছিল, যেটা বের করে একটা শব্দ কোথায় শেষ হয়, আর 60,000 character-এর একটা text-এর প্রতিটা শব্দের জন্য ওটা একবার করে call করেছিল। উত্তর ঠিকই আসছিল, কিন্তু program চলছিল হামাগুড়ি দিয়ে। ওর অভ্যাসমতো ও loop-টা নতুন করে লিখতে বসল। Amara helper-এর প্রথম লাইনটা পড়ল, size_t word_end(const string text, size_t start), আর একটা character যোগ করল: &। Program একশো গুণেরও বেশি দ্রুত হয়ে গেল। এই lesson ওই একটা character নিয়ে, আর সেই সব সময় নিয়ে, যখন string ঠিক জিনিস না।

তোমার text নিয়ে চারটা প্রশ্ন

Text-এর জন্য string হলো ঠিক default, কিন্তু সব কাজের জন্য না। প্রায় সব ক্ষেত্রে চারটা প্রশ্নই সিদ্ধান্ত দিয়ে দেয়।

Character-এর মালিক হওয়া মানে ওগুলো এমন memory-তে রাখা, যার দায় তোমার, আর কাজ শেষে সেই memory ছেড়ে দেওয়া। একটা string নিজের character-এর মালিক। একটা view, যার সাথে নিচে দেখা হবে, শুধু অন্যের মালিকানার character-এর দিকে তাকায়। Kenji-র উত্তর: অনেক character, text, আর মালিক caller, কারণ ওর helper শুধু পড়ে। প্রশ্ন 3 ওকে value হিসেবে নেওয়া string parameter থেকে সরিয়ে দেয়। তাই লাইনটা লেখার আগেই প্রশ্নগুলো type-টার নাম বলে দেয়।

তুলনার chart

পাঁচটা type পাশাপাশি দেখো। Char array হলো C-এর char name[20]; একটা const char* হলো এমন text-এর প্রথম character-এর pointer, যেটা শেষ হয় '\0' দিয়ে, যেমন একটা string literal। ঘরগুলো মেলানো হয়েছে cppreference-এ প্রতিটা type-এর page ধরে। n মানে character-এর সংখ্যা।

string-এর কলামটা উপর থেকে নিচে পড়ো: মালিক, দৈর্ঘ্য জানে, বড় হয়, আবার c_str() দিয়ে C-কে '\0'-এ শেষ হওয়া text-ও দিতে পারে। ওর একটাই দাম, copy, O(n)। যে দুইটা কলাম O(1)-এ copy হয়, const char* আর string_view, ওরা দাম দেয় শেষ সারিতে। ওদের নিজের কোনো character নেই, তাই মালিক চলে গেলে ওরা কিছুই-না-এর দিকে তাকিয়ে থাকে। একটা vector<char> string-এর মতোই মালিক আর বড় হয়, কিন্তু কোনো '\0'-এর কথা দেয় না, আর find-এর মতো text-এর function-ও ওর নেই। মানে সস্তা copy-গুলোই বিপজ্জনক, আর নিরাপদগুলো copy করে।

সিদ্ধান্তের flowchart

একই প্রশ্নগুলো, এবার flowchart হিসেবে, যে ক্রমে জিজ্ঞেস করবে। উপর থেকে শুরু করো, আর নিজের উত্তর ধরে এগোও।

Kenji-র পথ: অনেক character, text, আর মালিক caller, তাই তৃতীয় ঘর ওকে ডান দিকে পাঠায়, const string& বা string_view-এ। শেষ লাইনটা অক্ষর নিয়ে সৎ কথাটা বলে। Lesson 01 দেখিয়েছিল, বাংলায় Maria-র নামের size 21, অথচ code point মাত্র 7টা, আর পর্দার একটা অক্ষর একাধিক code point দিয়েও হতে পারে। পাঠক যেটাকে অক্ষর হিসেবে দেখে, সেটা গুনতে লাগে Unicode-এর নিয়ম। সেই নিয়মগুলো যে library-তে থাকে, তার নাম ICU (International Components for Unicode); Chromium আর Android দুটোই এটা সাথে নিয়ে আসে। এই track এটা শেখায় না; দরকার পড়লে এই নামটা দিয়েই খুঁজবে।

Function-এ text পাঠানো: value হিসেবে, const& দিয়ে, বা string_view দিয়ে

একটা function কীভাবে text নেয়, সেটাই বলে দেয় ও ওটা দিয়ে কী করতে পারবে, আর প্রতিটা call-এ কত খরচ।

এই হলো Kenji-র helper তিনভাবে লেখা, প্রতিটা একই text-এর প্রতিটা শব্দের জন্য একবার করে call হয়। word_end return করে start-এর পরের space-এর জায়গা, আর space না থাকলে text-এর size। Program প্রতিটা loop-এর সময় মাপে chrono::steady_clock দিয়ে, এমন একটা ঘড়ি, যেটা শুধু সামনেই চলে।

#include <chrono>
#include <iostream>
#include <string>
#include <string_view>
using namespace std;

size_t word_end_by_value(const string text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string::npos ? text.size() : space;
}

size_t word_end_by_ref(const string& text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string::npos ? text.size() : space;
}

size_t word_end_by_view(string_view text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string_view::npos ? text.size() : space;
}

int main() {
    string text;
    for (int k = 0; k < 3000; k++) {
        text += "Bob fixes bugs fast ";
    }

    auto t0 = chrono::steady_clock::now();
    size_t a = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_value(text, i);
        a += end - i;
        i = end + 1;
    }
    auto t1 = chrono::steady_clock::now();
    size_t b = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_ref(text, i);
        b += end - i;
        i = end + 1;
    }
    auto t2 = chrono::steady_clock::now();
    size_t c = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_view(text, i);
        c += end - i;
        i = end + 1;
    }
    auto t3 = chrono::steady_clock::now();

    chrono::duration<double, milli> va = t1 - t0, vb = t2 - t1, vc = t3 - t2;
    cout << text.size() << " characters, 12000 calls each\n";
    cout << "by value:       " << a << " letters, " << va.count() << " ms\n";
    cout << "by const&:      " << b << " letters, " << vb.count() << " ms\n";
    cout << "by string_view: " << c << " letters, " << vc.count() << " ms\n";
    return 0;
}

60000 characters, 12000 calls each
by value:       48000 letters, 16.6773 ms
by const&:      48000 letters, 0.087271 ms
by string_view: 48000 letters, 0.09158 ms

Compiler Explorer-এ একবার চালানো, GCC 12, -O2 -std=c++17, মানে Playground-এর flag। একই program এগারোবার চালালে value হিসেবে লেগেছে 15.8 থেকে 32.6 ms, আর const&-এ 0.07 থেকে 0.11 ms, মানে প্রতিটা run-এ value হিসেবে নেওয়াটা 152 থেকে 405 গুণ ধীর। string_view দশটা run-এ const&-এর সমান ছিল, আর একটায় নিয়েছে 0.94 ms। Value হিসেবে প্রতিটা call পুরো 60,000 character একটা নতুন buffer-এ copy করেছে, তারপর আবার ছেড়ে দিয়েছে: 12,000টা call, প্রায় 72 কোটি byte। Allocation গুনে দেখা একটা run 12,000টা call-এ 12,000টা allocation পেয়েছে, মানে compiler একটা copy-ও বাদ দেয়নি।

const string text-এর const কোনো কাজে আসেনি, কারণ ওটা শুধু function-কে নিজের copy বদলাতে দেয় না। Copy তো হচ্ছেই। তাই শুধু পড়ার parameter হলো const string& বা string_view, আর এখানে দুটোর খরচ একই।

string_view: একটা pointer আর একটা দৈর্ঘ্য

C++17-এর <string_view>-এর string_view হলো একটা view: ও রাখে অন্য কারও character-এর একটা pointer, আর কয়টা character দেখবে সেই সংখ্যা। একটা বানাতে খরচ O(1), copy করতেও O(1), আর ওর substr-ও তাই, কারণ ওটা শুধু pointer সরায় আর দৈর্ঘ্য বদলায়। String-এর পড়ার বেশিরভাগ function ওর আছে, size, [], find আর substr তার মধ্যে, কিন্তু character বদলায় এমন কিছুই নেই।

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int main() {
    string text = "Maria asks why, every time";
    string_view all = text;
    string_view who = all.substr(0, 5);
    string_view what = all.substr(6, 8);

    cout << "sizeof(string_view): " << sizeof(string_view) << " bytes\n";
    cout << "who:  [" << who << "] starts " << who.data() - text.data() << " bytes into text\n";
    cout << "what: [" << what << "] starts " << what.data() - text.data() << " bytes into text\n";

    text[0] = 'm';
    cout << "after text[0] = 'm', who is [" << who << "]\n";
    return 0;
}

sizeof(string_view): 16 bytes
who:  [Maria] starts 0 bytes into text
what: [asks why] starts 6 bytes into text
after text[0] = 'm', who is [maria]

64-bit machine-এর GCC 12-এ একটা view 16 byte, 8 byte-এর একটা pointer আর 8 byte-এর একটা দৈর্ঘ্য, text যত লম্বাই হোক। data() দেয় view-এর pointer-টা, আর দুইটা view-ই দেখায় text-এর ভিতরে, 0-তে আর 6-এ। text বদলাতেই who-তেও সেই বদল দেখা গেল, কারণ ওর নিজের কোনো character কখনো ছিলই না। তাই view হলো text-এর দিকে খোলা একটা জানালা, text-এর copy না।

ফাঁদ: যে view নিজের text-এর চেয়ে বেশি দিন বাঁচে

জানালার দাম ততক্ষণই, যতক্ষণ বাড়িটা দাঁড়িয়ে আছে। একটা view যে character-গুলোর দিকে তাকায়, সেগুলো ধ্বংস হয়ে গেলেও view-এর হাতে থাকে ওর pointer আর দৈর্ঘ্য, আর কেউ ওকে কিছু জানায় না। তখন ওটা ব্যবহার করা undefined behaviour। এখানে পৌঁছানোর সবচেয়ে সহজ রাস্তা একটা temporary: নাম ছাড়া একটা মান, যেটা যে statement ওকে বানিয়েছে তার শেষেই ধ্বংস হয়। string::substr একটা নতুন string return করে, তাই ও ঠিক এমন একটা বানায়।

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int main() {
    string record = "Amara Okafor, room 12, the north building";
    string_view place = record.substr(14, 27);
    cout << "place: [" << place << "]\n";
    return 0;
}

GCC 12 কোনো বার্তা ছাড়াই এটা compile করেছে, Playground-এর flag-এও, -Wall -Wextra দিয়েও। Compiler Explorer-এ একবার চালাতে print হয়েছে place: [, তারপর 16 byte-এর পড়া যায় না এমন আবর্জনা, তারপর th building]। 27 character-এর temporary-টা semicolon-এই free হয়ে গিয়েছিল, আর memory allocator ততক্ষণে ওর প্রথম 16 byte-এর উপর লিখে ফেলেছিল। আরেকবার চালাতে এসেছে অন্য আবর্জনা। সমাধান হলো character-গুলো রেখে দেওয়া: string place = record.substr(14, 27);, অথবা আসলটার দিকেই view নেওয়া, string_view(record).substr(14, 27) দিয়ে। তাই একটা view ঠিক ততক্ষণ নিরাপদ, যতক্ষণ ওর মালিক বেঁচে আছে, আর compiler তোমার হয়ে এটা check করবে না।

#include <iostream>
#include <string_view>
using namespace std;

int main() {
    string_view files[] = {"test_parser.cpp", "main.cpp", "test_report.cpp", "notes.txt"};
    for (string_view name : files) {
        if (name.starts_with("test_") && name.ends_with(".cpp")) {
            name.remove_prefix(5);
            name.remove_suffix(4);
            cout << "test: " << name << '\n';
        } else {
            cout << "skip: " << name << '\n';
        }
    }
    return 0;
}

test: parser
skip: main.cpp
test: report
skip: notes.txt

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int count_words(string_view text) {
    int words = 0;
    bool in_word = false;
    for (char c : text) {
        if (c == ' ') {
            in_word = false;
        } else if (!in_word) {
            in_word = true;
            words++;
        }
    }
    return words;
}

int main() {
    string line = "Amara writes the cleanest code";
    char old_style[] = "Bob rushes";

    cout << count_words("a literal works too") << '\n';
    cout << count_words(line) << '\n';
    cout << count_words(old_style) << '\n';
    cout << count_words(string_view(line).substr(6, 10)) << '\n';
    return 0;
}

4
5
2
2

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // The first eight bytes of every PNG image file.
    vector<unsigned char> header{0x89, 'P', 'N', 'G', 0x0D, 0x0A, 0x1A, 0x0A};
    cout << "bytes:";
    for (unsigned char b : header) {
        cout << ' ' << (int)b;
    }
    cout << "\nsize(): " << header.size() << '\n';

    char packet[] = {'H', 'I', 0, 'Z', 0};
    cout << "a packet of " << sizeof(packet) << " bytes, strlen says " << strlen(packet) << '\n';
    return 0;
}

bytes: 137 80 78 71 13 10 26 10
size(): 8
a packet of 5 bytes, strlen says 2

#include <iostream>
#include <string>
using namespace std;

char grade(int mark) {
    if (mark >= 80) {
        return 'A';
    }
    if (mark >= 65) {
        return 'B';
    }
    if (mark >= 50) {
        return 'C';
    }
    return 'F';
}

int main() {
    int marks[] = {84, 55, 91, 47, 70};
    string grades;
    for (int m : marks) {
        grades += grade(m);
    }
    cout << "grades: " << grades << " (" << grades.size() << " papers)\n";
    return 0;
}

grades: ACAFB (5 papers)

string line = "Maria asks why, every time";
string_view who = string_view(line).substr(0, 5);
cout << who << '\n';
cout << who.data() << '\n';

char answer[] = "yes";
if (answer == "yes") {
    cout << "same\n";
} else {
    cout << "different\n";
}

string_view room_label(int n) {
    string label = "room number " + to_string(n) + ", north building";
    return label;
}

string_view a = "abc";
string_view b = string("abc");

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

// Return a view of the first word of line: the characters before the
// first space, or the whole line if it has no space. Make no copy.
string_view first_word(string_view line) {
    return line;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    while (getline(cin, line)) {
        cout << first_word(line) << '\n';
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string count, kind, owner;
        cin >> count >> kind >> owner;
        // Ask the flowchart's questions in its order, and print one type.
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

// Kenji's helper: does pattern appear in text, starting at index i?
// It gives the right answer, and it is far too slow on a long text.
// Change only this function, never main.
bool starts_at(string text, string pattern, size_t i) {
    return text.substr(i, pattern.size()) == pattern;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);

    long long count = 0;
    for (size_t i = 0; i + pattern.size() <= text.size(); i++) {
        if (starts_at(text, pattern, i)) {
            count++;
        }
    }
    cout << count << '\n';
    return 0;
}

এখানেই এই module-এর free lesson-গুলো শেষ। এরপর আছে problems page আর module test। Pro পাঠকদের জন্য lesson 05 হলো "ভেতরের কথা: ছোট string-এর buffer, বাড়া আর + এর খরচ" (Pro)। আর lesson 06 হলো "CP আর interview pack: string-এর pattern, প্রশ্ন আর bug gallery" (Pro)।