map/multimap容器

map和multimap都是以红黑树为底层实现机制。

map和multimap的操作类似，唯一区别multimap键值可重复。

map的特性

• 所有元素都会根据元素的键值自动排序。
• map所有的元素都是pair，同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。

我们可以通过map的迭代器改变map的键值吗？

答案是不行，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。

map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

对组

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。

类模板：template <class T1, class T2> struct pair

如何创建对组?

//第一种方法创建一个对组
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值
//第二种
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

map/multimap常用API

map构造函数

map<T1, T2> mapTT;//map默认构造函数: 
map(const map &mp);//拷贝构造函数

map赋值操作

map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器

map大小操作

size();//返回容器中元素的数目
empty();//判断容器是否为空

map插入数据元素操作

map.insert(...); //往容器插入元素，返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

map删除操作

clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。

map查找操作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

multimap案例

公司今天招聘了5个员工，5名员工进入公司之后，需要指派员工在那个部门工作

• 人员信息有: 姓名 年龄 电话 工资等组成
• 通过multimap进行信息的插入 保存 显示
• 分部门显示员工信息 显示全部员工信息

点击查看代码

#define _CRT_SECURE_NO_WARNINGS

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

//multimap 案例
//公司今天招聘了 5 个员工，5 名员工进入公司之后，需要指派员工在那个部门工作
//人员信息有: 姓名 年龄 电话 工资等组成
//通过 multimap 进行信息的插入 保存 显示
//分部门显示员工信息 显示全部员工信息


#define SALE_DEPATMENT 1 //销售部门
#define DEVELOP_DEPATMENT 2 //研发部门
#define FINACIAL_DEPATMENT 3 //财务部门
#define ALL_DEPATMENT 4 //所有部门

//员工类
class person{
public:
    string name; //员工姓名
    int age; //员工年龄
    double salary; //员工工资
    string tele; //员工电话
};

//创建5个员工
void CreatePerson(vector<person>& vlist){

    string seed = "ABCDE";
    for (int i = 0; i < 5; i++){
        person p;
        p.name = "员工";
        p.name += seed[i];
        p.age = rand() % 30 + 20;
        p.salary = rand() % 20000 + 10000;
        p.tele = "010-8888888";
        vlist.push_back(p);
    }

}

//5名员工分配到不同的部门
void PersonByGroup(vector<person>& vlist, multimap<int, person>& plist){


    int operate = -1; //用户的操作

    for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){

        cout << "当前员工信息:" << endl;
        cout << "姓名：" << it->name << " 年龄:" << it->age << " 工资:" << it->salary << " 电话：" << it->tele << endl;
        cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
        scanf("%d", &operate);

        while (true){

            if (operate == SALE_DEPATMENT){  //将该员工加入到销售部门
                plist.insert(make_pair(SALE_DEPATMENT, *it));
                break;
            }
            else if (operate == DEVELOP_DEPATMENT){
                plist.insert(make_pair(DEVELOP_DEPATMENT, *it));
                break;
            }
            else if (operate == FINACIAL_DEPATMENT){
                plist.insert(make_pair(FINACIAL_DEPATMENT, *it));
                break;
            }
            else{
                cout << "您的输入有误，请重新输入(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
                scanf("%d", &operate);
            }

        }

    }
    cout << "员工部门分配完毕!" << endl;
    cout << "***********************************************************" << endl;

}

//打印员工信息
void printList(multimap<int, person>& plist, int myoperate){

    if (myoperate == ALL_DEPATMENT){
        for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){
            cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;
        }
        return;
    }

    multimap<int, person>::iterator it = plist.find(myoperate);
    int depatCount = plist.count(myoperate);
    int num = 0;
    if (it != plist.end()){
        while (it != plist.end() && num < depatCount){
            cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;
            it++;
            num++;
        }
    }
}

//根据用户操作显示不同部门的人员列表
void ShowPersonList(multimap<int, person>& plist, int myoperate){

    switch (myoperate)
    {
    case SALE_DEPATMENT:
        printList(plist, SALE_DEPATMENT);
        break;
    case DEVELOP_DEPATMENT:
        printList(plist, DEVELOP_DEPATMENT);
        break;
    case FINACIAL_DEPATMENT:
        printList(plist, FINACIAL_DEPATMENT);
        break;
    case ALL_DEPATMENT:
        printList(plist, ALL_DEPATMENT);
        break;
    }
}

//用户操作菜单
void PersonMenue(multimap<int, person>& plist){

    int flag = -1;
    int isexit = 0;
    while (true){
        cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4 所有部门, 0退出)：" << endl;
        scanf("%d", &flag);

        switch (flag)
        {
        case SALE_DEPATMENT:
            ShowPersonList(plist, SALE_DEPATMENT);
            break;
        case DEVELOP_DEPATMENT:
            ShowPersonList(plist, DEVELOP_DEPATMENT);
            break;
        case FINACIAL_DEPATMENT:
            ShowPersonList(plist, FINACIAL_DEPATMENT);
            break;
        case ALL_DEPATMENT:
            ShowPersonList(plist, ALL_DEPATMENT);
            break;
        case 0:
            isexit = 1;
            break;
        default:
            cout << "您的输入有误，请重新输入!" << endl;
            break;
        }

        if (isexit == 1){
            break;
        }
    }

}

