set和map基础:【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
std::map 容器 是 C++ 语言 标准模板库 ( STL , Standard Template Library ) 提供的 的一个 " 关联容器 " ;
STL 是 Standard Template Library 的缩写,中文译为“标准模板库”。STL 是 C++ 标准库的一部分。
关联容器和顺序容器的根本不同之处在于,关联容器中的元素是按关键字来保存和访问的(比如map和set),而顺序容器中的元素是按照在容器中的位置来顺序保存和访问的(比如vector和string)。
在C++ Standard Template Library(STL)中,map和set作为关联容器,为开发者提供了键值对存储和唯一键集合管理的强大工具。它们底层通常基于红黑树实现,保证了元素的有序性和对数时间复杂度的查找效率。本文将深入浅出地解析map与set的使用方法、常见问题及其规避策略,并通过代码示例加以说明。
这一章介绍了标准库中的关联容器们,主要是11.3的对有序关联容器操作的介绍。这章比较短,也只是比较工具性的东西,快速浏览即可。下一章就是C++的重要运用:动态内存管理。
—————————————–分割线—————————– map和set都是stl中的关联容器,map以键值对的形式存储,key=value组成pair,是一组映射关系。set只有值,可以认为只有一个数据,并且set中元素不可以重复且自动排序,如果需要重复则使用multiset,要说区别的话,存储的东西不一样,应用场景不一样,支持的操作也不一样,很多不同。 map和set支持快速查找和删除,一般使用RB树来实现,当然后面还有用hashtable实现的,使用rb树作为底层结构增删数据都很快,不存在内存移动也就不容易出现迭代器失效的问题,这也就是区别于vector的原因-内存移动 Map中的每一个元素包含一个键对象和值对象,它们成对出现。键对象不能重复,值对象可以重复。 Set中的对象不按特定方式排序,并且没有重复对象。但它的有些实现类能对集合中的对象按特定方式排序,例如TreeSet类,它可以按照默认排序,也可以通过实现java.util.Comparator接口来自定义排序方式。
//https://blog.csdn.net/qls315/article/details/106759358
C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。
第 11 章 关联容器 标签: C++Primer 学习记录 关联容器 ---- 第 11 章 关联容器 11.1 使用关联容器 11.2 关联容器概述 11.3 关联容器操作 11.4 无序容器 ---- 11.1 使用关联容器 标准库中定义了 8个关联容器,这些容器的不同体现在三个维度上。 或者是一个 set,或者是一个 map。 或者要求不重复的关键字,或者允许重复关键字,允许重复的容器的名字中都包含单词 multi。 或者按顺序保存元素或无序保存。不保持关键字按顺序存储的容器的名字都以 unord
之前介绍过标准库中的顺序容器,顺序容器是元素在内存中按照一定顺序进行排列的,都是按线性结构进行排列。除了顺序容器外,c++中还有关联容器。与顺序容器不同的是,关联容器中元素是按照关键字来保存和访问的。与之相对的顺序容器是按它们在容器中的位置来顺序的保存和访问的。
它的特性总结来讲就是:所有元素都会根据元素的键值key自动排序(也可根据自定义的仿函数进行自定义排序),其中的每个元素都是<key, value>的键值对,map中不允许有键值相同的元素,
这篇是第二部分的总结,基本上就是回看了之前的5篇笔记并且重新翻翻书梳理了一下,内容基本都是从前面的章节复制来的,长度较长,不熟悉的话看起来可能不会很轻松。
函数默认是进行升序排序,同时函数也接受第二个参数指定排序方法:SORT_ASC(升序)、SORT_DESC(降序)
STL的意思是与迭代器合作的C++标准库的一部分,包括标准容器(包括string),iostream库的一部分,函数对象和算法,它不包括标准容器适配器(stack,queue和priority_queue)以及bitset和valarray容器,因为它们缺乏迭代器的支持,也不包括数组。数组以指针的形式支持迭代器,但数组是C++语言的一部分,并非库。
set是STL中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高。 set,顾名思义是“集合”的意思,在set中元素都是唯一的,而且默认情况下会对元素自动进行升序排列,支持集合的交(set_intersection),差(set_difference) 并(set_union),对称差(set_symmetric_difference) 等一些集合上的操作,如果需要集合中的元素允许重复那么可
multimap 容器 中 可以 存储 多个具有 相同 键 Key 的 键值对 pair 对组元素 ;
STL(Standard Template Library)的六大组件:容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。其交互关系:容器通过空间配置器取得数据存储空间,空间配置器通过迭代器存取容器的内容,仿函数可以协助空间配置器完成不同的策略变化,配接器可以修饰或套接仿函数。
#estl 第50条:熟悉与STL相关的web站点。三个:www.sgi.com/tech/stl、www.stlport.org 和 www.boost.org。 #estl 第49条:学会分析与STL相关的编译器诊断信息。嗯,第一招是替换大法,然后介绍了一下与容器、插入迭代器、绑定器、输出迭代器或算法相关的错误大概有什么套路看。 #estl 第48条:总是包含(#include)正确 的头文件。因为C++标准没有规定头文件的互相包含关系,所以不同的STL实现有所不同。要记住容器基本上声明在同名文件中,算法是algo..和 num..,迭代器在iterator中,函数子和配接器在functional中。 #estl 第47条:避免产生“直写型”(write-only)的代码。即所谓容易编写,但难以阅读和理解的代码,比如一行调用函数12次,其中 10 个是互不相同的。 #estl 第46条:考虑使用函数对象而不是函数作为STL算法的参数。嗯,因为函数对象更容易让编译器乐于内联,所以速度会快一些。从代码被编译器接受的程度而言,它们更加稳定可靠。 #estl 第45条:正确区分count、find、binary_search、lower_bound、upper_bound和equal_range。嗯,这与传入的区间是否已经排序有关,与你的目的有关,与容器有关,总之复杂,要自己去看这一小节两次。 googollee 我一直认为这个应该由重载来完成 RT @laiyonghao: #estl 第44条:容器的成员函数优先于同名的算法。原因:速度更快,且与容器结合得更加紧密,更能够与容器的行为保持一致。 #estl 第44条:容器的成员函数优先于同名的算法。原因:速度更快,且与容器结合得更加紧密,更能够与容器的行为保持一致。 #estl 第43条:算法调用优先于手写的循环。三个理由:效率更高,更不容易出错,和更好的可维护性。 #estl 第42条:确保less<T>与operator<T>具有相同的语义。真理总是如此平淡……还能说啥呢? #estl 第41条:理解ptr_fun、mem_fun和mem_fun_ref的来由。咳,想起当年理解 .* 和 ->* 的时候多么地头痛…… #estl 第40条:若一个类是函数子,则应使它可配接。因为 STL 的函数配接器要求一些特殊的类型定义,argument_type,result_type…之类。编写函数子从unary_function或 binary_function继承是一个不错的方案。 #estl 第39条:确保判别式是“纯函数”。纯函数即返回值仅仅依赖于其参数的函数。估计在这条阴沟里翻过船的人不少,哈哈哈。 #estl 第38条:遵循按值传递的原则来设计函数子类。换句话说就是让它们小巧,而且单态。这个条款的意义在于为赘重而且多态的函数子带来的问题提出一个解决方案,pimpl 惯用法。 #estl 第37条:使用accumulate或者for_each进行区间统计,前者的代码更明了一些,重要的是它们接受的函数子要求不同。 #estl 第36条:理解copy_if算法的正确实现。文中给出了一个正确实现,注意点是不能要求使用的函数子是可配接的,STL 算法都这样。 #estl 第35条:通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较。 #estl 第34条:了解哪此算法要求使用排序的区间作为参数。嗯,STL 算法有不少是要排序的区间的,如果实参并非如此,轻则性能下降,重则逻辑错误,不可不察。 #estl 第33条:对包含指针的容器使用remove这一类算法时要特别小心。作为cpp程序员,一定要时刻警惕资源泄漏。boost::shared_ptr是一个好选择。 #estl 第32条:如果确实需要删除元素,则需要在remove这一类算法之后调用erase。嗯,讲的就是erase-remove惯用法的由来,另外在讲了一次不同容器删除元素的方法是不同的。 #estl 第31条:了解各种与排序有关的选择。简言之,介绍了partition/stable_partition/nth_element /partial_sort/sort/stable_sort的用法和适用场合。 吼吼,到这里,书就看了一半了。接下来是重头戏:算法。 #estl 第30条:确保目标区间足够大。特别是做覆盖的时候,一定要注意,可以先用resize撑大。插入时用back_inserter、front_…、 inserter和ostream_iterator。 #estl 第29条:对于逐个字符的输入请考虑使用istreambuf_iterator。先说了一下istream_it
1.可以用下标访问的容器有(既可以插入也可以赋值):vector、deque、map;
vector 是 C++ 标准库提供的一个动态数组容器,它可以自动扩展和收缩,使其非常适合存储和管理可变数量的元素。
可能很多人都不在意,在使用STL容器的时候,潜意识里面将clear()成员函数视为常量时间复杂度O(1)的。但是其实不然。我感觉可能是很多人都知道对于vector而言,clear()之后,修改了size()的结果,不影响capacity()的结果,因而得出clear()只是修改了某个标记,是常量时间复杂度的错误结论。
本节将深入学习现代C++实战30讲中的第4节与第5节容器所提到的内容。正文中的一些文字直接引用自上面。
C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。若需要存储的元素数在编译器间就可以确定,可以使用数组来存储,否则,就需要用到容器类了。
内存管理分为堆、栈和RAII(Resource Acquisition Is Initialization)。除了C,还有几个语言D、Ada和RAII少数派语言也采用RAII
php 内置的排序函数很多,正反各种排,常用的排序函数: sort() – 以升序对数组排序 rsort() – 以降序对数组排序 asort() – 根据值,以升序对关联数组进行排序 ksort() – 根据键,以升序对关联数组进行排序 arsort() – 根据值,以降序对关联数组进行排序 krsort() – 根据键,以降序对关联数组进行排序 基本都能满足需求了,关于这些函数的使用方法就不多啰嗦了,但是在项目的实际开发中还是会有些更加苛刻的排序需求,今天要介绍的排序函数是: uasort
C++中的map是一种关联容器,用于存储键值对。它提供了一种非常高效的方法来快速查找特定的值,并且允许我们根据键来排序和遍历数据。
利用Collections.reverseOrder()方法:倒叙排列,数组倒置。
1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。 2. 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型 value_type绑定在一起,为其取别名称为pair:
Section I 正确区分不同的查找算法count,find,binary_search,lower_bound,upper_bound,equal_range 本文是对Effective STL第45条的一个总结,阐述了各种查找算法的异同以及使用他们的时机。
作为关联式容器的一种,map 容器存储的都是 pair 对象,也就是用 pair 类模板创建的键值对。其中,各个键值对的键和值可以是任意数据类型,包括 C++ 基本数据类型(int、double 等)、使用结构体或类自定义的类型。
STL 容器库是 STL 的一个重要组成部分,提供了多种数据结构,包括序列容器、关联容器和容器适配器等,用于存储和管理数据。容器管理着为其元素分配的存储空间,并提供成员函数来直接访问或通过迭代器(具有类似于指针的属性的对象)访问它们。
如果需求了解集合的其他功能,可以通过下面的链接了解。(公众号中无法访问外网,可以通过阅读原文进行查询)
在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque。forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面 存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?
从c++11标准以来,c++中std定义的几种容器的效率非常高,优化的非常好,完全没有必要自己去定义类似的数据结构。了解使用它们,可以满足90%的日常编程需要。该篇文章基于c++11标准,从用户角度来介绍常用的顺序容器与并联容器(如果想从内部了解它们是怎么实现的,推荐看看《std源码剖析》这本书)。它们包括:
有一个列表,分别包含几下文本行:"01 hadoop", "02 flume", "03 hive", "04 spark"
当我们谈论编程中的数据结构时,顺序容器是不可忽视的一个重要概念。顺序容器是一种能够按照元素添加的顺序来存储和检索数据的数据结构。它们提供了简单而直观的方式来组织和管理数据,为程序员提供了灵活性和性能的平衡。
list.sort(cmp=None, key=None, reverse=False)
STL就是Standard Template Library,标准模板库。这可能是一个历史上最令人兴奋的工具的最无聊的术语。从根本上说,STL是一些“容器”的集合,这些“容器”有list, vector,set,map等,STL也是算法和其它一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。是C++标准库的一个重要组成部分,它由Stepanov and Lee等人最先开发,它是与C++几乎同时开始开发的;一开始STL选择了Ada作为实现语言,但Ada有点不争气,最后他们选择了C++,C++中已经有了模板。STL又被添加进了C++库。1996年,惠普公司又免费公开了STL,为STL的推广做了很大的贡献。STL提供了类型安全、高效而易用特性的STL无疑是最值得C++程序员骄傲的部分。每一个C++程序员都应该好好学习STL。大体上包括container(容器)、algorithm(算法)和iterator(迭代器),容器和算法通过迭代器可以进行无缝连接。
vector封装数组,list封装了链表,map和set封装了二叉树等。set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。set插入是按照一定规则排序,默认是由小到大。
容器操作函数find(begin, end, val) 返回值是迭代器,没找到返回end。 容器类型和元素类型都相同,可以用赋值vec1=vec2。容器类型不同或元素类型不同,但是兼容可以用assign函数来赋值。 vector容器中的元素以连续的方式存放【动态数组】。有预先分配策略,需要重新分配时加倍当前容量。capacity函数获取目前能够存储的元素总数,reserve函数设置capacity。 string中的字符也是连续存储的,也有迭代器string::iterator。string类将string
持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第17天,点击查看活动详情
在 C++ 语言 标准模板库 ( STL , Standard Template Library ) 中 , std::set 集合容器 中 包含一组唯一的元素 , 并且元素在容器中是自动排序的 ;
STL库还有很多内容,比如:向量(vector)、栈(stack)、队列(queue)、优先队列
本文主要介绍博主在以往开发过程中,对于不同业务所对应的 sql 写法进行归纳总结而来。进而分享给大家。
上期说过C++这块面试问的东西也蛮多,简历上只要出现C++这几个字,那么STL库就是必问。
C++ 标准模板库 ( STL , Standard Template Library ) 中 提供 了 sort 算法 函数 , 该函数定义在 <algorithm> 头文件 中 , 是一个泛型算法 ;
题记: 前段时间集中精力写了数据的分拣算法,用到了容器QMap和QMultiMap。回头再来回去该算法的时候,又觉得当时好像不是自己写的一样,于是有必要将QMap类来总结一下。
对于有序容器,关键字类型必须定义元素比较的方法。默认情况下,标准库使用关键字类型的<运算符来比较两个关键字。
进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:
领取专属 10元无门槛券
手把手带您无忧上云