菜鸟笔记
提升您的技术认知

c 中的map问题 unordered-ag真人游戏

4.map问题 unordered_map问题

4.1 map

        map是stl的一个关联容器,它提供一对一的hash。第一个可以称为关键字(key),每个关键字只能在map中出现一次;第二个可能称为该关键字的值(value)。map以模板(泛型)方式实现,可以存储任意类型的数据,包括使用者自定义的数据类型。map主要用于资料一对一映射(one-to-one)的情況,map內部的实现自建一颗红黑树,这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的。

4.1.1 map的使用

  • 使用map得包含map类所在的头文件:#include
  • map对象是模板类,需要关键字和存储对象两个模板参数:std:map<int, string> personnel;这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
  • 为了使用方便,可以对模板类进行一下类型定义,typedef map<int,cstring> udt_map_int_cstring;udt_map_int_cstring enummap;

4.1.2 构造map

我们通常用如下方法构造一个map:map mapstudent;

4.1.3 往map中插入元素

    map mapstudent;
    //插入第一种 用insert函數插入pair
    mapstudent.insert(pair(000, "zhangsan"));
    //插入第二种 用insert函数插入value_type数据
    mapstudent.insert(map::value_type(001, "lisi"));
    // 插入第三种 用"array"方式插入
    mapstudent[002] = "wangwu";
    mapstudent[003] = "liuqi";

        以上三种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的 插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是不能在插入数据的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值。

        我们怎么知道insert语句是否插入成功的问题了,可以用pair来获得是否插入成功,程序如下:

// 构造定义,返回一个pair对象
pair insert (const value_type& val);
 
pair::iterator, bool> insert_pair;
 
insert_pair = mapstudent.insert(map::value_type (001, "student_one"));
 
if(!insert_pair.second)
    cout << ""error insert new element" << endl;

        我们通过pair的第二个变量来知道是否插入成功,它的第一个变量返回的是一个map的迭代器,如果插入成功的话insert_pair.second应该是true的,否则为false。

4.1.4 在map中查找元素

        当所查找的关键key出现时,它返回数据所在对象的位置,如果沒有,返回iter与end函数的值相同。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
iter = mapstudent.find("123");
 
if(iter != mapstudent.end())
       cout<<"find, the value is"<second<

4.1.5 删除与清空map中元素

//迭代器刪除
iter = mapstudent.find("123");
mapstudent.erase(iter);
 
//用关键字刪除
int n = mapstudent.erase("123"); //如果刪除了會返回1,否則返回0
 
//用迭代器范围刪除 : 把整个map清空
mapstudent.erase(mapstudent.begin(), mapstudent.end());
//等同于mapstudent.clear()

4.1.6 查看map大小

        在往map里面插入了数据,我们怎么知道当前已经插入了多少数据呢,可以用size函数,用法如下:

int nsize = mapstudent.size();

4.1.7 map的基础操作函数总结

        c  maps是一种关联式容器,包含“关键字/值”对

  •      begin()         返回指向map头部的迭代器
  •      clear()        删除所有元素
  •      count()         返回指定元素出现的次数
  •      empty()         如果map为空则返回true
  •      end()           返回指向map末尾的迭代器
  •      equal_range()   返回特殊条目的迭代器对
  •      erase()         删除一个元素
  •      find()          查找一个元素
  •      get_allocator() 返回map的配置器
  •      insert()        插入元素
  •      key_comp()      返回比较元素key的函数
  •      lower_bound()   返回键值>=给定元素的第一个位置
  •      max_size()      返回可以容纳的最大元素个数
  •      rbegin()        返回一个指向map尾部的逆向迭代器
  •      rend()          返回一个指向map头部的逆向迭代器
  •      size()          返回map中元素的个数
  •      swap()           交换两个map
  •      upper_bound()    返回键值>给定元素的第一个位置
  •      value_comp()     返回比较元素value的函数

4.2 unordered_map

        hash_map ≈ unordered_map,最初的 c 标准库中没有类似 hash_map 的实现,但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的,所以它们在功能和性能保证方面都有细微差别。从 c 11 开始,hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突,决定使用替代名称 unordered_map。这个名字其实更具描述性,因为它暗示了该类元素的无序性。

4.2.1 创建unordered_map容器

头文件:

#include 

(1)默认构造函数,可以创建空的 unordered_map 容器

std::unordered_map umap;

(2)在创建 unordered_map 容器的同时,可以完成初始化操作

std::unordered_map umap{
    {"python教程","http://c.biancheng.net/python/"},
    {"java教程","http://c.biancheng.net/java/"},
    {"linux教程","http://c.biancheng.net/linux/"} };

(3)可以调用 unordered_map 模板中提供的复制(拷贝)构造函数,将现有 unordered_map 容器中存储的键值对,复制给新建 unordered_map 容器

std::unordered_map umap2(umap);

(4)c 11 标准中还向 unordered_map 模板类增加了移动构造函数,即以右值引用的方式将临时 unordered_map 容器中存储的所有键值对,全部复制给新建容器。

//返回临时 unordered_map 容器的函数
std::unordered_map  retumap(){
    std::unordered_maptempumap{
        {"python教程","http://c.biancheng.net/python/"},
        {"java教程","http://c.biancheng.net/java/"},
        {"linux教程","http://c.biancheng.net/linux/"} };
    return tempumap;
}
//调用移动构造函数,创建 umap2 容器
std::unordered_map umap2(retumap());

