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

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

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容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的