【C++】树形结构的关联式容器(map、set)

这篇具有很好参考价值的文章主要介绍了【C++】树形结构的关联式容器(map、set)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

set

  1. set 是按照一定次序存储元素的容器
  2. 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现的。
#include <iostream>
#include <map>
#include <set>
using namespace std;
void test_set1()
{
	set<int> s;
	s.insert(3);
    s.insert(2);
    s.insert(4);
    s.insert(5);
    s.insert(1);
    s.insert(5);
    s.insert(2);
    s.insert(5);

    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    auto pos = s.find(3);//o(logn)
    //auto pos = find(s.begin(), s.end(), 3);o(N) 暴力查找
    if (pos != s.end())
    {
        s.erase(pos);
    }

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
}
int main()
{
    test_set1();
    return 0;
}

【C++】树形结构的关联式容器(map、set),c++,c++

set操作函数方法

find查找

find(时间复杂度为log(N)),利用二叉搜索树查找方式。返回值为迭代器

【C++】树形结构的关联式容器(map、set),c++,c++

count返回重复数字出现的次数

【C++】树形结构的关联式容器(map、set),c++,c++

【C++】树形结构的关联式容器(map、set),c++,c++

lower_bound 返回大于等于目标值的iterator

lower_bound在查找目标值的时候,只针对搜索大于等于该值的目标,并且找到后返回其iterator位置,如果没有找到,则返回end位置
【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++

upper_bound返回大于目标值的iterator

upper_bound返回目标值后一个位置的iterator位置

【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++

equal_range 获取相等元素的范围

如果要查找的元素在本set中没有,则会返回跟他最接近且大的值,如果要查找的元素只有一个,则会返回元素本身到最后一个元素区间。

【C++】树形结构的关联式容器(map、set),c++,c++

【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++

源代码

void test_set1()
{
	set<int> s;
	s.insert(3);
    s.insert(2);
    s.insert(4);
    s.insert(5);
    s.insert(1);
    s.insert(5);
    s.insert(2);
    s.insert(5);

    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    set<int>::iterator pos = s.find(3);//o(logn)
    auto pos = find(s.begin(), s.end(), 3);o(N)
    if (pos != s.end())
    {
        s.erase(pos);
    }

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
}

multiset 操作方法

  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 ( l o g 2 N ) O(log_2 N) O(log2N)
  7. multiset的作用:可以对元素进行排序
count返回重复数字出现的次数

【C++】树形结构的关联式容器(map、set),c++,c++

lower_bound和upper_bound

【C++】树形结构的关联式容器(map、set),c++,c++
此处只简单演示set与multiset的不同,其他接口接口与set相同

源代码

void test_set2()
{
    multiset<int> s;
    s.insert(3);
    s.insert(5);
    s.insert(8);
    s.insert(7);
    s.insert(7);
    s.insert(9);
    s.insert(7);

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    cout << s.count(7) << endl;

    auto ret = s.equal_range(7);
    auto itlow = ret.first;
    auto itup = ret.second;

    cout << *itlow << endl;
    cout << *itup << endl;

    s.erase(itlow, itup);
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
}

认识pair

【C++】树形结构的关联式容器(map、set),c++,c++

模拟实现pair

template <class T1, class T2>
 struct pair 
{
 	typedef T1 first_type;
 	typedef T2 second_type;
 	T1 first;
 	T2 second;
	pair(): first(T1()), second(T2())
 	{}
	pair(const T1& a, const T2& b): first(a), second(b)
 	{}
 };

认识make_pair

make_pair就直接帮我们内部调用了pair
【C++】树形结构的关联式容器(map、set),c++,c++

map操作方法

  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通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。

【C++】树形结构的关联式容器(map、set),c++,c++

insert

insert插入用的pair来插入的
【C++】树形结构的关联式容器(map、set),c++,c++

【C++】树形结构的关联式容器(map、set),c++,c++

private:
    int _a1;
    int _a2;
};

void test_map1()
{
    map<string, string> dict;

    pair<string, string> kv1("insert", "插入");
    dict.insert(kv1);

    dict.insert(pair<string, string>("sort", "排序"));
	//c++98
    dict.insert(make_pair("string", "字符串"));

    //C++11多参数的构造函数隐式类型转换
    dict.insert({ "apple","苹果" });
    //例如
    string str = "hello";//字符串隐式类型转换
    A aa1 = { 1,2 };
     
}

【C++】树形结构的关联式容器(map、set),c++,c++
在我们的日常使用中,map中的key值是不可以修改的,只有value值是可以修改的
【C++】树形结构的关联式容器(map、set),c++,c++

【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++

void test_map2()
{
    map<string, string> dict;
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("insert", "插入"));
    dict.insert(make_pair("sort", "排序"));

    //map<string, string>::iterator it = dict.begin();
    auto it = dict.begin();
    
    while (it != dict.end())
    {
        //it->first = "xxx";
        it->second = "xxx";
        cout << (*it).first << " : " << (*it).second << endl;
        cout << it->first << " : " << it->second << endl;
        it++;
    }
    cout << endl;

    for (const auto& kv : dict)
    {
        cout << kv.first << " : " << kv.second << endl;
    }
}

【C++】树形结构的关联式容器(map、set),c++,c++

