【C++】map和set使用
前言
有了前面搜索二叉树的基础,那么这篇博客对于map和set两个容器就很好理解使用,让我们来看看map和set到底有什么特性吧
💓 个人主页:小张同学zkf
⏩ 文章专栏:C++
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
1.序列式容器和关联式容器
2.2set类的介绍
template < class T , // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type> class set;
2.3set的构造和迭代器
// empty (1) ⽆参默认构造explicit set ( const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template < class InputIterator >set (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_list<value_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 ();
2.4set的增删查
Member typeskey_type -> The first template parameter (T)value_type -> The first template parameter (T)// 单个数据插⼊,如果已经存在则插⼊失败pair<iterator, bool > insert ( const value_type& val);// 列表插⼊,已经在容器中存在的值不会插⼊void insert (initializer_list<value_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);// 删除 val , val 不存在返回 0 ,存在返回 1size_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 ;
2.5multiset和set的差异
# include <iostream># include <set>using namespace std;int main (){// 相⽐ set 不同的是, multiset 是排序,但是不去重multiset< int > 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 ;}
3.map系列的使用
3.1map和multimap参考文档
链接:https://legacy.cplusplus.com/reference/map/
3.2map类的介绍
template < class Key , // map::key_typeclass T , // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair< const Key,T> > //map::allocator_type> class map;
3.3pair类型介绍
map底层的红⿊树节点中的数据,使⽤pair<Key, T>存储键值对数据。
typedef pair< const 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){}template < class U, class V>pair ( const pair<U,V>& pr): first(pr.first), second(pr.second){}};template < class T1 , class T2 >inline pair<T1,T2> make_pair (T1 x, T2 y){return ( pair <T1,T2>(x,y) );}
3.4map的构造
// empty (1) ⽆参默认构造explicit map ( const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template < class InputIterator >map (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_list<value_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 ();
3.5map的增删查
Member typeskey_type -> The first template parameter (Key)mapped_type -> The second template parameter (T)value_type -> pair < const key_type,mapped_type>// 单个数据插⼊,如果已经 key 存在则插⼊失败 ,key 存在相等 value 不相等也会插⼊失败pair<iterator, bool > insert ( const value_type& val);// 列表插⼊,已经在容器中存在的值不会插⼊void insert (initializer_list<value_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);// 删除 k , k 存在返回 0 ,存在返回 1size_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 ;
3.6map的数据修改
Member typeskey_type -> The first template parameter (Key)mapped_type -> The second template parameter (T)value_type -> pair < const 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::firstset to an iterator pointing to either the newly inserted element or to theelement with an equivalent key in the map . The pair::second element in the pairis set to true if a new element was inserted or false if an equivalent keyalready existed.// insert 插⼊⼀个 pair<key, T> 对象// 1 、如果 key 已经在 map 中,插⼊失败,则返回⼀个 pair<iterator,bool> 对象,返回 pair 对象first 是 key 所在结点的迭代器, second 是 false// 2 、如果 key 不在在 map 中,插⼊成功,则返回⼀个 pair<iterator,bool> 对象,返回 pair 对象first 是新插⼊ key 所在结点的迭代器, second 是 true// 也就是说⽆论插⼊成功还是失败,返回 pair<iterator,bool> 对象的 first 都会指向 key 所在的迭代器// 那么也就意味着 insert 插⼊失败时充当了查找的功能,正是因为这⼀点, insert 可以⽤来实现operator[]// 需要注意的是这⾥有两个 pair ,不要混淆了,⼀个是 map 底层红⿊树节点中存的 pair<key, T> ,另⼀个是 insert 返回值 pair<iterator,bool>pair<iterator, 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 值的引⽤,所以 [] 具备了查找 + 修改的功能pair<iterator, bool > ret = insert ({ k, mapped_type () });iterator it = ret.first;return it->second;}
3.7multimap和map的差异
结束语
set和map的使用总结完了,他们底层都是红黑树,后面详细介绍
OK,感谢观看!!!
原文地址:https://blog.csdn.net/m0_74091744/article/details/142924869
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!