Sets - Забони барномасозии C++ барои барномасозии рақобатӣ

Week 11Sets, Maps, Multisets and Key-Based Data Processing

Sets

A set keeps each value once and in order: insert, size and walking in order, count and find, erase, the nearest values with lower_bound and upper_bound, and one set of positions for each letter.

Назария
Дарси 1 аз 7
Хониш: 19 дақиқа
Саволҳо: 6

A vector remembers everything: every value, in the order it came, duplicates included. Often a problem needs less than that, and needs it fast. Which values have appeared? Is this one of them? Searching a vector of 200 000 values for each of 200 000 questions takes 40 billion steps. A set answers each question in about 18.

A set keeps each value once, in order

A set follows two rules, and keeps them by itself:

No duplicates. Inserting a value that is already there changes nothing.
Always sorted. The values are kept in increasing order, whatever order they arrive in. You never call sort.

s.size() is the number of values in the set — so after inserting everything, it is the number of different values. s.empty() says whether the set has nothing in it. Step through six inserts and watch where each value lands:

A set keeps one copy of each value, in order

C++

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

7

8 vector<int> a = {40, 10, 40, 25, 10, 5};

9 set<int> s;

10 for (int x : a) {

11 s.insert(x);

12 }

13 cout << s.size() << "\n";

14 for (int x : s) {

15 cout << x << " ";

16 }

17 cout << "\n";

18 return 0;

19}

Six values

сатр 8

Two of them come twice: 40 and 10.

a6 катак

40

10

40

25

10

5

0

1

2

3

4

5

set<int> s0 катак

x—

1 / 26

навбатӣ

Practice: Sets

Five problems solved with a set.

Дарси навбатӣ

Дарси пешина Ба харитаи курс

	`vector<int>`	`set<int>`
Duplicates	kept	dropped
Order	as inserted	always increasing
`a[i]`	one step	not available
Is `x` there?	look at every value: `n` steps	`count` / `find`: about log₂ n
Nearest value to `x`	sort first, then search	`lower_bound` / `upper_bound`: about log₂ n
Add or remove a value	at the end: one step; in the middle: up to `n`	about log₂ n, anywhere

set<int> s;            // an empty set of ints
s.insert(40);
s.insert(10);
s.insert(40);          // 40 is already there: nothing happens
s.insert(25);          // s is now {10, 25, 40}
cout << s.size();      // 3

4
10 20 40 50

30 20
50 50
10 -

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);                  // a value that is already there is not added again
    }

    cout << s.size() << "\n";         // how many different values
    for (int x : s) {                 // smallest to largest
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    set<string> invited;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        invited.insert(name);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string name;
        cin >> name;
        if (invited.count(name)) {    // 1 if the name is in the set, 0 if not
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    set<int> stops;                   // where the bus stops are along the road
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        stops.insert(x);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;

        auto it = stops.lower_bound(x);       // the first stop at x or after it
        if (it == stops.end()) {
            cout << "-";                      // every stop is before x
        } else {
            cout << *it;
        }
        cout << " ";

        it = stops.upper_bound(x);            // the first stop after x
        if (it == stops.begin()) {
            cout << "-";                      // that is the very first stop: none at x or before
        } else {
            it--;                             // one step back: the last stop at x or before
            cout << *it;
        }
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    vector<set<int>> pos(26);         // pos[0]: where the a's are, pos[1]: the b's, ...
    for (int i = 0; i < (int)s.size(); i++) {
        pos[s[i] - 'a'].insert(i + 1);        // positions counted from 1
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        for (int c = 0; c < 26; c++) {
            auto it = pos[c].lower_bound(l);  // this letter's first position at l or after
            if (it != pos[c].end() && *it <= r) {
                cout << (char)('a' + c);      // it is inside [l, r]
            }
        }
        cout << "\n";
    }
    return 0;
}