opeartor[]

map的【】和我们平时使用的【】是完全不一样的
在元素访问时,有一个与operator[]类似的操作at()(该函数不常用)函数,都是通过key找到与key对应的value然后返回其引用,不同的是:当key不存在时,operator[]用默认value与key构造键值对然后插入,返回该默认value,at()函数直接抛异常。

普通插入
【C++】树形结构的关联式容器(map、set),c++,c++
使用operator[] 插入
【C++】树形结构的关联式容器(map、set),c++,c++
【C++】树形结构的关联式容器(map、set),c++,c++

void test_map3()
{
    string arr[] = { "苹果","橘子","梨","苹果","橘子","梨" ,"苹果" };
    map<string, int> countMap;
    /*for (auto e : arr)
    {
        auto it = countMap.find(e);
        if (it == countMap.end())
        {
            countMap.insert(make_pair(e, 1));
        }
        else
        {
            it->second++;
        }
    }*/

    for (auto e : arr)
    {
        countMap[e]++;
    }

    for (const auto& kv : countMap)
    {
        cout << kv.first << " ; " << kv.second << endl;
    }
}

验证【】插入方法

void test_map5()
{
     map<string, string> dict;
     dict.insert(make_pair("string", "字符串"));
     dict.insert(make_pair("insert", "插入"));
     dict.insert(make_pair("sort", "排序"));

     cout << dict["sort"] << endl;//查找和读
     dict["map"];              //插入
     dict["map"] = "映射地图";//修改
     dict["insert"] = "xxx";//修改
     dict["set"] = "集合";//插入+修改

     for (auto it : dict)
     {
         cout << it.first << " : " << it.second << endl;
     }
}

【C++】树形结构的关联式容器(map、set),c++,c++

multimap

multimap只跟map差一个operator[]操作方法,其次,multimap还支持多个相同元素的存放文章来源地址https://www.toymoban.com/news/detail-629219.html

到了这里,关于【C++】树形结构的关联式容器(map、set)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++高级编程——STL:list容器、set容器和map容器

    本专栏记录C++学习过程包括C++基础以及数据结构和算法,其中第一部分计划时间一个月,主要跟着黑马视频教程,学习路线如下, 不定时更新,欢迎关注 。 当前章节处于: ---------第1阶段-C++基础入门 ---------第2阶段实战-通讯录管理系统, ---------第3阶段-C++核心编程, -----

    2024年01月25日
    浏览(47)
  • 【C++】容器篇(五)—— map和set的基本介绍

    序言: 在之前,我们已经对STL中的 序列式容器 进行了相关的学习。本期,我将给大家介绍的则是另外一类容器 ——  关联式容器 !!! 目录 (一)容器回顾 💨【顺序容器】 💨【关联式容器】 💨【容器适配器】 (二)键值对 (三)树形结构的关联式容器 1、set  1️⃣

    2024年02月14日
    浏览(36)
  • 【C++】map与set容器——红黑树底层封装

    💭STL中,容器大概可分为两种类型——序列式容器和关联式容器。在前面的系列文章中,我们已经介绍了诸多序列式容器,如:vector、list、stack、queue等,它们以序列的形式存储数据。 💭而关联式容器也是一种非常重要的容器。标准的STL关联式容器分为set(集合)和map(映

    2023年04月11日
    浏览(40)
  • C++进阶:详细讲解容器set与map(pair、multiset、multimap)

    C++进阶:详细讲解容器set与map(pair、multiset、multimap) 上次介绍了搜索二叉树:C++进阶:二叉搜索树介绍、模拟实现(递归迭代两版本)及其应用 为了介绍后面的AVLTree和红黑树,我们要进行一些铺垫,就是set与map的介绍啦 关联式容器和序列式容器是 C++ 中两种不同的容器类

    2024年04月12日
    浏览(40)
  • 【C++】数据结构的恶龙set和map来了~

    下一篇AVL树难点中的难点~   文章目录 前言 一、set的介绍 二、map的介绍        题目练习 总结   1.关联式容器 在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque、 forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面

    2024年02月05日
    浏览(39)
  • 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)

    前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是: 其底层都是按照 二叉搜索树 来实现的。 但是二叉搜索树有其自身的缺陷,假如 往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) ,

    2024年02月06日
    浏览(45)
  • 【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 在学习了二叉搜索树后,现在 就可以来学习map和set了,虽然 它们的底层是红黑树结构,但是红黑树 的本质也是一颗二叉搜索树! 本质重点: 本

    2024年02月05日
    浏览(39)
  • 「数据结构」Map&Set

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! Map和Set是专门用来进行搜索的容器或者数据结构,它们适合动态查找(即在查找时可能会进行一些插入和删除的操作) 我们一般把搜索的数据称为 (Key) ,和对应的称为 值(

    2024年02月22日
    浏览(50)
  • 【C++】map & set

    我们前面接触过 STL 中的部分容器,比如:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别? 关联式容器 也是用来存储数据的,与序列式容器

    2024年04月14日
    浏览(26)
  • [数据结构]-map和set

    前言 作者 : 小蜗牛向前冲 名言 : 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正   目录 一、键值对 二、set 1、set的基本知识 2、set的使用  三、map 1、map的基本

    2024年02月04日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包