★ FEATURED ARTICLE 文章目录1. 从“把数据存进去”到“按键找到它”2. set 的第一个程序2.1 构造、批量插入和反向遍历2.2 set 没有整数下标3. “有序”和“重复”都由比较器决定3.1 学生对象只按编号比较4. lower_bound 和 upper_bound先找边界再处理区间5. map 中存的是一整对数据5.1 用字典说明插入、查找和修改6. map 的下标不是数组下标它可能创建元素6.1 find、at 与 [] 应该怎么选6.2 水果计数一行代码就够了7. 一个键要保留多份时multiset 与 multimap8. 为什么 myset 和 mymap 可以复用同一棵红黑树8.1 为什么不直接比较两个 pair9. 树迭代器的 与 --怎样只看局部走到下一个节点10. 一份可以独立运行的 myset / mymap 模拟实现11. 总结1. 从“把数据存进去”到“按键找到它”假设已经有一串整数5、2、7、5现在需要保留不同的整数并且以后经常判断某个整数是否出现过。用已经学过的顺序容器当然可以完成插入前遍历检查或者先排序再去重。但随着数据不断加入我们就需要不断反复维护这两件事。再换一个需求把英文单词与中文解释对应起来输入left希望找到“左边”。这次就不只是确认单词是否存在了还需要取出与它关联的内容。这两个需求分别对应需求适合的容器一个元素表示什么记录不同的键判断键是否存在std::setKey一个键根据键查询对应的信息std::mapKey, T一个键与它的映射值一个键允许出现多次std::multisetKey一个键每次插入分别保留一个键对应多条记录std::multimapKey, T一个键值对等价键可以重复这里的“键”是用来组织与查找数据的依据不要求它必须是整数。字符串、按编号比较的学生对象甚至对象指针都可以作为键前提是比较规则合适。map和set属于有序关联式容器。我们使用它们时主要关心“这个键在不在”“它对应什么内容”而不是“它位于第几个下标”。遍历顺序由键的比较规则决定默认通常表现为升序。2. set 的第一个程序#includeiostream#includesetintmain(){inta[]{5,2,7,5};std::setints;//将数组元素逐个插入setfor(intx:a){autorets.insert(x);std::coutx: ret.secondstd::endl;}//逐个输出set元素for(intx:s)std::coutx ;std::coutstd::endl;autoposs.find(5);if(pos!s.end())std::coutfound: *posstd::endl;std::couterase 2: s.erase(2)std::endl;std::couterase 9: s.erase(9)std::endl;}运行示例std::set底层是红黑树自动排序 元素唯一不能存放重复值。insert每次尝试插入一个键返回std::pairiterator, bool。ret.first是迭代器指向新元素或容器中已经存在的等价元素。ret.second表示本次有没有插入新元素成功是true已有等价键是false。s.erase(值)这个重载版本返回 size_t代表删除掉元素的个数找到并删除返回 1不存在该值返回 0range for 遍历 set会按升序依次访问2,5,7find找到返回元素迭代器找不到返回end()不能直接解引用 end 迭代器。默认输出布尔值时true显示为1false显示为0。第二次插入5没有增加元素但返回的迭代器仍指向已有的5。2.1 构造、批量插入和反向遍历inta[]{4,2,7,2,8};std::setintempty;// 空集合std::setintfrom_array(a,a5);// [a, a 5)会去重std::setintfrom_list{4,2,7};std::setintcopyfrom_list;// 标准 set 支持独立复制empty.insert(a,a5);// 插入一个迭代器区间empty.insert({3,5,5});// 列表中的重复键同样只保留一个for(autoitempty.rbegin();it!empty.rend();it)std::cout*it ;// 与正向遍历相反的顺序rbegin()与rend()是反向迭代器接口。对反向迭代器执行沿着反向遍历顺序前进。常用的empty()、size()、clear()、swap()等接口与之前容器相似。clear()清空所有元素标准库的复制构造和赋值会复制内容修改副本不会修改原容器。2.2 set 没有整数下标对std::setint来说find(2)查找的是键 2不是“第 2 个元素”。set不提供s[2]迭代器也不支持it 2、it[2]或两个迭代器相减。它的迭代器是双向迭代器支持和--。如果确实要走到第 k 个位置需要逐步移动时间与移动步数有关。因此set适合按键访问不适合反复按排名随机访问。3. “有序”和“重复”都由比较器决定默认的setint使用std::lessint即按“小于”关系组织键。如果想降序可以使用functional中的std::greaterintstd::setint,std::greaterints{5,2,7,5};// 正向遍历是 7、5、2。这表示的是按照当前排序规则。对整数的小于比较与整数相等一致对自定义对象却可能与所有成员是否相等不同。3.1 学生对象只按编号比较#includeiostream#includesetstructStudent{intid;std::string name;};structById{booloperator()(constStudenta,constStudentb)const{returna.idb.id;}};intmain(){std::setStudent,ByIdstudents;students.insert({2,Bob});students.insert({1,Ann});autoretstudents.insert({2,Ben});std::coutinsert Ben: ret.secondstd::endl;std::coutexisting: ret.first-namestd::endl;for(constautoe:students)std::coute.id e.namestd::endl;}运行示例ById是仿函数对象可以通过operator()像函数一样调用。它只比较id所以{2, Bob}与{2, Ben}是等价键。4. lower_bound 和 upper_bound先找边界再处理区间对默认升序的整数集合接口返回的位置lower_bound(x)第一个 x的元素upper_bound(x)第一个 x的元素equal_range(x)将以上两个边界打包成一个pair没找到符合条件的位置就返回end()。它们不要求键x本身一定存在比如在10、20、30、40中lower_bound(25)仍然可以找到30。若想要删除闭区间[30, 60]中的键可用//s 是默认升序的 std::setint。s.erase(s.lower_bound(30),s.upper_bound(60));左边指向首个需要删除的元素右边指向首个不需要删除的元素传给erase的是迭代器半开区间[first, last)。#includeiostream#includesetintmain(){std::setints;for(inti1;i9;i)s.insert(i*10);autofirsts.lower_bound(30);autolasts.upper_bound(60);std::coutrange: ;for(autoitfirst;it!last;it)std::cout*it ;std::coutstd::endl;s.erase(first,last);std::coutremain: ;for(intx:s)std::coutx ;std::coutstd::endl;std::setint,std::greaterintdesc{10,20,30,40,50};std::coutdescending bounds: *desc.lower_bound(30) *desc.upper_bound(30)std::endl;}运行示例为什么降序情况下upper_bound(30)返回20因为边界定义必须依照比较器的顺序不能一直背“数值大于”。更一般地说lower_bound(key)第一个使comp(element_key, key)为false的位置。upper_bound(key)第一个使comp(key, element_key)为true的位置。lower_bound(key)默认std::lessint升序comp(a,b)就是ab→ 找第一个不满足 element key也就是 keystd::greaterint降序comp(a,b)就是ab→ 找第一个不满足 element key也就是element keyupper_bound(key)升序 lesscomp (key,elem) → key elem降序 greatercomp (key,elem) → key elem对std::greaterint序列是50、40、30、20、10。找到30后再沿容器的正向顺序走后面的键是20所以两个返回值分别是30与20。5. map 中存的是一整对数据std::mapKey, T的一个元素类型是// 类型说明片段Key 是键类型T 是映射值类型。std::pairconstKey,Tpair可以先理解成标准库提供的“双成员结构体”first保存第一个数据second保存第二个数据。std::make_pair(a, b)用来构造键值对它按实参推导类型产生的对象可以在满足条件时转换成map所需的元素类型。map的几个类型名容易混淆名称mapstd::string, int中的含义key_typestd::string用于比较和查找的键mapped_typeint键关联的内容value_typestd::pairconst std::string, int完整的一个元素5.1 用字典说明插入、查找和修改#includeiostream#includemapintmain(){std::mapstd::string,std::stringdict;//插入dict.insert({left,左边});dict.insert(std::make_pair(right,右边));//插入重复autoretdict.insert({left,剩余});std::coutinsert again: ret.secondstd::endl;std::coutleft: ret.first-secondstd::endl;//查找修改autoposdict.find(left);if(pos!dict.end())pos-second左侧;//逐个输出元素for(constautoe:dict)std::coute.first: e.secondstd::endl;//查找不存在的元素constautoviewdict;automissingview.find(up);std::coutmissing: (missingview.end())std::endl;}运行示例insert()只有 key 不存在才会插入如果 key 已经存在不会覆盖旧 value再次insert({left, 剩余})keyleft已经存在插入失败。ret.second是false打印输出0ret.first迭代器指向原来的left:左边。想要修改 value不能用 insert要用findfind(left)返回迭代器pos-second 左侧直接修改 pair 的 value。范围 for 遍历 map按 key 字典序输出left在前right在后。find查找失败返回end()迭代器view.find(up)找不到missing view.end()表达式结果为 true输出1。6. map 的下标不是数组下标它可能创建元素对std::mapstd::string, int countcount[apple]的参数是键返回类型是int。这与数组按整数位置访问的行为不同。它分两种情况键已存在返回该元素second的引用。键不存在插入一个新元素其映射值按规则进行值初始化再返回新元素second的引用。#includeiostream#includemapintmain(){std::mapstd::string,intcount;std::coutbefore: count.size()std::endl;std::coutapple initial: count[apple]std::endl;std::coutafter: count.size()std::endl;count[apple];intrefcount[apple];ref2;std::coutapple now: count.at(apple)std::endl;}运行示例apple initial: 0执行count[apple]时容器内不存在apple这个 key随后自动插入appleint 类型默认初始值为 0打印这个 0。这一步过后新增元素。after: 1上一步已经插入了一对键值map 现在元素数量变成 1。count[apple]apple已经存在拿到它的值引用0 自增变成 1。int ref count[apple]; ref 2再次获取apple值的引用1 再加 2最终值变成 3。apple now: 3at找到apple读取并打印最终结果 3。map 的[]不是单纯读取。key 不存在时哪怕只是打印读取也会插入这个键值对。而at只查询不会插入。6.1 find、at 与 [] 应该怎么选接口键不存在时是否自动插入是否可通过 const map 使用find(key)返回end()否是返回只读迭代器at(key)抛出std::out_of_range否是返回只读值引用operator[](key)插入值初始化的映射值是否6.2 水果计数一行代码就够了#includeiostream#includemapintmain(){std::string fruit[]{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};std::mapstd::string,intcount;for(constautoname:fruit)count[name];for(conststd::string name:{苹果,西瓜,香蕉})std::coutname: count.at(name)std::endl;}第一次遇到“苹果”count[name]插入{苹果, 0}然后将它改成1。第二次遇到“苹果”直接取得已有次数的引用再加一。于是“首次出现”和“再次出现”通过默认值0接在了一起。7. 一个键要保留多份时multiset 与 multimapmultiset与multimap允许等价键重复存在但仍然保持按比较器有序。一个英文单词有多个解释时multimap可以分别保留每条解释。操作set / mapmultiset / multimap单元素insert返回pairiterator, bool返回新插入元素的迭代器count(key)0 或 1等价键的实际数量find(key)找到唯一的等价元素或end()找到一个等价元素或end()erase(key)删除至多一个元素删除全部等价键元素erase(iterator)删除该位置一个元素同样只删除该位置一个元素下标[]只有 map 提供均不提供多重容器的find不保证返回等价区间的第一个元素。如果需要枚举所有等价键需使用equal_range。8. 为什么 myset 和 mymap 可以复用同一棵红黑树到这里容器的使用已经足够解决去重、字典和计数问题。接下来从红黑树出发理解封装设计。旋转与颜色修复的完整推导见此前的红黑树文章本篇把注意力放在新的接口关系上。把红黑树改造成公共底层时它要同时知道三件事参数负责什么set 场景map 场景K查找时传入的键类型intstringT节点实际存储的数据类型intpairconst string, intKeyOfT如何从数据 T 中得到键 K返回数据自身返回 firstCompare如何比较两个键lessless这里的T是节点数据不能直接当成 map 的映射值。例如RBTreestd::string, std::pairconst std::string, int, ...中find接受字符串但insert接受一整个键值对。8.1 为什么不直接比较两个 pair假设把{apple, 1}与{apple, 3}直接作为两对数据比较。pair的默认字典序比较会先比较first键相同时还会比较second。这样可能把同一个键的两个不同计数当成不同位置违背 map 对键唯一性的要求。树不应擅自决定“元素的哪些成员参与比较”所以把这个决定交给KeyOfT。下面是完整实现中取键器的局部定义片段// set 的取键器K 是外层类的键类型。structKeyOfT{constKoperator()(constKvalue)const{returnvalue;}};// map 的取键器value_type 是 pairconst K, V。structKeyOfT{constKoperator()(constvalue_typevalue)const{returnvalue.first;}};两段代码分别位于两个类中不能当作同一作用域里重复定义的完整程序。9. 树迭代器的 与 --怎样只看局部走到下一个节点按照中序遍历元素顺序是左子树、当前节点、右子树。迭代器不必每次重新遍历整棵树来确定位置节点的孩子和 parent 指针已经提供了局部路径。对it当前节点有右子树下一项是右子树的最左节点。没有右子树沿 parent 向上走跳过“当前子树是父亲右孩子”的路径第一次从左孩子上来那个父亲就是下一项。一直走到没有父亲已经越过最后一个元素进入end()。--it则左右对称有左子树找其中最右节点否则向上找直到第一次从右孩子上来。--end()是特殊情况它需要从当前树的根出发找到最右节点。10. 一份可以独立运行的 myset / mymap 模拟实现代码仓库《myset / mymap 模拟实现》11. 总结set、map 底层都是红黑树元素自动按照 key 有序排列key 不可重复。set 只存 keymap 存储 key-value 键值对key 为 const 不可修改value 可以修改。insertkey 不存在才插入key 重复则插入失败返回 pairsecond 标记插入结果。find查找 key找到返回迭代器失败返回 end ()只查询不新增元素。map 支持operator[]key 不存在时会自动插入默认 value只读查询推荐用 find 或 at。count返回 0 或 1用来判断 key 是否存在。erase传 key 删除该键值对传迭代器只删除迭代器指向的单个元素。lower_bound、upper_bound 可以获取 key 的边界区间得到左闭右开范围支持区间遍历与区间删除。
阅读完成 · 觉得有帮助？
