【C++】STL 容器 - map 关联容器 ① ( std::map 容器简介 | std::map 容器排序规则

文章目录

一、std::map 容器
- 1、std::map 容器简介
- 2、std::map 容器排序规则
- 3、std::map 容器底层实现
二、代码示例 - std::map 容器
- 1、代码示例
- 2、执行结果

一、std::map 容器

1、std::map 容器简介

std::map 容器是 C 语言标准模板库 ( STL , Standard Template Library ) 提供的的一个 " 关联容器 " ;

std::map 关联容器 , 提供一对一数据处理能力 , 容器中的元素自动按键 Key 排序 , 键 Key 和值 Value 是一一对应的 ;

第一个键 Key 可以称为关键字 , 每个关键字只能在 map 中出现一次 ;
第二个是关键字的值 Value ;

std::map 容器中存储的是键值对 key-value 数据 , 容器中的元素是键 Key 对元素进行自动排序的 ;

每个键的值在 std::map 容器中都是唯一的 , 键值不允许重复 ;

在 std::map 容器中 , 可以根据键 Key 快速检索容器中的对应值 Value ;

std::map 容器的大小是动态调整的 , 在运行时增加 / 删除键值对元素 , 其大小也随之变化 ;

使用 map 集合之前 , 需要导入 <map> 头文件 ;

代码语言：javascript复制

#include "map"

2、std::map 容器排序规则

std::map 容器中 , 排序规则如下 :

默认排序规则 : 默认的排序规则是 less 仿函数规则 , 即按照键的升序进行排列 ;
less 仿函数运算 : 在该仿函数中核心操作就是调用元素的 < 运算符 , 如果该元素类型没有重载 < 运算符 , 则会报错 ;
自定义排序规则 : 如果想要自己设置排序规则 , 则自定义仿函数 / 函数对象即可 ;

map 容器必须制定排序规则 , 默认就是 less 排序规则 , 使用该规则的前提是元素类型可以使用 < 操作符进行运算 , 如果不能进行 < 运算 , 则必须传入一个排序规则 ;

3、std::map 容器底层实现

std::map 容器底层使用红黑树实现 , 这是平衡二叉树的变体数据结构 ;

std::map 容器与 std::set 容器底层实现相同 , 区别是 map 容器中存储的是键值对 , set 容器中存储的事单个元素值 ;

使用红黑树实现的 std::map 容器和 std::set 容器 , 其插入 / 删除操作比线性表性能要高 ;

线性表的插入 / 删除操作 , 时间复杂度是 O(n) ;
红黑树的插入 / 删除操作 , 时间复杂度是 O(log n) ;

二、代码示例 - std::map 容器

1、代码示例

代码语言：javascript复制

#include "iostream"
using namespace std;
#include "map"
#include "string"


int main() {

    // 创建一个空的 map 容器，键为 string 类型，值为 int 类型
    map<string, int> myMap;   

    myMap["Tom"] = 18;                // 插入键值对 ("Tom", 18)  
    myMap["Jerry"] = 12;              // 插入键值对 ("Jerry", 12)  
    myMap["Trump"] = 80;              // 插入键值对 ("Trump", 80)  

    // 遍历 map 中的所有元素  
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;  
    }


	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

2、执行结果

执行结果 :

Jerry: 12 Tom: 18 Trump: 80 请按任意键继续. . .

容器 map std stl 排序

0 人点赞

【C++】STL 容器 - map 关联容器 ① ( std::map 容器简介 | std::map 容器排序规则 | std::map 容器底层实现 )