国外域名注册网站,html网站 怎么做seo,xp系统做局域网内网站,wordpress 找不到安装主题文章目录 一、序列式容器和关联式容器二、set系列的使用1、set和multiset参考文档2、set类的介绍3、set的构造和迭代器4、set的增删查5、insert和迭代器遍历使用样例#xff1a;6、find和erase使用样例#xff1a;7、multiset和set的差异 三、map系列的使用1、map和multimap参… 文章目录 一、序列式容器和关联式容器二、set系列的使用1、set和multiset参考文档2、set类的介绍3、set的构造和迭代器4、set的增删查5、insert和迭代器遍历使用样例6、find和erase使用样例7、multiset和set的差异 三、map系列的使用1、map和multimap参考文档2、map类的介绍3、pair类型介绍4、map的构造5、map的增删查6、map的数据修改7、构造遍历及增删查使用样例8、map的迭代器和[]功能样例9、multimap和map的差异 一、序列式容器和关联式容器
前面我们已经接触过STL中的部分容器如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换一下他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章讲解的map和set底层是红黑树红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构 map是key/value搜索场景的结构。
二、set系列的使用
1、set和multiset参考文档
https://legacy.cplusplus.com/reference/set/
2、set类的介绍
set的声明如下T就是set底层关键字的类型set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。一般情况下我们都不需要传后两个模版参数。set底层是用红黑树实现增删查效率是 O(logN)迭代器遍历是走的搜索树的中序所以是有序的。前面部分我们已经学习了vector/list等容器的使用STL容器接口设计高度相似所以这里我们就不需要一个一个的介绍而是直接看文档挑比较重要的接口进行介绍。
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type class set;3、set的构造和迭代器
set的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围forset的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造
explicit set (const key_compare comp key_compare(),const allocator_type alloc allocator_type());// range (2) 迭代器区间构造
template class InputIteratorset (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());// copy (3) 拷⻉构造
set (const set x);// initializer list (5) initializer 列表构造
set (initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());// 迭代器是⼀个双向迭代器
iterator - a bidirectional iterator to const value_type// 正向迭代器
iterator begin();
iterator end();// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();4、set的增删查
关注以下几个接口即可
Member types
key_type - The first template parameter (T)
value_type - The first template parameter (T)
// 单个数据插⼊如果已经存在则插⼊失败
pairiterator,bool insert (const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert (initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert (InputIterator first, InputIterator last);// 查找val返回val所在的迭代器没有找到返回end()
iterator find (const value_type val);
// 查找val返回Val的个数
size_type count (const value_type val) const;// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除valval不存在返回0存在返回1
size_type erase (const value_type val);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type val) const;5、insert和迭代器遍历使用样例
#includeiostream
#includeset
using namespace std;
int main()
{// 去重升序排序setint s;// 去重降序排序给⼀个⼤于的仿函数//setint, greaterint s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){// error C3892: “it”: 不能给常量赋值// *it 1;cout *it ;it;} cout endl;// 插⼊⼀段initializer_list列表值已经存在的值插⼊失败s.insert({ 2,8,3,9 });for (auto e : s){cout e ;} cout endl;setstring strset { sort, insert, add };// 遍历string⽐较ascll码⼤⼩顺序遍历的for (auto e : strset){cout e ;} cout endl;return 0;
}6、find和erase使用样例
#includeiostream
#includeset
using namespace std;
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;// 算法库的查找 O(N)auto pos1 find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 s.find(x);// 利⽤count间接实现快速查找cin x;if (s.count(x)){cout x 在 endl;} else{cout x 不存在 endl;} return 0;
}#includeiostream
#includeset
using namespace std;
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]区间// 返回 30auto itlow myset.lower_bound(30);// 返回 60auto itup myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout e ;} cout endl;return 0;
}7、multiset和set的差异
multiset和set的使用基本完全类似主要区别点在于multiset支持值冗余那么insert/find/count/erase都围绕着支持值冗余有所差异具体参看下面的样例代码理解。
#includeiostream
#includeset
using namespace std;
int main()
{// 相⽐set不同的是multiset是排序但是不去重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;// 相⽐set不同的是x可能会存在多个find查找中序的第⼀个int x;cin x;auto pos s.find(x);while (pos ! s.end() *pos x){cout *pos ;pos;} cout endl;// 相⽐set不同的是count会返回x的实际个数cout s.count(x) endl;// 相⽐set不同的是erase给值时会删除所有的xs.erase(x);for (auto e : s){cout e ;} cout endl;return 0;
}三、map系列的使用
1、map和multimap参考文档
https://legacy.cplusplus.com/reference/map/
2、map类的介绍
map的声明如下Key就是map底层关键字的类型T是map底层value的类型 set默认要求Key支持小于比较如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后两个模版参数。 map底层是用红黑树实现增删查改效率是 O(logN) 迭代器遍历是走的中序所以是按key有序顺序遍历的。
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key,T //
map::allocator_type class map;3、pair类型介绍
map底层的红黑树节点中的数据使用pairKey, T存储键值对数据。
typedef pairconst Key, T value_type;
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){}templateclass U, class Vpair (const pairU,V pr): first(pr.first), second(pr.second){}
};template class T1,class T2
inline pairT1,T2 make_pair (T1 x, T2 y)
{return ( pairT1,T2(x,y) );
}4、map的构造
map的构造我们关注以下几个接口即可。
map的支持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围formap支持修改value数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造
explicit map (const key_compare comp key_compare(),const allocator_type alloc allocator_type());// range (2) 迭代器区间构造
template class InputIteratormap (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());// copy (3) 拷⻉构造
map (const map x);// initializer list (5) initializer 列表构造
map (initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());// 迭代器是⼀个双向迭代器
iterator - a bidirectional iterator to const value_type// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();5、map的增删查
map的增删查关注以下几个接口即可
map增接口插⼊的pair键值对数据跟set所有不同但是查和删的接口只用关键字key跟set是完全类似的不过find返回iterator不仅仅可以确认key在不在还找到key映射的value同时通过迭代还可以修改value。
Member types
key_type - The first template parameter (Key)
mapped_type - The second template parameter (T)
value_type - pairconst key_type,mapped_type// 单个数据插⼊如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pairiterator,bool insert (const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert (initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert (InputIterator first, InputIterator last);// 查找k返回k所在的迭代器没有找到返回end()
iterator find (const key_type k);
// 查找k返回k的个数
size_type count (const key_type k) const;// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除kk存在返回0存在返回1
size_type erase (const key_type k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type k) const;6、map的数据修改
前面我提到map支持修改mapped_type 数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。
map第一个支持修改的方式时通过迭代器迭代器遍历时或者find返回key所在的iterator修改map还有一个非常重要的修改接口operator[]但是operator[]不仅仅支持修改还支持插入数据和查找数据所以他是一个多功能复合接口。
需要注意从内部实现角度map这里把我们传统说的value值给的是T类型typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
Member types
key_type - The first template parameter (Key)
mapped_type - The second template parameter (T)
value_type - pairconst key_type,mapped_type// 查找k返回k所在的迭代器没有找到返回end()如果找到了通过iterator可以修改key对应的mapped_type值
iterator find (const key_type k);// ⽂档中对insert返回值的说明
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.// insert插⼊⼀个pairkey, T对象
// 1、如果key已经在map中插⼊失败则返回⼀个pairiterator,bool对象返回pair对象 first是key所在结点的迭代器second是false
// 2、如果key不在在map中插⼊成功则返回⼀个pairiterator,bool对象返回pair对象 first是新插⼊key所在结点的迭代器second是true
// 也就是说⽆论插⼊成功还是失败返回pairiterator,bool对象的first都会指向key所在的迭代器
// 那么也就意味着insert插⼊失败时充当了查找的功能正是因为这⼀点insert可以⽤来实现operator[]
// 需要注意的是这⾥有两个pair不要混淆了⼀个是map底层红⿊树节点中存的pairkey, T另⼀个是insert返回值pairiterator,bool
pairiterator,bool insert (const value_type val);mapped_type operator[] (const key_type k);// operator的内部实现
mapped_type operator[] (const key_type k)
{// 1、如果k不在map中insert会插⼊k和mapped_type默认值同时[]返回结点中存储mapped_type值的引⽤那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊修改功能// 2、如果k在map中insert会插⼊失败但是insert返回pair对象的first是指向key结点的迭代器返回值同时[]返回结点中存储mapped_type值的引⽤所以[]具备了查找修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second;
}7、构造遍历及增删查使用样例
#includeiostream
#includemap
using namespace std;
int main()
{// initializer_list构造及迭代遍历mapstring, string dict { {left, 左边}, {right, 右边},{insert, 插⼊},{ string, 字符串 } };//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){//cout (*it).first :(*it).second endl;// map的迭代基本都使⽤operator-,这⾥省略了⼀个-// 第⼀个-是迭代器运算符重载返回pair*第⼆个箭头是结构指针解引⽤取pair数据//cout it.operator-()-first : it.operator-()-second endl;cout it-first : it-second endl;it;} cout endl;// insert插⼊pair对象的4种⽅式对⽐之下最后⼀种最⽅便pairstring, string kv1(first, 第⼀个);dict.insert(kv1);dict.insert(pairstring, string(second, 第⼆个));dict.insert(make_pair(sort, 排序));dict.insert({ auto, ⾃动的 });// left已经存在插⼊失败dict.insert({ left, 左边剩余 });// 范围for遍历for (const auto e : dict){cout e.first : e.second endl;} cout endl;string str;while (cin str){auto ret dict.find(str);if (ret ! dict.end()){cout - ret-second endl;} else{cout ⽆此单词请重新输⼊ endl;}} // erase等接⼝跟set完全类似这⾥就不演⽰讲解了return 0;
}8、map的迭代器和[]功能样例
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{// 利⽤find和iterator修改功能统计⽔果出现的次数string arr[] { 苹果, 西⽠, 苹果, 西⽠, 苹果, 苹果, 西⽠,苹果, ⾹蕉, 苹果, ⾹蕉 };mapstring, int countMap;for (const auto str : arr){// 先查找⽔果在不在map中// 1、不在说明⽔果第⼀次出现则插⼊{⽔果, 1}// 2、在则查找到的节点中⽔果对应的次数auto ret countMap.find(str);if (ret countMap.end()){countMap.insert({ str, 1 });} else{ret-second;}} for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0;
}
///
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{// 利⽤[]插⼊修改功能巧妙实现统计⽔果出现的次数string arr[] { 苹果, 西⽠, 苹果, 西⽠, 苹果, 苹果, 西⽠,苹果, ⾹蕉, 苹果, ⾹蕉 };mapstring, int countMap;for (const auto str : arr){// []先查找⽔果在不在map中// 1、不在说明⽔果第⼀次出现则插⼊{⽔果, 0}同时返回次数的引⽤⼀下就变成1次了// 2、在则返回⽔果对应的次数countMap[str];} for (const auto e : countMap){cout e.first : e.second endl;} cout endl;return 0;
}#includeiostream
#includemap
#includestring
using namespace std;
int main()
{mapstring, string dict;dict.insert(make_pair(sort, 排序));// key不存在-插⼊ {insert, string()}dict[insert];// 插⼊修改dict[left] 左边;// 修改dict[left] 左边、剩余;// key存在-查找cout dict[left] endl;return 0;
}9、multimap和map的差异
multimap和map的使用基本完全类似主要区别点在于multimap支持关键值key冗余那么insert/find/count/erase都围绕着支持关键值key冗余有所差异这里跟set和multiset完全一样比如find时有多个key返回中序第一个。其次就是multimap不支持[]因为支持key冗余[]就只能支持插入了不能支持修改。
