前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >map 学习(上)——C++中 map 的使用

map 学习(上)——C++中 map 的使用

作者头像
剑影啸清寒
发布2018-01-02 13:35:38
3.1K0
发布2018-01-02 13:35:38
举报
文章被收录于专栏:琦小虾的Binary

map 学习(上)——C++中 map 的使用

欠下数据结构的债,迟早是要还的…… 最近写毕业论文过程中,需要用到哈希表的数据结构,此外空闲时间在刷 Leetcode 过程中,发现好多高效算法都是用 unordered_map 实现的,看来学习 map 相关内容是躲不了的了,开始学习 map 的相关内容。 本篇先学习 C++ 中 STL 标准库中 map 的使用方法。

以下内容翻译自:《map - C++ Reference》

一、原型

代码语言:javascript
复制
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

二、说明

map 是一种容器,用来存储若干元素,这些元素都是由关键值 (Key Value,以下称为 Key 值) 和映射值 (Mapped Value,以下依旧称为映射值) 配对组成的,具体说明如下: 在一个 map 中, Key 值通常用来排序或特指元素,映射值用来存储与该 Key 值绑定的内容。 Key 值与映射值的数据类型可以不同,而且可以一起被放进成员类型 value_type 中,value_type 是一种配对类型,定义如下:

代码语言:javascript
复制
typedef pair<const Key, T> value_type;

在 map 内部的元素通常按照其 Key 值排序,且排序方式是根据某种明确、严格的弱排序标准进行的,这种排序标准是由 map 内部的比较对象(即 map::key_comp)指定的。 map 容器通过 Key 值访问特定元素的速度,相较于 unordered_map 容器通常较慢,但 map 容器允许基于它们的顺序对子集进行直接迭代。 map 中的映射值可以使用括号运算符 (operator[]) 通过其关联的 Key 值直接访问。 map 通常使用二叉搜索树实现。

三、map 容器属性

  • 关联性:
    • 关联容器中的元素的参考地址指的是其 Key 值,而不是他们在容器中的绝对地址;
  • 有序性:
    • 容器中的元素一直按照排序方式严格排序,所有插入元素都按照该顺序排列;
  • 映射:
    • 每个元素中,一个 Key 值与一个映射值相关。Key 值是用来标识其主要内容是映射值的元素;
  • 唯一 Key 值:
    • 容器中不存在同时拥有相同 Key 值的两个元素;
  • 分配感知 (Allocator-aware):
    • map 容器使用分配器对象动态处理其存储需求。

四、模板参数

  • Key
    • Key 值的类型。在 map 中的每个元素都是由其 Key 值唯一指定的。
    • 别名为成员类型 map::key_type
  • T
    • 映射值的类型。在 map 中的每个元素,都存储了一些数据作为其映射值。
    • 别名为成员类型 map::mapped_type
  • Compare
    • 一个二元值,它将两个元素的 Key 值作为输入参数,并返回一个布尔值。表达式 comp(a, b),其中 comp 是该类型的对象,a, b是 Key 值,如果按照函数定义的严格弱排序,参数 a 被认为排在参数 b 之前,则返回 true。
    • map 对象使用该表达式确定元素在容器中的位置,并判断两个元素的 Key 值是否相等(通过自反比较:如果 (!comp(a,b) && !comp(b,a) ) 结果为真,则 a, b 等价)。map 容器中没有两个元素拥有相同的 Key 值。
    • Compare 可以使一个函数指针,或者函数对象(详细请参阅示例构造函数)。默认值小于<T>,返回应用小于运算符 (a < b) 相同的值;
    • 别名为成员类型 map::key_compare
  • Alloc
    • 用于定义存储分配模型的分配器对象的类型。默认情况下使用分配器类模板,它定义了最简单的模型分配模型,而且与值无关。
    • 别名为成员类型 map::allocator_type

五、常用函数

  • 构造函数
    • 在后续的程序示例中展示了五种不同的构造函数;
  • clear
    • 清除 map 中所有元素;
  • erase
    • 删除 map 中指定位置的元素;
  • insert
    • 在 map 指定位置添加 pair 类型的元素;
  • find
    • 获取 map 中元素的迭代器;
  • begin, end
    • map 的正向迭代器的起始位置与终点位置;
  • rbegin, rend
    • map 的反向迭代器的起始位置与终点位置;

六、程序示例

以下源码摘自《C++STL之map学习》,笔者对其进行注释。

代码语言:javascript
复制
#include <iostream>
#include <map>

using namespace std;

// 比较函数(用于后面的函数指针定义)
bool fncomp(char lhs, char rhs){
    return lhs < rhs;
}

// 定义一个 Compare 对象,且内部对运算符 () 进行重载
struct classcomp{
    bool operator() (const char& lhs, const char& rhs){
        return lhs < rhs;
    }
};

int main(int argc, char* argv[])
{
    //=========================
    //  map 的多种构造函数
    //=========================

    // 1. 直接定义
    map<char,int> mymap;
    mymap['a'] = 10;
    mymap['b'] = 60;
    mymap['c'] = 30;
    mymap['d'] = 90;
    mymap['e'] = 50;

    // 2. 复制
    map<char, int> second(mymap);

    // 3. 通过迭代器
    map<char, int> third(mymap.begin(),mymap.end());

    // 4. 重新定义 Compare 对象,该对象内部对运算符 () 进行重载
    map<char, int, classcomp> fourth;

    // 5. 通过函数指针
    bool(*fn_pt)(char, char) = fncomp;
    map<char, int, bool(*)(char, char)> fifth(fn_pt);

    //=========================
    //  以最初定义的mymap 为例,讲解 map 的使用
    //=========================
    map<char,int>::key_compare key_comp;
    map<char,int>::iterator it;
    it = mymap.begin();


    //=========================
    //  1. 输出所有 Pair 元素
    //=========================
    // 迭代器遍历 map
    for (it; it != mymap.end(); it++)
    {
        // map的迭代器,可以用 first 访问std::pair的第一个成员(Type1),second 访问第二个成员 (Type2)
        cout<<it->first<<":"<<it->second<<endl;
    }
    cout<<"================================="<<endl;

    //=========================
    //  2. 修改映射值
    //=========================
    second.clear();
    second['a']=1002;
    second['b']=10023;
    while (!second.empty())
    {
        cout << second.begin()->first << " => ";
        cout << second.begin()->second << endl;
        second.erase(second.begin());
    }
    cout<<"================================="<<endl;

    //=========================
    //  3. 插入
    //=========================
    mymap.insert(pair<char,int>('f',100) );
    mymap.insert(pair<char,int>('g',200) );
    cout<<"f => " <<mymap.find('f')->second<<endl;
    cout<<"g => " <<mymap.find('g')->second<<endl;

    cout<<"================================="<<endl;

    //=========================
    //  4. Compare 参数的使用
    //=========================
    key_comp = mymap.key_comp();
    cout << "mymap contains:\n";

    // 迭代器反向遍历的起始位置
    char highest = mymap.rbegin()->first;     // key value of last element
    it = mymap.begin();
    do {
        cout << (*it).first << " => " << (*it).second << endl;
    } while ( key_comp((*it++).first, highest) );

    cout << endl;
    return 0;
}

运行结果如下:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • map 学习(上)——C++中 map 的使用
  • 一、原型
  • 二、说明
  • 三、map 容器属性
  • 四、模板参数
  • 五、常用函数
  • 六、程序示例
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档