int main(void){

    vector<person>  vlist; //创建的5个员工 未分组
    multimap<int, person> plist; //保存分组后员工信息

    //创建5个员工
    CreatePerson(vlist);
    //5名员工分配到不同的部门
    PersonByGroup(vlist, plist);
    //根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表
    PersonMenue(plist);

    system("pause");
    return EXIT_SUCCESS;
}

面试题

海量数据查重

对于海量数据的查重需要记录重复次数，必须使用映射表类型的容器，可以利用单重映射表容器进行存储，有序无序都无所谓

海量数据查重

#include <cstdlib>
#include <iostream>
#include <unordered_map>
using namespace std;

int main(int argc, char *argv[]) {
    // 1.构造海量数据
    const int LENGTH = 100000;
    int arr[LENGTH] = {0};
    for (int i = 0; i < LENGTH; ++i) {
        arr[i] = rand() % 100 + 1;
    }

    // 2.进行查重操作
    unordered_map<int, int> m;

    for (auto item: arr) {
        /*
        // 第一种添加的方式
        auto ret = m.find(item);
        if (ret != m.end()) {
            ret->second++;
        } else {
            m.insert({item, 1});
        }
        */

        // 第二种添加的方式
        m[item]++;

        /*
          之所以第二种方式可以达到同样的效果还是因为map中对于operator[]的重载机制导致
          当使用m[item]的时间会先查询有没有key为item的键值对，如果有就返回值的引用
          如果没有，就会新建一个key为item 值为值类型的默认值 的键值对，对于此例中就是
          [item, int()] int()会被编译成0 --> [item, 1]
         */
    }

    for (auto i: m) {
        if (i.second > 1) {
            cout << i.first << ":" << i.second << endl;
        }
    }

    return 0;
}

海量数据去重

海量数据去重

#include <cstdlib>
#include <iostream>
#include <unordered_set>
using namespace std;

int main(int argc, char *argv[]) {
    // 1.构造海量数据
    const int LENGTH = 100000;
    int arr[LENGTH] = {0};
    for (int i = 0; i < LENGTH; ++i) {
        arr[i] = rand() % 100 + 1;
    }

    // 2.进行去重操作
    unordered_set<int> s;

    for (auto item: arr) {
        /*
        auto ret = m.find(item);
        if (ret != m.end()) {
            ret->second++;
        } else {
            m.insert({item, 1});
        }
        */
        s.insert(item);
    }

    for (auto i: s) {
        cout << i << endl;
    }

    return 0;
}

map为什么用红黑树实现？有什么好处？

C++ map 使用红黑树实现，主要因其在插入/删除性能、有序性支持和稳定性之间取得了最佳平衡。红黑树的弱平衡特性减少了旋转次数，适合频繁修改的场景；其有序遍历能力满足 map 的排序需求，而哈希表虽查询更快但无法保证顺序。相较 AVL 树，红黑树实现更简单且内存占用更低，是工程实践中的优选。

Details

C++ STL 中的 map 使用红黑树（Red-Black Tree）作为底层实现，而非哈希表（如 unordered_map）或严格平衡的 AVL 树，主要基于以下原因和优势：

---

一、红黑树的特性与优势

1. 平衡性与性能的折中
   • 红黑树是一种弱平衡二叉搜索树，通过颜色标记和旋转规则（如根节点为黑、红色节点子节点必为黑等）保证树的高度平衡。虽然不如 AVL 树严格平衡（AVL 树要求左右子树高度差 ≤1），但红黑树的插入和删除操作所需的旋转次数更少，综合性能更优。
   • 例如，红黑树插入最多需 2 次旋转，删除最多 3 次，而 AVL 树可能需要多次调整平衡因子。

2. 稳定的时间复杂度
   • 红黑树的查找、插入、删除操作的时间复杂度均为 O(log n)，且最坏情况下仍保持这一复杂度。相比之下，哈希表虽然平均时间复杂度为 O(1)，但可能因哈希冲突退化为 O(n)。

3. 内存效率与实现复杂度
   • 红黑树仅需为每个节点存储颜色标记和指针，而 AVL 树需额外记录平衡因子，哈希表则需要维护哈希桶和链表/开放寻址结构，内存占用更高。 • 红黑树的实现复杂度低于 AVL 树，适合工程实践。

---

二、对比其他数据结构的劣势

1. 与哈希表对比
   • 有序性需求：map 要求元素按键排序（如升序），而哈希表（unordered_map）是无序的。红黑树天然支持有序遍历和范围查询（如 lower_bound()）。
   • 哈希冲突问题：哈希表的性能依赖于哈希函数设计，冲突可能导致链表过长或频繁扩容，而红黑树无需考虑此类问题。

2. 与 AVL 树对比
   • 插入/删除性能：AVL 树为严格平衡，插入/删除后需频繁调整平衡因子，导致旋转次数更多；红黑树允许局部不平衡，减少了调整频率。
   • 适用场景：若应用场景以查找为主（如数据库索引），AVL 树更优；但 map 作为通用容器需平衡增删查操作，红黑树更合适。

---

三、红黑树在 map 中的具体优势

1. 支持有序操作
   • 红黑树的中序遍历可直接输出有序键值对，适用于需要排序的场景（如排行榜、字典）。

2. 动态数据的高效管理
   • 在频繁插入/删除的场景中（如实时更新缓存），红黑树的旋转成本低于 AVL 树，且无需哈希表的扩容开销。

3. 稳定性与泛用性
   • 红黑树的稳定 O(log n) 性能使其适合大规模数据，而哈希表在数据量激增时可能因扩容或冲突导致性能波动。