观察者模式 express d3 cakephp junit ansible angular material cuda Material UI vue中文 河南普通话考试报名 c语言求和 linux下载器 css面试题 配置tomcat环境变量 dwf文件怎么转成dwg idea批量替换快捷键 oracle存储过程返回值 mysql时间戳转换日期 java初级 java开发学习 java正则替换 java抽象方法 java正则匹配数字 js添加元素 oem修改器 计价软件 生存猎人属性 红巨人插件 ps从入门到精通 微信小程序开发实例 批量插入数据 mac修改器 g4560配什么显卡 ae蒙版和遮罩 pr脱机文件怎么恢复 三菱plc序列号 ansys安装 声如银铃 excel箱线图
当前位置: 首页 > 学习教程  > 编程语言

c++11:std::map与std::unordered_map(hash map)的区别

2021/1/13 19:23:56 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

目录 1、std::map 2、std::unordered_map 本质区别在于std::map底层使用红黑树&#xff0c;而std::unordered_map使用的是hash map。 1、std::map 头文件&#xff1a;<map> 类声明&#xff1a; template<class Key,class T,class Compare std::less<Key>…

目录

1、std::map

2、std::unordered_map


本质区别在于std::map底层使用红黑树,而std::unordered_map使用的是hash map。

1、std::map

头文件:<map>

类声明:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

namespace pmr { //c++17起
    template <class Key, class T, class Compare = std::less<Key>>
    using map = std::map<Key, T, Compare,
                         std::pmr::polymorphic_allocator<std::pair<const Key,T>>>
}

std::map 是有序键值对容器,它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树

在每个标准库使用比较 (Compare) 概念的位置,以等价关系检验唯一性。不精确而言,若二个对象 a 与 b 互相比较不小于对方 : !comp(a, b) && !comp(b, a) ,则认为它们等价(非唯一)。

std::map 满足容器 (Container) 、知分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

成员函数

(构造函数)构造 map
(公开成员函数)

(析构函数)

析构 map
(公开成员函数)

operator=

赋值给容器
(公开成员函数)

get_allocator

返回相关的分配器
(公开成员函数)

元素访问

at

(C++11)

访问指定的元素,同时进行越界检查
(公开成员函数)

operator[]

访问或插入指定的元素
(公开成员函数)

迭代器

begincbegin

(C++11)

返回指向起始的迭代器
(公开成员函数)

endcend

(C++11)

返回指向末尾的迭代器
(公开成员函数)

rbegincrebegin

(C++11)

返回指向起始的逆向迭代器
(公开成员函数)

rendcrend

(C++11)

返回指向末尾的逆向迭代器
(公开成员函数)

容量

empty

检查容器是否为空
(公开成员函数)

size

返回容纳的元素数
(公开成员函数)

max_size

返回可容纳的最大元素数
(公开成员函数)

修改器

clear

清除内容
(公开成员函数)

insert

插入元素或结点 (C++17 起)
(公开成员函数)

insert_or_assign

(C++17)

插入元素,或若键已存在则赋值给当前元素
(公开成员函数)

emplace

(C++11)

原位构造元素
(公开成员函数)

emplace_hint

(C++11)

使用提示原位构造元素
(公开成员函数)

try_emplace

(C++17)

若键不存在则原位插入,若键存在则不做任何事
(公开成员函数)

erase

擦除元素
(公开成员函数)

swap

交换内容
(公开成员函数)

extract

(C++17)

从另一容器释出结点
(公开成员函数)

merge

(C++17)

从另一容器接合结点
(公开成员函数)

查找

count

返回匹配特定键的元素数量
(公开成员函数)

find

寻找带有特定键的元素
(公开成员函数)

contains

(C++20)

检查容器是否含有带特定键的元素
(公开成员函数)

equal_range

返回匹配特定键的元素范围
(公开成员函数)

lower_bound

返回指向首个不小于给定键的元素的迭代器
(公开成员函数)

upper_bound

返回指向首个大于给定键的元素的迭代器
(公开成员函数)

观察器

key_comp

返回用于比较键的函数
(公开成员函数)

value_comp

返回用于在value_type类型的对象中比较键的函数。
(公开成员函数)

2、std::unordered_map

头文件: <unordered_map>

类声明

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

