set: সাজানো, কোনো repeat নেই, আর কয়েক ধাপেই খুঁজে পাওয়া

Amara coding club-এর sign-up খাতাটা সামলায়, আর নামগুলো আসে যেকোনো ক্রমে, কেউ কেউ দুইবারও লেখে। ওর লাগবে আলাদা আলাদা নামগুলো, বর্ণমালার ক্রমে, আর ওদিকে Kenji বারবার জিজ্ঞেস করছে, ওর নাম তালিকায় উঠেছে কি না। Vector হলে প্রতিটা sign-up-এর পরে sort করে repeat-গুলো বাদ দিতে হতো, নয়তো প্রতিটা প্রশ্নে পুরো তালিকা ঘেঁটে দেখতে হতো। সাজানো C array-ও কাজে আসে না: প্রতিটা নতুন নামের জন্য পরের সব নাম এক ঘর করে সরাতে হয়। এই lesson Amara-কে এমন একটা container দেবে, যেটা নাম আসতে আসতেই দুটো কাজই সেরে ফেলে।

দুইটা প্রতিশ্রুতি: সাজানো, আর কোনো repeat নেই

Set হলো এমন একটা container, যেটা প্রতিটা মান বড়জোর একবার রাখে, আর মানগুলো সাজিয়ে রাখে। তুমি মান insert করো যেকোনো ক্রমে। Set-টার শুরু থেকে হাঁটলে মানগুলো বেরোয় সবচেয়ে ছোট থেকে সবচেয়ে বড় পর্যন্ত। ছোট মানে সংখ্যার বেলায় তোমার চেনা সেই <, আর string-এর বেলায় Module 3-এর byte-এর ক্রম।

Set-এ আগে থেকেই আছে, এমন একটা মান insert করলে কিছুই বদলায় না। Module 0-এ একটা set-কে দেওয়া হয়েছিল 30, 10, 20 আর 10, আর সেটা print করেছিল 10 20 30। এবার একই কথা, Amara-র নামগুলো দিয়ে।

তাই set Amara-কে একসাথে দুইটা জিনিস দেয়: নামগুলো বেরোয় সাজানো অবস্থায়, আর প্রতিটা নাম বেরোয় একবারই।

ভেতরে: একটা tree, যেটা খাটো থাকে

প্রতিটা নাম না দেখেই set কীভাবে একটা নাম খুঁজে পায়? ও মানগুলো রাখে একটা binary search tree-তে। প্রতিটা মান থাকে একটা node-এ, memory-র একটা ছোট্ট বাক্সে। কোনো node-এর চেয়ে ছোট সব মান থাকে ওর বাঁ দিকে কোথাও, আর বড় সব মান ওর ডান দিকে। খোঁজা শুরু হয় একদম উপরের node থেকে, যার নাম root; প্রতিটা node-এ একবার তুলনা করে বাঁয়ে বা ডানে যায়, আর একটা গোটা দিক পেছনে পড়ে থাকে।

ছবিতে সাতটা মানের মধ্যে 50 খোঁজা হচ্ছে। সাজানো array একটা একটা করে দেখে 10, 20, 30, 40, তারপর 50: পাঁচ ধাপ। Tree-তে তুলনা হয় 40-এর সাথে, তারপর 60, তারপর 50-এর সাথে: তিন ধাপ। সাতটা মান 40, 20, 60, 10, 30, 50 আর 70 ক্রমে এলে GCC 12-এর library হুবহু এই tree-টাই বানায়। অন্য ক্রমে এলে আকারও হয় অন্যরকম, পরের অংশে সেটা দেখবে।

Tree-তে প্রতিটা নতুন level মানের জন্য জায়গা দ্বিগুণ করে দেয়, তাই 20টা level-এ দশ লাখের বেশি মান ধরে। দশ লাখ মানের সবচেয়ে খাটো tree-র level 20টা, আর ওতে একটা find-এ লাগে বড়জোর 20 ধাপ। Module 2-এর find একটা vector-এ খুঁজতে গিয়ে দশ লাখ ধাপও নিতে পারে।

যে tree-কে ওই সবচেয়ে খাটো আকারের কাছাকাছি রাখা হয়, তাকে বলে balanced। প্রতিটা insert আর erase-এর পরে library ওর tree আবার balance করে নেয়। আসল tree সবচেয়ে খাটোটার চেয়ে উঁচু হতে পারে, তবে বড়জোর দ্বিগুণ; lesson 05 সেটা মেপে দেখাবে। তাই একটা find-এ প্রতি level-এ একটা করে তুলনা লাগে, আর library level-এর সংখ্যা কম রাখে।