4.2.2 unordered_map容器的成员方法

        unordered_map 既可以看做是关联式容器,更属于自成一脉的无序容器。因此在该容器模板类中,既包含一些在学习关联式容器时常见的成员方法,还有一些属于无序容器特有的成员方法。

成员方法 功能
begin() 返回指向容器中第一个键值对的正向迭代器。
end()  返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。
empty() 若容器为空,则返回 true;否则 false。
size() 返回当前容器中存有键值对的个数。
max_size() 返回容器所能容纳键值对的最大个数,不同的操作系统,其返回值亦不相同。
operator[key] 该模板类中重载了 [] 运算符,其功能是可以向访问数组中元素那样,只要给定某个键值对的键 key,就可以获取该键对应的值。注意,如果当前容器中没有以 key 为键的键值对,则其会使用该键向当前容器中插入一个新键值对。
at(key) 返回容器中存储的键 key 对应的值,如果 key 不存在,则会抛出 out_of_range 异常。 
find(key) 查找以 key 为键的键值对,如果找到,则返回一个指向该键值对的正向迭代器;反之,则返回一个指向容器中最后一个键值对之后位置的迭代器(如果 end() 方法返回的迭代器)。
count(key) 在容器中查找以 key 键的键值对的个数。
equal_range(key) 返回一个 pair 对象,其包含 2 个迭代器,用于表明当前容器中键为 key 的键值对所在的范围。
emplace() 向容器中添加新键值对,效率比 insert() 方法高。
emplace_hint() 向容器中添加新键值对,效率比 insert() 方法高。
insert()  向容器中添加新键值对。
erase() 删除指定键值对。
clear()  清空容器,即删除容器中存储的所有键值对。
swap() 交换 2 个 unordered_map 容器存储的键值对,前提是必须保证这 2 个容器的类型完全相等。
bucket_count() 返回当前容器底层存储键值对时,使用桶(一个线性链表代表一个桶)的数量。
max_bucket_count() 返回当前系统中,unordered_map 容器底层最多可以使用多少桶。
bucket_size(n) 返回第 n 个桶中存储键值对的数量。
bucket(key) 返回以 key 为键的键值对所在桶的编号。
load_factor() 返回 unordered_map 容器中当前的负载因子。负载因子,指的是的当前容器中存储键值对的数量(size())和使用桶数(bucket_count())的比值,即 load_factor() = size() / bucket_count()。
max_load_factor() 返回或者设置当前 unordered_map 容器的负载因子。
rehash(n) 将当前容器底层使用桶的数量设置为 n。
reserve() 将存储桶的数量(也就是 bucket_count() 方法的返回值)设置为至少容纳count个元(不超过最大负载因子)所需的数量,并重新整理容器。
hash_function() 返回当前容器使用的哈希函数对象。

4.2.3 unordered_map实例演示代码

#include 
#include 
#include 
using namespace std;
int main()
{
    //创建空 umap 容器
    unordered_map umap;
    //向 umap 容器添加新键值对
    umap.emplace("python教程", "http://c.biancheng.net/python/");
    umap.emplace("java教程", "http://c.biancheng.net/java/");
    umap.emplace("linux教程", "http://c.biancheng.net/linux/");
    //输出 umap 存储键值对的数量
    cout << "umap size = " << umap.size() << endl;
    //使用迭代器输出 umap 容器存储的所有键值对
    for (auto iter = umap.begin(); iter != umap.end();   iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}
/*
执行结果:
umap size = 3
python教程 http://c.biancheng.net/python/
linux教程 http://c.biancheng.net/linux/
java教程 http://c.biancheng.net/java/
*/

4.2.4 unordered_map遍历

    for (const auto &[k, v] : map)
    {
        cout << k << "===" << v << endl;
    }
//使用迭代器(使用auto)
    for (auto iter = map.begin(); iter != map.end();   iter)
    {
        cout << iter->first << "===" << iter->second << endl;
    }
//迭代器(已知数据类型的情况下)
    unordered_map::iterator iter;
    for (iter = map.begin(); iter != map.end();   iter)
    {
        cout << iter->first << "===" << iter->second << endl;
    }

4.3 map和unordered_map对比

(1)需要引入的头文件不同

  • map: #include < map >
  • unordered_map: #include < unordered_map >

(2)内部实现机理不同
        map: map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而avl是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树(又名二叉查找树、二叉排序树,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到hash表中一个位置来访问记录,查找的时间复杂度可达到o(1),其在海量数据处理中有着广泛应用),因此,其元素的排列顺序是无序的。

(3)优缺点以及适用处

map:

  • 优点:有序性,这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作。内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高。
  • 缺点: 空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间。
  • 适用处:对于那些有顺序要求的问题,用map会更高效一些

unordered_map:

  • 优点: 因为内部实现了哈希表,因此其查找速度非常的快
  • 缺点: 哈希表的建立比较耗费时间
  • 适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map

总结:

  • 内存占有率的问题就转化成红黑树 vs hash表 , 还是unorder_map占用的内存要高。但是unordered_map执行效率要比map高很多
  • 对于unordered_map或unordered_set容器,其遍历顺序与创建该容器时输入的顺序不一定相同,因为遍历是按照哈希表从前往后依次遍历的
网站地图