个性化定制网站有哪些,云南公司网站开发,建网站什么样的域名最好,思明区建设局官网站【C】—— map 与 set 1 序列式容器和关联式容器2 set 系列的使用2.1 set 和 multiset 参考文档2.2 set 类的介绍2.3 set 的迭代器和构造2.4 set的增删查2.4.1 insert2.4.2 find 与 erase2.4.3 count 2.5 lower_bound 与 upper_bound2.6 multiset 与 set 的差异2.6.1 不再去重2… 【C】—— map 与 set 1 序列式容器和关联式容器2 set 系列的使用2.1 set 和 multiset 参考文档2.2 set 类的介绍2.3 set 的迭代器和构造2.4 set的增删查2.4.1 insert2.4.2 find 与 erase2.4.3 count 2.5 lower_bound 与 upper_bound2.6 multiset 与 set 的差异2.6.1 不再去重2.6.2 find 返回中序的第一个2.6.3 erase 删除所有的 x2.6.4 count 个数 1 序列式容器和关联式容器 前面我们已经接触过 STL 中的部分容器如string、vector、list、deque、array等这些容器统称为序列式容器因为他们是逻辑结构为线性序列的数据结构物理结构不一定为线性两个位置存储的值之间一般没有紧密的关联关系比如交换一下它依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的 关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有 map / set 系列和 unordered_map / unordered_set 系列 本文讲解的 m a p map map 和 s e t set set 底层是红黑树红黑树是一颗平衡二叉搜索树。 s e t set set 是 k e y key key 搜索场景的结构 m a p map map 是 k e y key key / v a l u e value value 搜索场景的结构
2 set 系列的使用
2.1 set 和 multiset 参考文档 https://legacy.cplusplus.com/reference/set/ 2.2 set 类的介绍
set 的声明如下
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type class set;• s e t set set 的声明如上T 就是 s e t set set 底层关键字的类型 • s e t set set 默认要求 T 支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数 • s e t set set 底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。 • ⼀般情况下我们都不需要传后两个模版参数。 • s e t set set 底层是用红黑树实现增删查效率是 O(logN)迭代器遍历是⾛的搜索树的中序所以是有序的。 • 前面部分我们已经学习了 v e c t o r vector vector / l i s t list list 等容器的使用STL 容器接口设计高度相似所以这里我们就不再⼀个接口⼀个接口的介绍而是直接带着大家看文档挑比较重要的接口进行介绍。 这里库中的模板参数用的是 T个人认为这里设计的不够好既然是搜索那用 Key 更好我们可以将其当成是 Key虽然库中没用这个名字。
2.3 set 的迭代器和构造 s e t set set 的迭代器是一个双向迭代器 // 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();s e t set set 主要构造方式如下
无参构造
explicit set(const key_compare comp key_compare(),const allocator_type alloc allocator_type());迭代器区间构造
template class InputIterator
set(InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type());拷贝构造
set(const set x);
set(const set x, const allocator_type alloc);列表构造
set(initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());2.4 set的增删查 首先要注意的是 s e t set set 是不支持改的因为 s e t set set 属于关联式容器对齐进行数据修改会破坏它的存储结构
2.4.1 insert
// 单个数据插⼊如果已经存在则插⼊失败
pairiterator, bool insert(const value_type val);// 列表插⼊已经在容器中存在的值不会插⼊
void insert(initializer_listvalue_type il);// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert(InputIterator first, InputIterator last);这里 v a l u e value value_ t y p e type type 就是 T即 Key此外 k e y key key_ t y p e type type 也是 T。这里这么设计是为了和后面的 m a p map map 保持一致 返回值 pairiterator, bool 这里还不需要用到它暂不解释在后面的 m a p map map 部分会详细介绍。 举个栗子
int main()
{// 去重升序排序setint s;// 去重降序排序给⼀个⼤于的仿函数//setint, greaterint s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);setint::iterator it s.begin();while (it ! s.end()){// error C3892: “it”: 不能给常量赋值// *it 1;cout *it ;it;}cout endl;。return 0;
}运行结果 可以看到 s e t set set 是不允许两个相同的值进行插入的即 s e t set set 有去重功能。并且 s e t set set 是不允许修改的*it 1 进行修改会报错。 默认 s e t set set 走的是升序如果想走降序可以传递一个大于的仿函数。迭代器的底层走的是一个中序遍历 s e t set set 支持列表插入
int main()
{setint s;s.insert({ 2,8,3,9,2 });for (auto e : s){cout e ;} cout endl;return 0;
}s e t set set 除了支持整型其他任意类型都是可以的如果该类型不支持比较需自己传递仿函数我们以 s t r i n g string string 为例
int main()
{// void insert(initializer_listvalue_type il);// 构造出临时对象再拷贝构造优化成直接构造setstring strset { sort, insert, add };// 遍历string⽐较ascll码⼤⼩顺序遍历的for (auto e : strset){cout e ;} return 0;
}2.4.2 find 与 erase
const_iterator find(const value_type val) const;
iterator find(const value_type val);f i n d find find 返回的是对应位置的迭代器如果没找到就返回 end()
迭代器删除
iterator erase(const_iterator position);Key删除
size_type erase(const value_type val);s i z e size size_ t y p e type type 是一个无符号整型即 u n s i g n e d unsigned unsigned i n t int int返回的是删除元素的个数。 如果删除成功表示删除了一个值返回 1删除失败表示没有删除值返回 0 为什么这里不用 b o o l bool bool 呢这里是为了兼容 m u l t i s e t multiset multiset。 m u l t i s e t multiset multiset 中允许相同数插入的可能 e r a s e erase erase 多个相同的值这时就不能用 b o o l bool bool 了
迭代器区间删除
iterator erase(const_iterator first, const_iterator last);栗子
int main()
{setint s { 4,2,7,2,8,5,9 };for (auto e : s){cout e ;} cout endl;// 删除最⼩值s.erase(s.begin());for (auto e : s){cout e ;}cout endl;// 直接删除xint x;cin x;int num s.erase(x);if (num 0){cout x 不存在 endl;} for (auto e : s){cout e ;}cout endl;// 直接查找在利⽤迭代器删除xcin x;auto pos s.find(x);if (pos ! s.end()){s.erase(pos);}else{cout x 不存在 endl;}for (auto e : s){cout e ;} cout endl;return 0;
}s e t set set 进行删除同样会导致 迭代器失效 i ) 此时删除的是叶子结点 1删除后迭代器中的指针为野指针迭代器失效。 ii ) 删除 6 节点。它要与 5 或 7 节点进行交换删除进行删除。虽然此时迭代器中的指针并不是野指针但它原来的意义已经改变了我们也认为是迭代器失效。 而且从我们的角度我们不知道这个节点是直接删除还是替代法删除。 p s ps ps对二叉搜索树的删除有不理解的小伙伴可移步至【C】—— 二叉搜索树 2.4.3 count c o u n t count count 的功能是返回 v a l u e value value_ t y p e type type 在容器中的个数
size_type count (const value_type val) const;c o u n t count count 是给 m u l t i s t multist multist 设计的因为对 s e t set set 而言 c o u n t count count 要么返回 1 要么返回 0并没有什么意义。但对于 m u l t i s e t multiset multiset 就不一样 m u l t i s e t multiset multiset 是允许多个相同值存在的 我们可以用 c o u n t count count 来判断一个 K e y Key Key 在不在在的话返回的是 1不在返回 0。 而且用 c o u n t count count 来判断往往比 f i n d find find 更方便因为 f i n d find find 返回的是迭代器迭代器 ! end() 才是找到了
int main()
{setint s { 4,2,7,2,8,5,9 };// 利⽤count间接实现快速查找int x;cin x;if (s.count(x)){cout x 在 endl;} else{cout x 不存在 endl;} return 0;
}2.5 lower_bound 与 upper_bound
// 返回⼤于等于val位置的迭代器
iterator lower_bound(const value_type val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type val) const;l o w e r lower lower_ b o u n d bound bound 与 u p p e r upper upper_ b o u n d bound bound 是为了方便查找一段区间 我们曾经说过在 STL 里面只要是迭代器区间必须是 左闭右开这时就可以用到 l o w e r lower lower_ b o u n d bound bound 与 u p p e r upper upper_ b o u n d bound bound
举个栗子 int main()
{std::setint myset;for (int i 1; i 10; i)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout e ;}cout endl; 实现查找到的[itlow,itup)包含[30, 60]区间 返回 30这里即返回30//auto itlow myset.lower_bound(30); 返回 60这里即返回70//auto itup myset.upper_bound(60);// 实现查找到的[itlow,itup)包含[25, 55]区间//对应别人来说并不知道容器里面是否有 25 和 55但是查找这段区间的方法与查找30-60的方法一样的// 返回 25这里即返回30auto itlow myset.lower_bound(25);// 返回 55这里即返回60auto itup myset.upper_bound(55);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;return 0;
}2.6 multiset 与 set 的差异 m u l t i s e t multiset multiset 和 s e t set set 的使用基本完全类似主要区别点在于 m u l t i s e t multiset multiset 支持值冗余那么 i n s e r t insert insert / f i n d find find / c o u n t count count / e r a s e erase erase 都围绕着支持值冗余有所差异具体参看下面的样例代码理解。
2.6.1 不再去重
相比 s e t set set 不同的是 m u l t i s e t multiset multiset 是排序但是不去重
int main()
{multisetint s { 4,2,7,2,4,8,4,5,4,9 };auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;return 0;
}2.6.2 find 返回中序的第一个
相比 s e t set set 不同的是 x x x 可能会存在多个 f i n d find find 查找中序遍历的第一个
int main()
{multisetint s { 4,2,7,2,4,8,4,5,4,9 };int x;cin x;auto pos s.find(x);while (pos ! s.end() *pos x){cout *pos ;pos;} cout endl;return 0;
}简单讲一下他是怎么找到中序的第一个的。 查找依然是 O(logN) 算法的查找并不是通过中序的方式遍历一遍这样的话二叉搜索树就失去其意义。 中序的查找规则是左子树 - 根 - 右子树。 假设要找的值是 5 如果找到了一个 5 就再往其左子树找因为中序第一个 5 一定是在左树直到找到了某一个 5 并且其左子树没有 5 表面当前 5 就是中序的第一个 5。 为什么这里要找中序的第一个呢 因为找中序的第一个 x就可以用迭代器不断就可以找到所有的 x
2.6.3 erase 删除所有的 x
相比 s e t set set 不同的是 e r a s e erase erase 给值时会删除所有的 x
int main()
{multisetint s { 4,2,7,2,4,8,4,5,4,9 };for (auto e : s){cout e ;} cout endl;int x;cin x;s.erase(x);for (auto e : s){cout e ;} cout endl;return 0;
}2.6.4 count 个数
相比 s e t set set 不同的是 c o u n t count count 会返回 x x x 的实际个数
int main()
{multisetint s { 4,2,7,2,4,8,4,5,4,9 };for (auto e : s){cout e ;}cout endl;int x;cin x;cout s.count(x) endl;return 0;
}好啦本期关于 s e t set set 与 m u l t i s e t multiset multiset 的知识就介绍到这里啦希望本期博客能对你有所帮助。同时如果有错误的地方请多多指正让我们在 C 的学习路上一起进步