Tree-টাকে বাড়তে দেখো, একটা একটা insert করে

GCC-র standard library, যার নাম libstdc++, set রাখে একটা red-black tree-তে। প্রতিটা node সাথে একটা রংও রাখে, লাল বা কালো। প্রতিটা insert বা erase-এর পরে library কয়েকটা node-এর রং বদলায় আর কয়েকটাকে ঘুরিয়ে বসায়, যাতে রঙের নিয়মগুলো ঠিক থাকে। Widget-টা প্রতি ধাপের পরে আসল আকারটাই দেখায়, শুধু রংগুলো বাদ দিয়ে। C++ standard কোনো tree-র নামই বলে না: ও শুধু কথা দেয়, find, insert আর erase-এ O(log n) ধাপ লাগবে।

O(log n) মানে n দ্বিগুণ হলে মোটামুটি একটা ধাপ বাড়ে, Module 0 যেমন বলেছিল। এবার দেখো 10 থেকে 80 আসছে ছোট থেকে বড় ক্রমে; যে tree কখনো balance করে না, তার জন্য এটাই সবচেয়ে খারাপ ক্রম।

ছোট থেকে বড় ক্রমে আসা আটটা মান দিয়ে level হলো 4টা। যে সাধারণ tree কখনো balance করে না, সে প্রতিটা মান আগেরটার ডানে ঝোলাত: 8 level গভীর একটা chain। Root-টা খেয়াল করো: ও 10 থেকে সরে গেল 20-এ, তারপর 40-এ। দ্বিতীয়বারের insert(50) নিচে নেমে আগে থেকে থাকা 50 পর্যন্ত গেল, কিছুই বদলাল না। find(35) 30-এর নিচে গিয়ে tree থেকে পড়ে গেল, তাই 35 set-এ নেই।

তাই আকারটা library-র পছন্দ, আর মান যে ক্রমেই আসুক, tree থাকে মোটে কয়েক level গভীর।

প্রথম দিনেই যে syntax লাগবে

#include <set>

set<T> s;                  an empty set of T
set<T> s{a, b, c};         a set made from a list; repeats are dropped
s.insert(x);               add x; nothing happens if x is already there
s.erase(x);                remove x, if it is there
s.count(x)                 1 if x is there, 0 if not
s.find(x)                  an iterator to x, or s.end() if x is not there
s.size()    s.empty()      how many values, and whether there are none
*s.begin()  *s.rbegin()    the smallest and the largest value
for (T x : s)              every value, from the smallest to the largest

multiset<T> m;             the same calls, but repeats are kept

তাই রোজকার set-এর code মান ধরে কাজ করে, জায়গার নম্বর ধরে কখনো না।

insert, আর সাজানো ক্রমে হাঁটা

s.insert(x) x-কে ওর সাজানো জায়গায় বসায়। একটা range-for set-টার উপর দিয়ে হাঁটে, সবচেয়ে ছোট মান থেকে সবচেয়ে বড় পর্যন্ত। এই program প্রতিটা insert-এর পরে পুরো set print করে।

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

void show(const char* step, const set<int>& s) {
    cout << step << ':';
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
}

int main() {
    set<int> s;
    s.insert(30);
    show("insert(30)", s);
    s.insert(10);
    show("insert(10)", s);
    s.insert(20);
    show("insert(20)", s);
    s.insert(10);
    show("insert(10)", s);
    return 0;
}

insert(30): 30 (size 1)
insert(10): 10 30 (size 2)
insert(20): 10 20 30 (size 3)
insert(10): 10 20 30 (size 3)

মানগুলো এসেছিল 30, 10, 20 ক্রমে, তবু 10 বসল 30-এর আগে, আর 20 ওদের মাঝখানে। দ্বিতীয় insert(10) দেখল 10 আগে থেকেই আছে, তাই size রইল 3। তাই insert যে ক্রমেই হোক, হাঁটলে সবসময় সাজানোই পাওয়া যায়।

আছে তো? count আর find

s.count(x) বলে set-এ x-এর কয়টা copy আছে। Set-এ সেটা শুধু 1 বা 0 হয়, তাই এটাকে হ্যাঁ বা না হিসেবে পড়া যায়। s.find(x) ফেরত দেয় x-এর দিকে একটা iterator, আর x না থাকলে s.end()।

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