namespace pmr { //c++17起
    template <class Key,
              class T,
              class Hash = std::hash<Key>,
              class KeyEqual = std::equal_to<Key>>
              using unordered_map = std::unordered_map<Key, T, Hash, Pred,
                              std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}

unordered_map 是关联容器,含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序,而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问,因为一旦计算哈希,则它准确指代元素所放进的桶。

std::unordered_map 满足容器 (Container) 、知分配器容器 (AllocatorAwareContainer) 、无序关联容器 (UnorderedAssociativeContainer) 的要求。

成员函数

(构造函数)

构造 unordered_map
(公开成员函数)

(析构函数)

析构 unordered_map
(公开成员函数)

operator=

赋值给容器
(公开成员函数)

get_allocator

返回相关的分配器
(公开成员函数)

迭代器

begincbegin

返回指向起始的迭代器
(公开成员函数)

endcend

返回指向末尾的迭代器
(公开成员函数)

容量

empty

检查容器是否为空
(公开成员函数)

size

返回容纳的元素数
(公开成员函数)

max_size

返回可容纳的最大元素数
(公开成员函数)

修改器

clear

清除内容
(公开成员函数)

insert

插入元素或结点 (C++17 起)
(公开成员函数)

insert_or_assign

(C++17)

插入元素,或若键已存在则赋值给当前元素
(公开成员函数)

emplace

原位构造元素
(公开成员函数)

emplace_hint

使用提示原位构造元素
(公开成员函数)

try_emplace

(C++17)

若键不存在则原位插入,若键存在则不做任何事
(公开成员函数)

erase

擦除元素
(公开成员函数)

swap

交换内容
(公开成员函数)

extract

(C++17)

从另一容器释出结点
(公开成员函数)

merge

(C++17)

从另一容器接合结点
(公开成员函数)

查找

at

访问指定的元素,同时进行越界检查
(公开成员函数)

operator[]

访问或插入指定的元素
(公开成员函数)

count

返回匹配特定键的元素数量
(公开成员函数)

find

寻找带有特定键的元素
(公开成员函数)

contains

(C++20)

检查容器是否含有带特定键的元素
(公开成员函数)

equal_range

返回匹配特定键的元素范围
(公开成员函数)

桶接口

begin(size_type)

cbegin(size_type)

返回一个迭代器,指向指定的桶的开始
(公开成员函数)

end(size_type)

cend(size_type)

返回一个迭代器,指向指定的桶的末尾
(公开成员函数)

bucket_count

返回桶数
(公开成员函数)

max_bucket_count

返回桶的最大数量
(公开成员函数)

bucket_size

返回在特定的桶中的元素数量
(公开成员函数)

bucket

返回带有特定键的桶
(公开成员函数)

哈希策略

load_factor

返回每个桶的平均元素数量
(公开成员函数)
max_load_factor管理每个桶的平均元素数量的最大值
(公开成员函数)

rehash

至少为指定数量的桶预留存储空间。
这会重新生成哈希表。
(公开成员函数)

reserve

为至少为指定数量的元素预留存储空间。
这会重新生成哈希表。
(公开成员函数)

观察器

hash_function

返回用于对关键哈希的函数
(公开成员函数)

key_eql

返回用于比较键的相等性的函数
(公开成员函数)
/*================================================================
 *   Copyright (C) 2021 baichao All rights reserved.
 *
 *   文件名称:unordered_map.cpp
 *   创 建 者:baichao
 *   创建日期:2021年01月13日
 *   描    述:
 *
 ================================================================*/

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    // 创建三个 string 的 unordered_map (映射到 string )
    std::unordered_map<std::string, std::string> u = {
        {"RED","#FF0000"},
        {"GREEN","#00FF00"},
        {"BLUE","#0000FF"}
    };

    // 迭代并打印 unordered_map 的关键和值
    for( const auto& n : u ) {
        std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    }

    // 添加新入口到 unordered_map
    u["BLACK"] = "#000000";
    u["WHITE"] = "#FFFFFF";

    // 用关键输出值
    std::cout << "The HEX of color RED is:[" << u["RED"] << "]\n";
    std::cout << "The HEX of color BLACK is:[" << u["BLACK"] << "]\n";

    //返回哈希函数
    std::hash<std::string> hashFunc = u.hash_function(); //因为unordered_map实例u中的key是std::string类型,所以函数返回值也就是std::hash<std:;string>


    return 0;
}


本文链接: http://www.dtmao.cc/news_show_600053.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?