首页 > 其他分享 >set 、multiset、unordered_set 和 map 、multimap、unordered_map

set 、multiset、unordered_set 和 map 、multimap、unordered_map

时间:2024-11-11 20:50:13浏览次数:6  
标签:map set 元素 value 键值 key unordered

序列式容器:

比如:vector、list、deque、forward_list(C++11)等

因为其底层为线性序列的数据结构,里面存储的是元素本身。

关联式容器:

比如(树形结构的关联式容器):map、set、multimap、multiset等

也是用来存储数据的,与序列式容器不同的是,

其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高

unordered系列关联式容器:

unordered_map、unordered_set、unordered_multimap和unordered_multiset

这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同。

键值对:用来表示具有一一对应关系的一种结构,

该结构中一般只包含两个成员变量key和value,

key代表键值,value表示与key对应的信息。

比如:英文单词与其中文含义是一一对应的关系

一、set

1.介绍

1.set是按照一定次序存储元素的容器

2.在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。

set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。

3.在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行

排序。

4.set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对

子集进行直接迭代。

5.set在底层是用二叉搜索树(红黑树)实现的。

注意:

  1. 与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,

    但在底层实际存放的是由<value, value>构成的键值对。

  2. set中插入元素时,只需要插入value即可,不需要构造键值对。

  3. set中的元素不可以重复(因此可以使用set进行去重)。

  4. 使用set的迭代器遍历set中的元素,可以得到有序序列

  5. set中的元素默认按照小于来比较

  6. set中查找某个元素,时间复杂度为:logN

  7. set中的元素不允许修改

  8. set中的底层使用二叉搜索树(红黑树)来实现。

2.使用

参数列表

T: set中存放元素的类型,实际在底层存储<value, value>的键值对。

Compare:set中元素默认按照小于来比较

Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理

参数列表

构造

image-20241110185007772

迭代器

image-20241110185323809

image-20241110195204776

容量

image-20241110185509795

修改操作

image-20241110185552972

其他

image-20241110185616419

3.使用举例代码