int main() {
    set<int> s{3, 9, 14, 27, 31};
    cout << s.count(14) << ' ' << s.count(5) << '\n';
    auto it = s.find(27);
    if (it != s.end()) {
        cout << "found " << *it << '\n';
    }
    if (s.find(5) == s.end()) {
        cout << "5 is not there\n";
    }
    return 0;
}

1 0
found 27
5 is not there

* দিয়ে পড়ার আগে find-এর উত্তর end()-এর সাথে মিলিয়ে নাও। *s.end() পড়া হলো undefined behaviour: কী হবে, C++ standard কিছুই বলে না। তাই সোজা হ্যাঁ বা না-এর জন্য count নাও, আর জায়গাটাও লাগলে find।

মান ধরে erase

s.erase(x) x-কে সরিয়ে দেয়, যদি set-এ x থাকে। না থাকলে কিছুই হয় না।

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

int main() {
    set<int> s{3, 9, 14, 27, 31};
    s.erase(14);
    s.erase(5);
    cout << "left:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
    return 0;
}

left: 3 9 27 31 (size 4)

erase(14) 14-কে সরাল। erase(5) কোনো 5 পেল না, কিছুই করল না, কোনো error-ও দিল না। তাই নেই এমন মান erase করা নিরাপদ, কিন্তু নেই এমন মান পড়া নিরাপদ না।

সবচেয়ে ছোট আর সবচেয়ে বড়

s.begin() হলো সবচেয়ে ছোট মানের জায়গা, তাই *s.begin() সেটা পড়ে। s.rbegin() হলো উল্টো দিকে হাঁটার শুরু, r মানে reverse, তাই *s.rbegin() হলো সবচেয়ে বড় মান।

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

int main() {
    set<int> temps{31, 28, 35, 29};
    cout << "coolest " << *temps.begin() << ", hottest " << *temps.rbegin() << '\n';
    temps.insert(38);
    temps.erase(28);
    cout << "coolest " << *temps.begin() << ", hottest " << *temps.rbegin() << '\n';

    set<int> none;
    if (none.empty()) {
        cout << "an empty set has no coolest\n";
    }
    return 0;
}

coolest 28, hottest 35
coolest 29, hottest 38
an empty set has no coolest

Insert আর erase-এর পরে দুই মাথাই সরে গেল, অথচ program ওদের একবারও খুঁজতে যায়নি। খালি set-এর কোনো সবচেয়ে ছোট বা সবচেয়ে বড় মান নেই। ওখানে *s.begin() আর *s.rbegin() undefined, আর একবার চালাতে কী হয়েছিল, সেটা দেখাবে lesson 06। তাই কোনো মাথা পড়ার আগে empty() check করো।

Index নেই, আর জায়গায় বসে মান বদলানোও নেই

Vector-এর জায়গার নম্বর আছে, তাই v[0] ওর প্রথম element। Set-এর জায়গার কোনো নম্বর নেই, তাই index দিলে compile-ই হয় না।

set<int> s{10, 20, 30};
cout << s[0] << '\n';

Runner-এর flag-এ GCC 12 থেমে যায় error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int') দিয়ে। তৃতীয় মানে পৌঁছাতে begin() থেকে হেঁটে যেতে হয়, কীভাবে, সেটা দেখাবে lesson 03। Iterator দিয়ে মান বদলানোও compile হয় না।

set<int> s{10, 20, 30};
auto it = s.find(20);
*it = 25;

GCC 12 বলে error: assignment of read-only location 'it.std::_Rb_tree_const_iterator<int>::operator*()'। কারণটা tree, যেটা মান ধরে সাজানো। 20-কে জায়গায় বসেই 25 বানালে ও ভুল জায়গায় বসে থাকবে, আর পরের খোঁজগুলো ভুল পথে যাবে। তাই library প্রতিটা মান দেয় read-only করে: পড়তে পারবে, কিন্তু লিখতে কখনো না।

তাই set বদলাও শুধু insert আর erase দিয়ে: আগে পুরোনো মানটা erase করো, তারপর নতুনটা insert। Node-টা রেখেই এই কাজ করার একটা উপায় দেখাবে lesson 02।

multiset: যে set repeat-ও রাখে

কখনো কখনো repeat-গুলোই আসল কথা। ক্লাস কোথায় বেড়াতে যাবে, সেই ভোটে প্রতিটা ভোট লাগে, এক জায়গার জন্য একটা না। Multiset হলো এমন একটা set, যেটা repeat-ও রাখে। একই নিয়মে সাজায়, একই header-এ থাকে, call-গুলোও একই। ওর count(x) বলে x-এর কয়টা copy আছে।

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

