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

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

Maps

A map keeps a value for every key: adding and replacing, counting with cnt[x]++, walking in key order, looking without adding, erasing keys in a sliding window, lookup tables, and pairs as keys.

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

A set remembers which values it has seen. A map remembers something for each key: a phone number for each name, a count for each word, a price for each item on the menu. It is a table of key → value pairs, each key once, kept sorted by key.

A value for every key

map<K, V> names two types: the key's and the value's. m[key] = value adds the key, or replaces its value if the key is already there — a map never holds the same key twice. m[key] on its own reads the value, and m.size() is the number of keys.

Counting with a map

The most common map in a solution counts things:

The first time x comes up it isn't a key yet. cnt[x] then adds it with the value 0 — the starting value for any number — and ++ makes it 1. After that, every cnt[x]++ finds the key and adds one. Watch the keys arrive:

A map counts: a new key starts at 0

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<string> cars = {"red", "white", "red", "blue", "white", "red"};

9 map<string, int> cnt;

10 for (string c : cars) {

11 cnt[c]++;

12 }

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

14 for (auto p : cnt) {

15 cout << p.first << " " << p.second << "\n";

16 }

17 return 0;

18}

Six cars

сатр 8

The colours are words, so they can't be array indices.

cars6 катак

"red"

"white"

"red"

"blue"

"white"

"red"

0

1

2

3

4

5

map<string, int> cntЛуғат

холӣ

c—p—

1 / 23

навбатӣ

Practice: Maps

Four problems where a map keeps something for every key.

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

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

map<string, int> phone;     // key: a name, value: a number
phone["Mia"] = 4021;        // adds the key "Mia"
phone["Ali"] = 3310;
phone["Mia"] = 5577;        // "Mia" is already a key: its value is replaced
cout << phone["Mia"];       // 5577
cout << phone.size();       // 2

4 different words
fog 1
rain 2
snow 1
sun 3

0 0: 1
1 2: 3
3 -1: 1

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

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

    int n;
    cin >> n;
    map<string, int> cnt;             // word -> how many times it appeared
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        cnt[w]++;                     // a new word starts at 0, then becomes 1
    }

    cout << cnt.size() << " different words" << "\n";
    for (auto p : cnt) {              // keys in alphabetical order
        cout << p.first << " " << p.second << "\n";
    }
    return 0;
}

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

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

    map<string, int> price;
    price["tea"] = 5;
    price["cake"] = 12;

    cout << price["juice"] << "\n";   // careful: [] adds "juice" with the value 0
    cout << price.size() << "\n";     // 3 keys now

    cout << price.count("milk") << "\n";      // count() only looks: 1 or 0
    cout << price.size() << "\n";             // still 3

    auto it = price.find("cake");     // find() gives the key's place, or end() if it is missing
    if (it != price.end()) {
        cout << it->first << " costs " << it->second << "\n";
    }

    price.erase("juice");             // removes the key and its value
    cout << price.size() << "\n";
    return 0;
}

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

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

    vector<string> names = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    map<string, int> day;             // a lookup table: name -> its number
    for (int i = 0; i < 7; i++) {
        day[names[i]] = i;
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string from, to;
        cin >> from >> to;
        int d = day[to] - day[from];  // can be negative: from Fri to Tue is 1 - 4 = -3
        d = (d % 7 + 7) % 7;          // turns any whole number into 0..6
        cout << d << "\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;
    map<pair<int, int>, int> cnt;     // the key is a whole point (x, y)
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        cnt[{x, y}]++;                // {x, y} makes the pair
    }

    for (auto p : cnt) {              // by x, and by y when the x's are equal
        cout << p.first.first << " " << p.first.second << ": " << p.second << "\n";
    }
    return 0;
}