Open8

C++ の map を学ぶ

log5log5

https://paiza.io/projects/Ar4NEYhkWCybKkTfPMjVmw

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
template<typename L, typename R>
std::ostream & operator<<(std::ostream & Str, pair<L, R> const & p) {
    Str << "< " << p.first << " : " << p.second << " >";
    return Str;
}

template<typename T, typename U>
std::ostream & operator<<(std::ostream & Str, map<T, U> const & mp) {
    Str << "[";
    for (pair<T, U> p: mp) {
        Str << p;
    }
    Str << "]";
    return Str;
}

int main() {

    map<ll,ll> mymap;
    mymap.insert({1,2});
    mymap.insert({2,5});
    mymap.emplace(3, 7);

    cout << mymap << endl;

    return 0;
}

[< 1 : 2 >< 2 : 5 >< 3 : 7 >]

Process finished with exit code 0
log5log5

注目点

int main() {

    map<ll,ll> mymap;
    mymap.emplace(1,2);
    mymap.emplace(99, 1);
    mymap.emplace(9999, 99999);
    mymap.emplace(3, 7);

    cout << mymap << endl;

    return 0;
}

[< 1 : 2 >< 3 : 7 >< 99 : 1 >< 9999 : 99999 >]

Process finished with exit code 0f
log5log5

重複して挿入できない

int main() {

    map<ll,ll> mymap;
    mymap.emplace(1,1);
    mymap.emplace(1, 2);
    mymap.emplace(1, 3);
    mymap.emplace(1, 4);

    cout << mymap << endl;

    return 0;
}
[< 1 : 1 >]

Process finished with exit code 0
log5log5

マージ

int main() {

    map<ll,ll> mp1, mp2;
    mp1.emplace(1, 1);
    mp1.emplace(2, 4);
    mp2.emplace(3, 9);
    mp2.emplace(4, 16);
    mp2.emplace(5, 25);

    mp1.merge(mp2);

    cout << mp1 << endl;
    cout << mp2 << endl;

    return 0;
}
[< 1 : 1 >< 2 : 4 >< 3 : 9 >< 4 : 16 >< 5 : 25 >]
[]
log5log5

キー重複でマージできなかった場合は残る
https://paiza.io/projects/9Jdfo2MP_fgFhuZ-R2cHTw?language=cpp

int main() {

    map<ll,ll> mp1, mp2;
    mp1.emplace(1, 1);
    mp1.emplace(2, 4);
    mp2.emplace(1, 9);
    mp2.emplace(2, 16);
    mp2.emplace(3, 25);

    mp1.merge(mp2);

    cout << mp1 << endl;
    cout << mp2 << endl;

    return 0;
}
[< 1 : 1 >< 2 : 4 >< 3 : 25 >]
[< 1 : 9 >< 2 : 16 >]

log5log5

valueが数値だったときに、同じキー同士で合算させたい
https://paiza.io/projects/hf3TeWoOoBvdyuWf3AOp0w?language=cpp

int main() {

    vector<pair<ll, ll>> vpl;

    vpl.emplace_back(1, 2);
    vpl.emplace_back(2, 3);
    vpl.emplace_back(2, 5);
    vpl.emplace_back(3, 7);
    vpl.emplace_back(4, 11);

    map<ll, ll> mp;
    for (pair<ll, ll> p: vpl) {
        if (!mp.count(p.first)) mp.insert(p);
        else mp.at(p.first) += p.second;
    }

    cout << mp << endl;

    return 0;
}
[< 1 : 2 >< 2 : 8 >< 3 : 7 >< 4 : 11 >]

もっといい方法はないかな?
count の計算量が O(\log{N}) なのは気になる

log5log5

ちょっと寄り道
https://paiza.io/projects/KcRjniHWWfUZdKOKGSayug?language=cpp

template <typename T, typename K>
map<K, T> merge_value(vector<pair<K, T>> vpl) {
    map<K, T> mp;
    for (pair<K, T> p: vpl) {
        if (!mp.count(p.first)) mp.insert(p);
        else mp.at(p.first) += p.second;
    }
    return mp;
}

int main() {

    vector<pair<ll, ll>> vpl;

    vpl.emplace_back(1, 2);
    vpl.emplace_back(2, 3);
    vpl.emplace_back(2, 5);
    vpl.emplace_back(3, 7);
    vpl.emplace_back(4, 11);

    cout << merge_value(vpl) << endl;

    return 0;
}
[< 1 : 2 >< 2 : 8 >< 3 : 7 >< 4 : 11 >]

Process finished with exit code 0

数値型の元締めみたいなものってないのかな