void test_set1()
{
    set<int>s1;
    //排序+去重
    s1.insert(1);
    s1.insert(6);
    s1.insert(1);
    s1.insert(3);
    s1.insert(1);
    s1.insert(7);
    s1.insert(9);
​
    set<int>::iterator it = s1.begin();
    while (it != s1.end())
    {
        //*it=1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    //使用迭代器遍历
​
    vector<int> v = { 2,5,2,3,68,3,53,2,4 };
    set<int> s2(v.begin(), v.end());
    //拷贝
    for (auto e : s2)
    {
        cout << e << " ";
    }
    cout << endl;
    //使用范围for遍历
​
    set<int> s3= { 2,5,2,3,68,3,53,2,4 };
    for (auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
    //使用范围for遍历
​
    s3.erase(3);
    for (auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
    //范围for遍历后删除
​
    auto pos = s3.find(4);
    //查找 找不到返回end()
    if (pos != s3.end())
    {
        cout << *pos << endl;
        s3.erase(pos);
    }
    else
    {
        cout << "找不到" << endl;
    }
}

输出结果:

image-20241110190200382

void test_set2()
{
    std::set<int> myset;
    std::set<int>::iterator itlow, itup;
​
    for (int i = 1; i < 10; i++) 
        myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
​
    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;
​
    itlow = myset.lower_bound(30);                // X>=30     
    itup = myset.upper_bound(60);                 // X<70                 
​
    //[30,70)
    myset.erase(itlow, itup);                     // 10 20 70 80 90
​
    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;
}

输出结果:

image-20241110190546878

二、multiset

1.介绍

1.multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。

2.在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成

的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器

中进行修改(因为元素总是const的),但可以从容器中插入或删除。

3、在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则

进行排序。

4、multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭

代器遍历时会得到一个有序序列。

5.multiset底层结构为二叉搜索树(红黑树)。

注意:

  1. multiset中再底层中存储的是<value, value>的键值对

  2. mtltiset的插入接口中只需要插入即可

  3. 与set的区别是,multiset中的元素可以重复,set是中value是唯一的

  4. 使用迭代器对multiset中的元素进行遍历,可以得到有序的序列

  5. multiset中的元素不能修改

  6. 在multiset中找某个元素,时间复杂度为O(log N)

  7. multiset的作用:可以对元素进行排序

2.与set的区别

multiset的value可重复

set的value不可重复、是唯一的

3.使用举例代码

void test_multiset3()
{
    multiset<int>s1;
    //排序+可重复
    s1.insert(1);
    s1.insert(6);
    s1.insert(1);
    s1.insert(3);
    s1.insert(1);
    s1.insert(7);
    s1.insert(9);
​
    multiset<int>::iterator it = s1.begin();
    while (it != s1.end())
    {
        //*it=1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
​
    auto pos = s1.find(1);
    while (pos != s1.end() && *pos == 1)
    {
        cout << *pos << " ";
        ++pos;
    }
}

输出结果:

image-20241110191747884

三、unordered_set

1.介绍

与set的唯一区别:unordered_set是无序容器、set有序

2.使用

构造

image-20241110203043756

容器

image-20241110203123262

迭代器

image-20241110203140489

元素查找

image-20241110203236862

修改操作

image-20241110203257696

哈希、桶

image-20241110203347508

3.与set的区别

unordered_set无序

而set有序

void test_set1()
{
    set<int> s1 = { 3,4,5,2,6,8,9 };
    unordered_set<int> s = { 3, 1, 5, 6, 3, 7, 8, 9, 2, 4 };
    unordered_set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    for (auto e : s1)
    {
        cout << e << " ";
    }
    cout << endl;
}

输出结果:

image-20241110212050859

与set的效率对比

int test_set2()
{
    const size_t N = 1000000;
​
    unordered_set<int> us;
    set<int> s;
​
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; ++i)
    {
        //v.push_back(rand()); // N比较大时,重复值比较多
        //v.push_back(rand()+i); // 重复值相对少
        v.push_back(i); // 没有重复,有序
    }
​
    size_t begin1 = clock();
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;
​
    size_t begin2 = clock();
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;
​
    int m1 = 0;
    size_t begin3 = clock();
    for (auto e : v)
    {
        auto ret = s.find(e);
        if (ret != s.end())
        {
            ++m1;
        }
    }
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
​
    int m2 = 0;
    size_t begin4 = clock();
    for (auto e : v)
    {
        auto ret = us.find(e);
        if (ret != us.end())
        {
            ++m2;
        }
    }
    size_t end4 = clock();
    cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
​
    cout << "插入数据个数:" << s.size() << endl;
    cout << "插入数据个数:" << us.size() << endl << endl;
​
    size_t begin5 = clock();
    for (auto e : v)
    {
        s.erase(e);
    }
    size_t end5 = clock();
    cout << "set erase:" << end5 - begin5 << endl;
​
    size_t begin6 = clock();
    for (auto e : v)
    {
        us.erase(e);
    }
    size_t end6 = clock();
    cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
​
    return 0;
}

输出结果:

image-20241110212258764

四、map

1.介绍

  1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair : typedef pair<const key, T> value_type;
  3. 在内部,map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序。对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
  5. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。

注意:

  1. map中的的元素是键值对

  2. map中的key是唯一的,并且不能修改

  3. 默认按照小于的方式对key进行比较

  4. map中的元素如果用迭代器去遍历,可以得到一个有序的序列

  5. map的底层为平衡搜索树(红黑树),查找效率比较高O(log N)

  6. 支持[]操作符,operator[]中实际进行插入查找。

2.使用

参数列表

key: 键值对中key的类型

T: 键值对中value的类型

Compare: 比较器的类型,map中的元素是按照key来比较的,缺省情况下按照小于来比较,

一般情况下(内置类型元素)该参数不需要传递,

如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器

注意:在使用map时,需要包含头文件。

image-20241110194850630

构造

image-20241110195035463

image-20241110195112007

迭代器

image-20241110195234065

image-20241110195313246

容量

image-20241110195338634

访问

image-20241110195401542

修改操作

image-20241110195417799

其他

image-20241110195432100

3.使用举例代码

void test_map1()
{
    map<string, string>dict;
    pair<string, string >kv1("sort", "排序");
    dict.insert(kv1);
    dict.insert(pair<string, string >("left", "左边"));
    dict.insert(make_pair("right", "右边"));
​
    dict.insert(make_pair("right", "XXXX"));
    //不会更新
    
    //pair<string, string>kv2 = { "string","字符串" };
    dict.insert({ "string","字符串" });
​
    //map<string, string>::iterator it = dict.begin();
    auto it = dict.begin();
    while (it != dict.end())
    {
        //iterator  key不能修改 value可以修改
        // const_itreator 都不能修改
        //it->first += 'x';
        it->second += 'x';
​
​
        //cout << (*it).first << ":" << (*it).second << endl;
        cout << it->first << ":" << it->second << endl;
        //cout << it.operator->()->first << ":" << it.operator->()->second << endl;
        ++it;
    }
    cout << endl;
​
    for (auto& kv : dict)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
​
    /*for (auto& [x, y] : dict)
    {
        cout << x << ":" << y << endl;
    }*/
    //cout << endl;
​
    //map<string, string>dict2 = { {"sort", "排序"},{"left", "左边"},{"right", "右边"} };
}

输出结果:

image-20241110195746442

!!!operator[] !!!!

//V& operator[](const K& key)
//{
//  return (*((this->insert(make_pair(k, mapped_type)))).first)).second;
//}
//
//两者等价
//
//V& operator[](const K& key)
//{
//  //不管是插入成功还是失败,pair中iterator始终指向key所在的结点的迭代器
//  pair<iterator, bool> ret = this->insert(make_pair(key, V()));
//  iterator it = ret.first;
//  return it->second;
//}
​
//key 存在,插入失败,返回 ->pair<存在key值所在的迭代器,false>
//key 不存在,插入成功,返回 ->pair<新插入key值所在的迭代器,true>
void test_map3()
{
    map<string, string> dict;
    dict.insert({ "string","字符串" });
​
    //插入(一般不会这么用)
    dict["right"];
​
    //插入+修改
    dict["left"] = "左边";
​
    //查找
    cout << dict["string"] << endl;
​
    //修改
    dict["right"] = "右边";
​
    for (auto& s : dict)
    {
        cout << s.first << ":" << s.second << endl;
    }
​
    string str;
    cin >> str;
    if (dict.count(str))
    {
        if (dict.count(str))
        {
            cout << "在" << endl;
        }
        else
        {
            cout << "不在" << endl;
        }
    }
}

输出结果:

image-20241110200647260

五、multimap

1.介绍

  1. Multimaps是关联式容器,它按照特定的顺序,存储由key和value映射成的键值对<key, value>,其中多个键值对之间的key是可以重复的。
  2. 在multimap中,通常按照key排序和惟一地标识元素,而映射的value存储与key关联的内容。key和value的类型可能不同,通过multimap内部的成员类型value_type组合在一起,value_type是组合key和value的键值对: typedef pair<const Key, T> value_type;
  3. 在内部,multimap中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对key进行排序的。
  4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢,但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
  5. multimap在底层用二叉搜索树(红黑树)来实现。

注意:

  1. multimap中的key是可以重复的。

  2. multimap中的元素默认将key按照小于来比较

  3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。

  4. 使用时与map包含的头文件相同:

2.与map的区别

multimap和map的唯一不同就是:map中的key是唯一的,而multimap中key是可以重复的。

3.使用举例代码

void test_map2()
{
    string arr[] = { "苹果","草莓", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
        "苹果", "香蕉", "苹果", "香蕉","草莓" };
    map<string, int>CountMap;
    
    for (auto& e : arr)
    {
​
        CountMap[e]++;
​
        //auto it = CountMap.find(e);
        //if (it != CountMap.end())
        //{
        //  it->second++;
        //}
        //else
        //{
        //  //const pair<string, int>& val = { e,1 };
        //  CountMap.insert({ e,1 });
        //}
    }
​
    for (auto& kv : CountMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
​
    //----------------------------------------------------------------------------
    
    multimap<int, string>SortMap;
    for (auto& kv : CountMap)
    {
        //SortMap[kv.second] = kv.first;
        //草莓修改成香蕉了
​
        SortMap.insert({ kv.second,kv.first });
        //香蕉丢了
        //香蕉插入失败了
    }
    cout << endl;
    
    for (auto& kv : SortMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
}

输出结果:

image-20241110201608739

六、unordered_map

1.介绍

1.unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与

其对应的value。

2.在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此

键关联。键和映射值的类型可能不同。

3.在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内

找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。

4.unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭

代方面效率较低。

5.unordered_maps实现了直接访问操作符(operator[]),它允许使用key作为参数直接访问

value。

6.它的迭代器至少是前向迭代器。

2.使用

构造

image-20241110203707021

容器

image-20241110203752340

迭代器

image-20241110203814659

image-20241110204036488

访问

image-20241110203826922

元素查找

image-20241110203851380

修改操作

image-20241110203914519

哈希、桶

image-20241110203933498

image-20241110204111907

3.使用举例代码

void test_map1()
{
    string arr[] = { "苹果","草莓", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
        "苹果", "香蕉", "苹果", "香蕉","草莓" };
    unordered_map<string, int>CountMap;
​
    for (auto& e : arr)
    {
​
        CountMap[e]++;
    }
​
    for (auto& kv : CountMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
}

输出结果:

标签:map,set,元素,value,键值,key,unordered
From: https://blog.csdn.net/lll_666666/article/details/143694851

相关文章

  • 常见 setup.exe 参数 有关 Setup 命令行参数的其他信息,请参阅 Setup Help 文件。有
    Windows安装程序安装或升级Windows。Setup.exe[/debughelp][/auto<upgrade;dataonly;clean>][/quiet][/installdrivers<driver_folder_path>][/noreboot][/installangpacks<language_packfolder_path>][/showoobe<none;full>][/unattend:<ans......
  • Azure Availability Sets and Availability Zones
    InMicrosoftAzure,AvailabilitySetsandAvailabilityZonesarebothkeyfeaturesthatprovidehighavailabilityandfaulttoleranceforyourapplicationsandworkloads,buttheyareusedindifferentwaysandhavedifferentpurposes.Here'sabreak......
  • VUE3 script setup里面如何动态更新整个页面的背景图片
    1.使用内联样式和响应式数据步骤一:创建响应式数据来存储背景图片的URL在scriptsetup中,可以使用ref来创建一个响应式的变量来存储背景图片的URL。<template><div><button@click="changeBackground">更换背景图片</button></div></template><scriptsetup>......
  • Day02-映射(mapping)
    1.映射(Mapping)可以理解为对文档及其字段进行索引或存储的方式。可以拿Mapping和关系型数据库中的schema类比,schema在关系型数据库中指:库表包含的字段及字段存储类型等基础信息。下文中映射等价于Mapping。Elasticsearch映射,描述了文档可能具有的字段、属性、每个字段的数据......
  • Educational Codeforces Round 144 (Rated for Div. 2) C. Maximum Set
    我们要选出最长的子序列,使得每一个数都是前一个数的倍数。因此自然我们可以想到选择最小值然后每次乘\(2\)。所以有\(l\times2^k\ler\),即\(k=\left\lfloor\log_2\frac{r}{l}\right\rfloor\)。所以最大的集合大小就是\(k+1\)。然后考虑最大的集合中最小值可能不同,我假设......
  • MapStruct笔记
    依赖包<dependency><groupId>org.mapstruct</groupId><!--jdk8以下就使用mapstruct--><artifactId>mapstruct-jdk8</artifactId><version>1.2.0.Final</version></dependency><dependency>......
  • appsettings.json launchSettings.json 发布 配置
    默认的 JsonConfigurationProvider 会按以下顺序加载配置:appsettings.jsonappsettings.{Environment}.json:例如,appsettings.Production.json 和 appsettings.Development.json 文件。文件的环境版本是根据 IHostingEnvironment.EnvironmentName 加载的。有关详细信息,......
  • Scala:Scala的Map集合
    Scala的Map概述 Map(映射)是一种可迭代的键值对(Key/Value)结构,所有值都可以通过键来获取,Map中的键都是唯一的。定义Map时,需要为键值对定义类型。 ————Scala的Map的定义————在Java中,Map是以键值对(K,V)的形式存在的,例如(Key1,V1)。在Scala中,Map集合同样是以......
  • 如何使用Yolov8训练——胸部肺结节目标检测数据集 1个类别 精确度P:0.655,召回率R:0.575,m
    同时yolov8n训练100个epoch检测结果如下精确度P:0.655,召回率R:0.575,mAP50:0.639,map50-95:0.289数据集可直接使用,未做任何数据增强等预处理胸部肺结节目标检测数据集该数据集已经包括1个类别分别是:target总计图片4882张图像,分辨率是1024x1024像素数据集是txt格式数......
  • Linux中关于useradd、chmod、chown、getfacl、setfact等权限设置
    文章目录一、Linux用户管理1、用户(user)、用户组(group)、其他用户概念(other)1.1理解Linux的`单用户多任务`,`多用户多任务`概念1.2用户(user)和用户组(group)概念;查看主机名和修改主机名需要root权限(然后输入密码)2.1创建用户2.1.1用adduser创建用户3、删除用户查看用户列......