int main() {
    multiset<string> votes{"zoo", "museum", "zoo", "park", "zoo"};
    cout << "votes:";
    for (const string& v : votes) {
        cout << ' ' << v;
    }
    cout << " (size " << votes.size() << ")\n";
    cout << "zoo: " << votes.count("zoo") << ", lake: " << votes.count("lake") << '\n';
    return 0;
}

votes: museum park zoo zoo zoo (size 5)
zoo: 3, lake: 0

Zoo-র তিনটা ভোটই রইল, পাশাপাশি, কারণ সাজানো ক্রমে সমান মানগুলো গায়ে গায়ে বসে। এগুলোর মধ্যে শুধু একটা সরাতে আলাদা একটা call লাগে, সেটা দেখাবে lesson 02। তাই প্রতিটা copy লাগলে multiset নাও, আর একটা হলেই চললে set।

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

int main() {
    set<int> s;
    for (int x : {42, 7, 19, 7, 3}) {
        s.insert(x);
    }
    cout << "sorted:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n' << s.size() << " different values\n";
    return 0;
}

sorted: 3 7 19 42
4 different values

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

int main() {
    set<string> signed_up;
    for (string name : {"maria", "bob", "zara", "bob", "amara"}) {
        signed_up.insert(name);
    }

    for (string who : {"kenji", "zara"}) {
        if (signed_up.count(who) == 1) {
            cout << who << " is on the list\n";
        } else {
            cout << who << " is not on the list yet\n";
        }
    }

    signed_up.insert("kenji");
    auto it = signed_up.find("kenji");
    if (it != signed_up.end()) {
        cout << "now " << *it << " is on it too\n";
    }
    cout << signed_up.size() << " different people so far\n";
    return 0;
}

kenji is not on the list yet
zara is on the list
now kenji is on it too
5 different people so far

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

int main() {
    set<int> booked{12, 3, 27, 8, 15};
    booked.erase(3);
    booked.insert(30);

    cout << "booked:";
    for (int seat : booked) {
        cout << ' ' << seat;
    }
    cout << '\n';
    cout << "nearest the stage: " << *booked.begin() << ", farthest: " << *booked.rbegin() << '\n';
    if (booked.count(3) == 0) {
        cout << "seat 3 is free again\n";
    }
    return 0;
}

booked: 8 12 15 27 30
nearest the stage: 8, farthest: 30
seat 3 is free again

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

int main() {
    multiset<int> marks{85, 72, 85, 90, 64, 85, 72};
    set<int> different{85, 72, 85, 90, 64, 85, 72};

    cout << "every mark:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';
    cout << marks.count(85) << " students scored 85\n";
    cout << "lowest " << *marks.begin() << ", highest " << *marks.rbegin() << '\n';
    cout << "the multiset keeps " << marks.size() << ", a set keeps " << different.size() << '\n';
    return 0;
}

every mark: 64 72 72 85 85 85 90
3 students scored 85
lowest 64, highest 90
the multiset keeps 7, a set keeps 4

set<int> prices{10, 20, 30};
for (int& p : prices) {
    p += 5;
}

#include <iostream>
using namespace std;

int main() {
    set<int> s{3, 1, 2};
    cout << s.size() << '\n';
    return 0;
}

set<string> steps;
steps.insert("wash");
steps.insert("cut");
steps.insert("cook");
for (const string& s : steps) {
    cout << s << '\n';
}

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

int main() {
    set<string> s{"bob", "Zara", "amara"};
    cout << "order:";
    for (const string& name : s) {
        cout << ' ' << name;
    }
    cout << '\n';
    return 0;
}

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

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

    int n = 0;
    cin >> n;
    set<string> names;   // every different name, kept in alphabetical order
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        // Add name to names.
    }

    // Print how many different names there are, then every name in
    // alphabetical order, one per line.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    set<int> first;
    for (int i = 0; i < n; i++) {
        int mark;
        cin >> mark;
        first.insert(mark);
    }
    int m;
    cin >> m;
    set<int> second;
    for (int i = 0; i < m; i++) {
        int mark;
        cin >> mark;
        second.insert(mark);
    }

    // Walk first from its lowest mark. Print every mark that second also
    // holds, on one line, separated by single spaces, or the word none.

    return 0;
}

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

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

    int n;
    cin >> n;
    set<int> board;   // the highest different scores, never more than five
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        // Put score on the board, keep only the five highest, then print
        // the lowest score left on the board.
    }
    return 0;
}

এরপর lesson 02 set আর multiset-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ।