C++进阶：（五）map系列容器的全面解析

template <class T1, class T2>
struct pair {
    typedef T1 first_type;  // 第一个成员的类型（对应map的key）
    typedef T2 second_type; // 第二个成员的类型（对应map的value）

    T1 first;  // 关键字（key），在map中为const类型，不可修改
    T2 second; // 值（value），可修改

    // 无参构造：默认初始化两个成员
    pair() : first(T1()), second(T2()) {}

    // 带参构造：通过指定值初始化
    pair(const T1& a, const T2& b) : first(a), second(b) {}

    // 拷贝构造：从其他pair对象拷贝初始化
    template<class U, class V>
    pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {}
};

template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

// 1. 直接构造pair（需显式指定模板参数）
pair<string, int> kv1("apple", 5);

// 2. 通过make_pair构造（自动推导类型，更简洁）
auto kv2 = make_pair("banana", 3);

template < 
    class Key,                     // 1. 关键字（key）的类型
    class T,                       // 2. 值（value）的类型
    class Compare = less<Key>,     // 3. 排序规则（默认升序）
    class Alloc = allocator<pair<const Key, T>>  // 4. 空间配置器
> class map;

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

int main() {
    // 自定义排序规则：按key降序（使用STL内置的greater<int>）
    map<int, string, greater<int>> descMap = {
        {3, "apple"}, 
        {1, "banana"}, 
        {2, "orange"}
    };

    // 遍历：按key降序输出
    for (const auto& kv : descMap) {
        cout << kv.first << ": " << kv.second << endl;
    }
    /* 输出结果：
    3: apple
    2: orange
    1: banana
    */
    return 0;
}

// 1. 无参构造：创建空map，使用默认比较规则与空间配置器
explicit map(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

// 2. 迭代器区间构造：用[first, last)区间的键值对初始化
template <class InputIterator>
map(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// 3. 拷贝构造：用另一个map对象初始化
map(const map& x);

// 4. 初始化列表构造：用初始化列表中的键值对初始化（最常用）
map(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

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

int main() {
    // 1. 无参构造
    map<int, string> m1;
    m1.insert(make_pair(1, "one"));
    m1.insert({2, "two"});  // C++11列表初始化简化
    cout << "m1（无参构造+插入）：" << endl;
    for (const auto& kv : m1) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：1: one 2: two 

    // 2. 初始化列表构造（最简洁，推荐）
    map<int, string> m2 = {
        {3, "three"}, 
        {4, "four"}, 
        {5, "five"}
    };
    cout << "m2（初始化列表构造）：" << endl;
    for (const auto& kv : m2) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：3: three 4: four 5: five 

    // 3. 迭代器区间构造（用m2的部分区间初始化m3）
    auto start = ++m2.begin();  // 指向4: four
    auto end = m2.end();        // 指向尾后迭代器
    map<int, string> m3(start, end);
    cout << "m3（迭代器区间构造）：" << endl;
    for (const auto& kv : m3) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：4: four 5: five 

    // 4. 拷贝构造（用m2初始化m4）
    map<int, string> m4(m2);
    cout << "m4（拷贝构造）：" << endl;
    for (const auto& kv : m4) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：3: three 4: four 5: five 

    return 0;
}

// 正向迭代器：指向第一个元素
iterator begin();
const_iterator begin() const;

// 正向尾后迭代器：不指向任何元素，作为遍历结束标志
iterator end();
const_iterator end() const;

// 反向迭代器：指向最后一个元素（逆序遍历的起点）
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

// 反向尾后迭代器：作为逆序遍历的结束标志
reverse_iterator rend();
const_reverse_iterator rend() const;

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

int main() {
    map<string, int> fruitCount = {
        {"apple", 5}, 
        {"banana", 3}, 
        {"orange", 4}
    };

    // 1. 正向非const迭代器遍历（可修改value）
    cout << "正向遍历（修改value前）：" << endl;
    auto it = fruitCount.begin();
    while (it != fruitCount.end()) {
        // it->first = "pear";  // 错误：key为const，不可修改
        cout << it->first << ": " << it->second << " ";
        it->second += 1;  // 合法：修改value
        ++it;
    }
    cout << endl;  // 输出：apple: 5 banana: 3 orange: 4 

    // 2. 正向const迭代器遍历（完全只读）
    cout << "正向const遍历（修改value后）：" << endl;
    map<string, int>::const_iterator cit = fruitCount.cbegin();
    while (cit != fruitCount.cend()) {
        // cit->second += 1;  // 错误：const迭代器不可修改value
        cout << cit->first << ": " << cit->second << " ";
        ++cit;
    }
    cout << endl;  // 输出：apple: 6 banana: 4 orange: 5 

    // 3. 反向迭代器遍历（逆序输出）
    cout << "反向遍历：" << endl;
    map<string, int>::reverse_iterator rit = fruitCount.rbegin();
    while (rit != fruitCount.rend()) {
        cout << rit->first << ": " << rit->second << " ";
        ++rit;
    }
    cout << endl;  // 输出：orange: 5 banana: 4 apple: 6 

    // 4. 范围for遍历（最简洁，推荐）
    cout << "范围for遍历：" << endl;
    for (const auto& kv : fruitCount) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：apple: 6 banana: 4 orange: 5 

    return 0;
}

// 1. 插入单个键值对：返回pair<iterator, bool>
pair<iterator, bool> insert(const value_type& val);

// 2. 插入初始化列表中的键值对
void insert(initializer_list<value_type> il);

// 3. 插入[first, last)区间的键值对
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

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

int main() {
    map<int, string> dict;

    // 1. 插入方式1：直接构造pair（显式模板参数）
    pair<int, string> kv1(1, "one");
    auto ret1 = dict.insert(kv1);
    cout << "插入kv1（1, one）：" << (ret1.second ? "成功" : "失败") 
         << "，当前key对应的value：" << ret1.first->second << endl;  // 成功，one

    // 2. 插入方式2：make_pair（自动推导类型）
    auto ret2 = dict.insert(make_pair(2, "two"));
    cout << "插入make_pair(2, two)：" << (ret2.second ? "成功" : "失败") 
         << "，当前key对应的value：" << ret2.first->second << endl;  // 成功，two

    // 3. 插入方式3：C++11列表初始化（最简洁）
    auto ret3 = dict.insert({3, "three"});
    cout << "插入{3, three}：" << (ret3.second ? "成功" : "失败") 
         << "，当前key对应的value：" << ret3.first->second << endl;  // 成功，three

    // 4. 插入方式4：插入重复key（失败案例）
    auto ret4 = dict.insert({3, "three_new"});
    cout << "插入{3, three_new}：" << (ret4.second ? "成功" : "失败") 
         << "，当前key对应的value：" << ret4.first->second << endl;  // 失败，three

    // 5. 批量插入：初始化列表
    dict.insert({4, "four"}, {5, "five"});  // 错误：需用大括号包裹所有键值对
    dict.insert({{4, "four"}, {5, "five"}});  // 正确：批量插入两个键值对
    cout << "批量插入后dict：" << endl;
    for (const auto& kv : dict) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：1: one 2: two 3: three 4: four 5: five 

    return 0;
}

// 1. 精确查找：返回指向key的迭代器，未找到返回end()
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;

// 2. 计数查找：返回key的个数（map中仅0或1，multimap中为实际个数）
size_type count(const key_type& k) const;

// 3. 范围查找：返回第一个>=k的迭代器
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;

// 4. 范围查找：返回第一个>k的迭代器
iterator upper_bound(const key_type& k);
const_iterator upper_bound(const key_type& k) const;

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

int main() {
    map<int, string> dict = {
        {1, "one"}, {2, "two"}, {3, "three"}, 
        {4, "four"}, {5, "five"}
    };

    // 1. find精确查找
    int targetKey = 3;
    auto findIt = dict.find(targetKey);
    if (findIt != dict.end()) {
        cout << "找到key=" << targetKey << "，value=" << findIt->second << endl;  // 找到，three
    } else {
        cout << "未找到key=" << targetKey << endl;
    }

    targetKey = 6;
    findIt = dict.find(targetKey);
    if (findIt != dict.end()) {
        cout << "找到key=" << targetKey << "，value=" << findIt->second << endl;
    } else {
        cout << "未找到key=" << targetKey << endl;  // 未找到
    }

    // 2. count计数查找
    targetKey = 4;
    size_t count = dict.count(targetKey);
    cout << "key=" << targetKey << "的个数：" << count << endl;  // 1

    targetKey = 7;
    count = dict.count(targetKey);
    cout << "key=" << targetKey << "的个数：" << count << endl;  // 0

    // 3. lower_bound/upper_bound范围查找（查找key在[2,4]区间的键值对）
    auto lowIt = dict.lower_bound(2);  // 第一个>=2的迭代器（key=2）
    auto upIt = dict.upper_bound(4);   // 第一个>4的迭代器（key=5）
    cout << "key在[2,4]区间的键值对：" << endl;
    for (auto it = lowIt; it != upIt; ++it) {
        cout << it->first << ": " << it->second << " ";
    }
    cout << endl;  // 输出：2: two 3: three 4: four 

    return 0;
}

// 1. 按迭代器位置删除：返回删除元素的下一个元素的迭代器
iterator erase(const_iterator position);

// 2. 按key值删除：返回删除的元素个数（map中0或1）
size_type erase(const key_type& k);

// 3. 按迭代器区间删除：返回删除区间的下一个元素的迭代器
iterator erase(const_iterator first, const_iterator last);

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

int main() {
    map<int, string> dict = {
        {1, "one"}, {2, "two"}, {3, "three"}, 
        {4, "four"}, {5, "five"}
    };

    // 1. 按迭代器位置删除（删除key=3）
    auto posIt = dict.find(3);
    if (posIt != dict.end()) {
        dict.erase(posIt);
        cout << "删除key=3后dict：" << endl;
        for (const auto& kv : dict) {
            cout << kv.first << ": " << kv.second << " ";
        }
        cout << endl;  // 输出：1: one 2: two 4: four 5: five 
    }

    // 2. 按key值删除（删除key=5）
    size_t delCount = dict.erase(5);
    cout << "删除key=5：" << (delCount ? "成功" : "失败") << endl;  // 成功
    cout << "删除key=5后dict：" << endl;
    for (const auto& kv : dict) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：1: one 2: two 4: four 

    // 3. 按区间删除（删除key在[2,4]区间）
    auto lowIt = dict.lower_bound(2);  // key=2
    auto upIt = dict.upper_bound(4);   // key=5（已被删除，实际为end()）
    dict.erase(lowIt, upIt);
    cout << "删除区间[2,4]后dict：" << endl;
    for (const auto& kv : dict) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：1: one 

    return 0;
}

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

int main() {
    map<string, int> fruitCount = {{"apple", 5}, {"banana", 3}};

    // 查找并修改apple的数量
    auto it = fruitCount.find("apple");
    if (it != fruitCount.end()) {
        it->second += 2;  // 将5改为7
    }

    cout << "修改后fruitCount：" << endl;
    for (const auto& kv : fruitCount) {
        cout << kv.first << ": " << kv.second << " ";
    }
    cout << endl;  // 输出：apple: 7 banana: 3 

    return 0;
}

// 声明：返回value的引用，可修改
mapped_type& operator[](const key_type& k);

// 内部实现（简化版）
mapped_type& operator[](const key_type& k) {
    // 尝试插入键值对{k, mapped_type()}（mapped_type()为默认值，如int默认0）
    pair<iterator, bool> ret = insert({k, mapped_type()});
    // 返回value的引用（无论插入成功与否，ret.first均指向目标key的迭代器）
    return ret.first->second;
}

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

int main() {
    map<string, string> dict;

    // 1. 功能1：插入键值对（key不存在）
    dict["insert"];  // 插入{"insert", ""}（string默认空串）
    dict["left"] = "左边";  // 插入{"left", "左边"}
    cout << "插入后dict：" << endl;
    cout << "insert: " << dict["insert"] << endl;  // 输出：insert: 
    cout << "left: " << dict["left"] << endl;      // 输出：left: 左边

    // 2. 功能2：查找value（key存在）
    string value = dict["left"];
    cout << "查找left的value：" << value << endl;  // 输出：左边

    // 3. 功能3：修改value（key存在）
    dict["left"] = "左边、剩余";  // 将"左边"改为"左边、剩余"
    cout << "修改后left的value：" << dict["left"] << endl;  // 输出：左边、剩余

    // 4. 综合示例：统计单词出现次数
    string words[] = {"apple", "banana", "apple", "orange", "apple"};
    map<string, int> wordCount;
    for (const auto& word : words) {
        wordCount[word]++;  // 关键：不存在则插入（默认0）并+1；存在则直接+1
    }
    cout << "单词统计结果：" << endl;
    for (const auto& kv : wordCount) {
        cout << kv.first << ": " << kv.second << "次" << endl;
    }
    /* 输出：
    apple: 3次
    banana: 1次
    orange: 1次
    */

    return 0;
}

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

int main() {
    // 1. 初始化multimap（插入重复key）
    multimap<int, string> courseMap;
    courseMap.insert({101, "C++"});
    courseMap.insert({101, "Data Structure"});  // 插入相同key=101
    courseMap.insert({102, "Python"});
    courseMap.insert({101, "Algorithm"});        // 再次插入key=101
    cout << "multimap初始化结果：" << endl;
    for (const auto& kv : courseMap) {
        cout << "Course ID: " << kv.first << ", Name: " << kv.second << endl;
    }
    /* 输出（按key升序，相同key相邻）：
    Course ID: 101, Name: C++
    Course ID: 101, Name: Data Structure
    Course ID: 101, Name: Algorithm
    Course ID: 102, Name: Python
    */

    // 2. find接口：返回第一个匹配key的迭代器
    auto findIt = courseMap.find(101);
    if (findIt != courseMap.end()) {
        cout << "\n第一个key=101的课程：" << findIt->second << endl;  // 输出：C++
        // 遍历所有key=101的课程
        cout << "所有key=101的课程：" << endl;
        while (findIt != courseMap.end() && findIt->first == 101) {
            cout << findIt->second << " ";
            ++findIt;
        }
        cout << endl;  // 输出：C++ Data Structure Algorithm
    }

    // 3. count接口：统计key的个数
    size_t courseCount = courseMap.count(101);
    cout << "\nkey=101的课程个数：" << courseCount << endl;  // 输出：3

    // 4. erase接口：按key删除所有匹配项
    size_t delCount = courseMap.erase(101);
    cout << "删除key=101的课程个数：" << delCount << endl;  // 输出：3
    cout << "删除后multimap：" << endl;
    for (const auto& kv : courseMap) {
        cout << "Course ID: " << kv.first << ", Name: " << kv.second << endl;
    }
    /* 输出：
    Course ID: 102, Name: Python
    */

    return 0;
}

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

// 随机链表节点定义
struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;

        map<Node*, Node*> nodeMap;  // 建立原节点到拷贝节点的映射
        Node* copyHead = nullptr;
        Node* copyTail = nullptr;
        Node* cur = head;

        // 第一遍遍历：拷贝节点val，建立映射
        while (cur != nullptr) {
            Node* newNode = new Node(cur->val);
            nodeMap[cur] = newNode;  // 存储{原节点, 拷贝节点}

            // 构建拷贝链表的next指针（初步）
            if (copyTail == nullptr) {
                copyHead = copyTail = newNode;
            } else {
                copyTail->next = newNode;
                copyTail = copyTail->next;
            }

            cur = cur->next;
        }

        // 第二遍遍历：处理拷贝节点的random指针
        cur = head;
        Node* copyCur = copyHead;
        while (cur != nullptr) {
            // 原节点的random对应拷贝节点的random
            if (cur->random != nullptr) {
                copyCur->random = nodeMap[cur->random];
            } else {
                copyCur->random = nullptr;
            }

            cur = cur->next;
            copyCur = copyCur->next;
        }

        return copyHead;
    }
};

// 测试代码：创建随机链表并拷贝
int main() {
    Solution sol;

    // 创建原链表：1 -> 2 -> 3
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    // 设置random指针：1->3，2->1，3->null
    head->random = head->next->next;
    head->next->random = head;
    head->next->next->random = nullptr;

    // 拷贝链表
    Node* copyHead = sol.copyRandomList(head);

    // 验证拷贝结果
    Node* cur = copyHead;
    cout << "拷贝链表节点及random：" << endl;
    while (cur != nullptr) {
        cout << "Node val: " << cur->val;
        if (cur->random != nullptr) {
            cout << ", Random val: " << cur->random->val << endl;
        } else {
            cout << ", Random: null" << endl;
        }
        cur = cur->next;
    }
    /* 输出（与原链表一致）：
    Node val: 1, Random val: 3
    Node val: 2, Random val: 1
    Node val: 3, Random: null
    */

    // 释放内存（简化处理）
    delete head->next->next;
    delete head->next;
    delete head;
    delete copyHead->next->next;
    delete copyHead->next;
    delete copyHead;

    return 0;
}

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    // 自定义排序规则：先按频率降序，再按字典序升序
    struct Compare {
        bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
            if (a.second != b.second) {
                return a.second > b.second;  // 频率降序
            } else {
                return a.first < b.first;   // 字典序升序
            }
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1. 用map统计单词频率（map默认按key字典序排序，便于后续频率相同时的排序）
        map<string, int> countMap;
        for (const auto& word : words) {
            countMap[word]++;  // 统计频率，key自动按字典序排序
        }

        // 2. 将map转换为vector，便于排序
        vector<pair<string, int>> freqVec(countMap.begin(), countMap.end());

        // 3. 按自定义规则排序
        sort(freqVec.begin(), freqVec.end(), Compare());

        // 4. 取前K个单词作为结果
        vector<string> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(freqVec[i].first);
        }

        return result;
    }
};

// 测试代码
int main() {
    Solution sol;
    vector<string> words = {
        "i", "love", "leetcode", "i", "love", "coding"
    };
    int k = 2;

    vector<string> topK = sol.topKFrequent(words, k);
    cout << "前" << k << "个高频单词：" << endl;
    for (const auto& word : topK) {
        cout << word << " ";
    }
    cout << endl;  // 输出：i love 

    return 0;
}