广州大题小做考研网站,提供手机网站开发,怎么制作应用软件,资阳的网站建设目录 一、关联式容器二、键值对三、pair3.1 pair的常用接口说明3.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.2 [有参构造函数 / 拷贝构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.3 [有参构造函数](htt… 目录 一、关联式容器二、键值对三、pair3.1 pair的常用接口说明3.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.2 [有参构造函数 / 拷贝构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.3 [有参构造函数](https://legacy.cplusplus.com/reference/utility/pair/pair/)3.1.4 [make_pair()函数](https://legacy.cplusplus.com/reference/utility/make_pair/) 四、树形结构的关联式容器4.1 标准库中的set4.1.1 set的介绍4.1.2 set的常用接口说明4.1.2.1 set对象的常见构造4.1.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/set/set/set/)4.1.2.1.2 [有参构造函数使用迭代器进行初始化构造](https://legacy.cplusplus.com/reference/set/set/set/)4.1.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/set/set/set/) 4.1.2.2 set iterator 的使用4.1.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/set/set/begin/) [end()函数](https://legacy.cplusplus.com/reference/set/set/end/)4.1.2.2.2 [rbegin()函数](https://legacy.cplusplus.com/reference/set/set/rbegin/) [rend()函数](https://legacy.cplusplus.com/reference/set/set/rend/) 4.1.2.3 set对象的容量操作4.1.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/set/set/size/)4.1.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/set/set/empty/) 4.1.2.4 set对象的增删查改及访问4.1.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/set/set/insert/)4.1.2.4.2 [erase()函数](https://legacy.cplusplus.com/reference/set/set/erase/)4.1.2.4.3 [swap()函数](https://legacy.cplusplus.com/reference/set/set/swap/)4.1.2.4.4 [clear()函数](https://legacy.cplusplus.com/reference/set/set/clear/)4.1.2.4.5 [find()函数](https://legacy.cplusplus.com/reference/set/set/find/)4.1.2.4.6 [count()函数](https://legacy.cplusplus.com/reference/set/set/count/)4.1.2.4.7 [lower_bound()函数](https://legacy.cplusplus.com/reference/set/set/lower_bound/)4.1.2.4.8 [upper_bound()函数](https://legacy.cplusplus.com/reference/set/set/upper_bound/)4.1.2.4.9 [equal_range()函数](https://legacy.cplusplus.com/reference/set/set/equal_range/) 4.2 标准库中的multiset4.2.1 multiset的介绍4.2.2 multiset的常用接口说明4.2.2.1 multiset对象的常用构造4.2.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/set/multiset/multiset/)4.2.2.1.2 [有参构造函数使用迭代器进行初始化构造](https://legacy.cplusplus.com/reference/set/multiset/multiset/)4.2.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/set/multiset/multiset/) 4.2.2.2 multiset iterator 的使用4.2.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/set/multiset/begin/) [end()函数](https://legacy.cplusplus.com/reference/set/multiset/end/)4.2.2.2.2 [rbegin()函数](https://legacy.cplusplus.com/reference/set/multiset/rbegin/) [rend()函数](https://legacy.cplusplus.com/reference/set/multiset/rend/) 4.2.2.3 multiset 对象的容量操作4.2.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/set/multiset/size/)4.2.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/set/multiset/empty/) 4.2.2.4 multiset 对象的增删查改及访问4.2.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/set/multiset/insert/)4.2.2.4.2 [erase()函数](https://legacy.cplusplus.com/reference/set/multiset/erase/)4.2.2.4.3 [swap()函数](https://legacy.cplusplus.com/reference/set/multiset/swap/)4.2.2.4.4 [clear()函数](https://legacy.cplusplus.com/reference/set/multiset/clear/)4.2.2.4.5 [find()函数](https://legacy.cplusplus.com/reference/set/multiset/find/)4.2.2.4.6 [count()函数](https://legacy.cplusplus.com/reference/set/multiset/count/)4.2.2.4.7 [lower_bound()函数](https://legacy.cplusplus.com/reference/set/multiset/lower_bound/)4.2.2.4.8 [upper_bound()函数](https://legacy.cplusplus.com/reference/set/multiset/upper_bound/)4.2.2.4.9 [equal_range()函数](https://legacy.cplusplus.com/reference/set/multiset/equal_range/) 4.3 标准库中的map4.3.1 map的介绍4.3.2 map的常用接口说明4.3.2.1 map对象的常用构造4.3.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/map/map/map/)4.3.2.1.2 [有参构造函数使用迭代器进行初始化构造](https://legacy.cplusplus.com/reference/map/map/map/)4.3.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/map/map/map/) 4.3.2.2 map iterator 的使用4.3.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/map/map/begin/) [end()函数](https://legacy.cplusplus.com/reference/map/map/end/)4.3.2.2.2 [rbegin()函数](https://legacy.cplusplus.com/reference/map/map/rbegin/) [rend()函数](https://legacy.cplusplus.com/reference/map/map/rend/) 4.3.2.3 map对象的容量操作4.3.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/map/map/empty/)4.3.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/map/map/empty/) 4.3.2.4 map对象的增删查改及访问4.3.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/map/map/insert/)4.3.2.4.2 [erase()函数](https://legacy.cplusplus.com/reference/map/map/erase/)4.3.2.4.3 [swap()函数](https://legacy.cplusplus.com/reference/map/map/swap/)4.3.2.4.4 [clear()函数](https://legacy.cplusplus.com/reference/map/map/clear/)4.3.2.4.5 [find()函数](https://legacy.cplusplus.com/reference/map/map/find/)4.3.2.4.6 [count()函数](https://legacy.cplusplus.com/reference/map/map/count/)4.3.2.4.7 [lower_bound()函数](https://legacy.cplusplus.com/reference/map/map/lower_bound/)4.3.2.4.8 [upper_bound()函数](https://legacy.cplusplus.com/reference/map/map/upper_bound/)4.3.2.4.9 [equal_range()函数](https://legacy.cplusplus.com/reference/map/map/equal_range/)4.3.2.4.10 [operator[]](https://legacy.cplusplus.com/reference/map/map/operator%5B%5D/) 4.4 标准库中的multimap4.4.1 multimap的介绍4.4.2 multimap的常用接口说明4.4.2.1 multimap对象的常用构造4.4.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/map/multimap/multimap/)4.4.2.1.2 [有参构造函数使用迭代器进行初始化构造](https://legacy.cplusplus.com/reference/map/multimap/multimap/)4.4.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/map/multimap/multimap/) 4.4.2.2 multimap iterator 的使用4.4.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/map/multimap/begin/) [end()函数](https://legacy.cplusplus.com/reference/map/multimap/end/)4.4.2.2.2 [rbegin()函数](https://legacy.cplusplus.com/reference/map/multimap/rbegin/) [rend()函数](https://legacy.cplusplus.com/reference/map/multimap/rend/) 4.4.2.3 multimap 对象的容量操作4.4.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/map/multimap/size/)4.4.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/map/multimap/empty/) 4.4.2.4 multimap对象的增删查改及访问4.4.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/map/multimap/insert/)4.4.2.4.2 [erase()函数](https://legacy.cplusplus.com/reference/map/multimap/erase/)4.4.2.4.3 [swap()函数](https://legacy.cplusplus.com/reference/map/multimap/swap/)4.4.2.4.4 [clear()函数](https://legacy.cplusplus.com/reference/map/multimap/clear/)4.4.2.4.5 [find()函数](https://legacy.cplusplus.com/reference/map/multimap/find/)4.4.2.4.6 [count()函数](https://legacy.cplusplus.com/reference/map/multimap/count/)4.4.2.4.7 [lower_bound()函数](https://legacy.cplusplus.com/reference/map/multimap/lower_bound/)4.4.2.4.8 [upper_bound()函数](https://legacy.cplusplus.com/reference/map/multimap/upper_bound/)4.4.2.4.9 [equal_range()函数](https://legacy.cplusplus.com/reference/map/multimap/equal_range/) 五、map和set在OJ中的应用5.1 [692. 前K个高频单词](https://leetcode.cn/problems/top-k-frequent-words/description/)5.2 [349. 两个数组的交集](https://leetcode.cn/problems/intersection-of-two-arrays/submissions/) 结尾 一、关联式容器
在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 二、键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义
using namespace std;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){}
};三、pair
pair的文档介绍
pair 是 C 标准库中的一个模板类用于存储两个对象的有序对。通常情况下pair 用于将两个不同类型的对象组合成一个单元并且允许这两个对象分别访问。
3.1 pair的常用接口说明
3.1.1 无参构造函数
pair();int main()
{pair string, double p; cout p.first p.second endl;return 0;
}3.1.2 有参构造函数 / 拷贝构造函数
templateclass U, class V pair (const pairU,V pr);
当参数不匹配时为有参构造函数
当参数匹配时为拷贝构造函数3.1.3 有参构造函数
pair (const first_type a, const second_type b);int main()
{pair string, double p(Love, 5.20); cout p.first p.second endl;;return 0;
}3.1.4 make_pair()函数
template class T1, class T2pairT1,T2 make_pair (T1 x, T2 y);template class T1, class T2
pairT1, T2 make_pair(T1 x, T2 y)
{return (pairT1, T2(x, y));
}四、树形结构的关联式容器
根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
4.1 标准库中的set
4.1.1 set的介绍
set的文档介绍
set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。
set的模板参数列表介绍 T: set中存放元素的类型实际在底层存储value, value的键值对。
Compareset中元素默认按照小于来比较
Allocset中元素空间的管理方式使用STL提供的空间配置器管理目前不需要掌握 4.1.2 set的常用接口说明
4.1.2.1 set对象的常见构造
4.1.2.1.1 无参构造函数
set (const key_compare comp key_compare());int main()
{setint s;return 0;
}4.1.2.1.2 有参构造函数使用迭代器进行初始化构造
template class InputIteratorset (InputIterator first, InputIterator last,const key_compare comp key_compare());int main()
{string s(I Love Y);setint ss(s.begin(), s.end());for (auto e : ss){cout e ;}cout endl;return 0;
}4.1.2.1.3 拷贝构造函数
set (const set x);int main()
{string s(I Love Y);setint ss1(s.begin(), s.end());setint ss2(ss1);for (auto e : ss2){cout e ;}cout endl;return 0;
}4.1.2.2 set iterator 的使用
4.1.2.2.1 begin()函数 end()函数 iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iteratorint main()
{string s(I Love Y);setint ss1(s.begin(), s.end());setint::iterator it ss1.begin();while (it ! ss1.end()){cout *it ;it;}cout endl;return 0;
}4.1.2.2.2 rbegin()函数 rend()函数 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator int main()
{string s(I Love Y);setint ss1(s.begin(), s.end());setint::reverse_iterator it ss1.rbegin();while (it ! ss1.rend()){cout *it ;it;}cout endl;return 0;
}4.1.2.3 set对象的容量操作
4.1.2.3.1 size()函数
size_type size() const; 获取数据个数4.1.2.3.2 empty()函数
bool empty() const; 判断是否为空int main()
{setint ss;cout ss.empty() endl;string s(I Love Y);setint ss1(s.begin(), s.end());cout ss1.empty() endl;return 0;
}4.1.2.4 set对象的增删查改及访问
4.1.2.4.1 insert()函数
pairiterator,bool insert (const value_type val);
在set中插入一个元素val若set中有这个元素插入失败,则返回一个pair对象
pair.first原来val元素位置的迭代器,pair.second false若set中没有这个元素插入成功,则返回一个pair对象
pair.first新插入val元素位置的迭代器,pair.second trueiterator insert (iterator position, const value_type val);
不建议使用在position位置插入一个val并返回插入元素位置的迭代器template class InputIteratorvoid insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素int main()
{setint s;string ss(I Love Y);/*pairiterator, bool insert(const value_type val);在set中插入一个元素val*/pairsetint::iterator, bool ret;for (int i 0; i 14; i 2){ret s.insert(i % 10);cout 插入元素 *ret.first 是否成功 ret.second endl;}for (auto e : s){cout e ;}cout endl;// 插入一段迭代器区间的元素s.insert(ss.begin(), ss.end());for (auto e : s){cout e ;}cout endl;return 0;
}4.1.2.4.2 erase()函数
void erase (iterator position);
删除position位置的元素size_type erase (const value_type val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素int main()
{setint s;for (int i 0; i 10; i){s.insert(i);}for (auto e : s){ cout e ; }cout endl;setint::iterator it s.begin();s.erase(it);for (auto e : s){ cout e ; }cout endl;// 删除元素val并返回val的个数s.erase(5);for (auto e : s){ cout e ; }cout endl;// 删除一段迭代器区间内的元素s.erase(s.begin() , --s.end());for (auto e : s){ cout e ; }cout endl;return 0;
}4.1.2.4.3 swap()函数
void swap (set x);
交换两个set的数据空间int main()
{setint s1;setint s2;for (int i 1; i 10; i 2){ s1.insert(i); }for (int i 0; i 10; i 2){ s2.insert(i); }for (auto e : s1){ cout e ; }cout endl;for (auto e : s2){ cout e ; }cout endl;s1.swap(s2);for (auto e : s1){ cout e ; }cout endl;for (auto e : s2){ cout e ; }cout endl;return 0;
} 4.1.2.4.4 clear()函数
void clear();
清除set中的有效数据int main()
{setint s;for (int i 1; i 10; i 2){ s.insert(i); }s.clear();return 0;
} 4.1.2.4.5 find()函数
iterator find (const value_type val) const;
返回set中为val元素位置的迭代器int main()
{setint s;for (int i 1; i 10; i 2){s.insert(i);}setint::iterator it s.find(5);cout *it endl;return 0;
}4.1.2.4.6 count()函数
size_type count (const value_type val) const;
返回set中为val元素的个数
由于set并不允许相同的元素存在
所以set中所有元素的个数都是1int main()
{setint s;for (int i 1; i 10; i 2){s.insert(i);}for (auto e : s){cout e 的个数 s.count(e) endl;}return 0;
}4.1.2.4.7 lower_bound()函数
iterator lower_bound (const value_type val) const;
返回第一个 val 对象位置的迭代器int main()
{setint s;// 10 20 30 40 50for (int i 1; i 6; i){s.insert(i*10);}setint::iterator it s.lower_bound(30);cout *it endl;return 0;
}4.1.2.4.8 upper_bound()函数
iterator upper_bound (const value_type val) const;
返回第一个 val 对象位置的迭代器int main()
{setint s;// 10 20 30 40 50for (int i 1; i 6; i){s.insert(i * 10);}setint::iterator it s.upper_bound(30);cout *it endl;return 0;
}4.1.2.4.9 equal_range()函数
pairiterator,iterator equal_range (const value_type val) const;
返回一个pair对象
pair.first 第一个 val 对象位置的迭代器
pair.second 第一个 val 对象位置的迭代器int main()
{setint s;// 10 20 30 40 50for (int i 1; i 6; i){s.insert(i * 10);}pairsetint::iterator, setint::iterator p s.equal_range(30);cout *p.first * p.second endl;return 0;
}4.2 标准库中的multiset
4.2.1 multiset的介绍
multiset的文档介绍
multiset是按照特定顺序存储元素的容器其中元素是可以重复的。multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列。multiset底层结构为二叉搜索树(红黑树)。
注意
mtltiset的插入接口中只需要插入即可与set的区别是multiset中的元素可以重复set是中value是唯一的使用迭代器对multiset中的元素进行遍历可以得到有序的序列multiset中的元素不能修改在multiset中找某个元素时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)multiset的作用可以对元素进行排序
4.2.2 multiset的常用接口说明
注意multiset的接口与set的接口基本相似可以参考set的使用那么下面multiset将不会进行演示使用。
4.2.2.1 multiset对象的常用构造
4.2.2.1.1 无参构造函数
multiset (const key_compare comp key_compare());4.2.2.1.2 有参构造函数使用迭代器进行初始化构造
template class InputIteratormultiset (InputIterator first, InputIterator last,const key_compare comp key_compare());4.2.2.1.3 拷贝构造函数
multiset (const multiset x);4.2.2.2 multiset iterator 的使用
4.2.2.2.1 begin()函数 end()函数 iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator4.2.2.2.2 rbegin()函数 rend()函数 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 4.2.2.3 multiset 对象的容量操作
4.2.2.3.1 size()函数
size_type size() const;
获取数据个数4.2.2.3.2 empty()函数
bool empty() const; 判断是否为空4.2.2.4 multiset 对象的增删查改及访问
4.2.2.4.1 insert()函数
iterator insert (const value_type val);
在multiset中插入一个元素val并返回插入元素位置的迭代器
由于multiset可以存在相同的元素那么就不存在插入失败的情况iterator insert (iterator position, const value_type val);
不建议使用在position位置插入一个val并返回插入元素位置的迭代器template class InputIteratorvoid insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素4.2.2.4.2 erase()函数
void erase (iterator position);
删除position位置的元素size_type erase (const value_type val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素4.2.2.4.3 swap()函数
void swap (multiset x);
交换两个multiset的数据空间4.2.2.4.4 clear()函数
void clear();
清除multiset中的有效数据4.2.2.4.5 find()函数
iterator find (const value_type val) const;
返回multiset中为val元素位置的迭代器4.2.2.4.6 count()函数
size_type count (const value_type val) const;
返回multiset中为val元素的个数multiset中可以存在相同的元素4.2.2.4.7 lower_bound()函数
iterator lower_bound (const value_type val) const;
返回第一个 val 对象位置的迭代器4.2.2.4.8 upper_bound()函数
iterator upper_bound (const value_type val) const;
返回第一个 val 对象位置的迭代器4.2.2.4.9 equal_range()函数
pairiterator,iterator equal_range (const value_type val) const;
返回一个pair对象
pair.first 第一个 val 对象位置的迭代器
pair.second 第一个 val 对象位置的迭代器4.3 标准库中的map
4.3.1 map的介绍
map的文档介绍
map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
map的模板参数列表介绍 key: 键值对中key的类型
T 键值对中value的类型
Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器目前不需要掌握 4.3.2 map的常用接口说明
4.3.2.1 map对象的常用构造
4.3.2.1.1 无参构造函数
map (const key_compare comp key_compare());int main()
{mapint, int m;return 0;
} 4.3.2.1.2 有参构造函数使用迭代器进行初始化构造
template class InputIteratormap (InputIterator first, InputIterator last,const key_compare comp key_compare());map有序关联容器的构造函数通常也不接受其他容器类型的迭代器来直接构造。map 要求它的元素按照键key的顺序进行排序因此在构造时它期望提供的元素已经按照键的升序排列。
如果尝试使用未排序的迭代器范围例如来自 vector 或 list 的迭代器来构造 map将会导致编译错误或未定义行为因为 map 无法保证这些元素的排序。
如果想要从一个容器如 vector创建一个 map你需要确保容器中的元素已经按照键的升序排列然后你可以使用迭代器范围来构造 map。
int main()
{vectorpairint, int v({ {5,5},{13,13},{1,1} });sort(v.begin(), v.end());mapint,int m1(v.begin(), v.end());mapint, int m2(m1.begin(), m1.end());return 0;
}4.3.2.1.3 拷贝构造函数
map (const map x);int main()
{mapint, int m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));mapint, int m2(m1);return 0;
}4.3.2.2 map iterator 的使用
4.3.2.2.1 begin()函数 end()函数 iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iteratorint main()
{mapint, int m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));mapint, int::iterator it m1.begin();while(it ! m1.end()){cout first it-first second: it-second endl;it;}return 0;
}4.3.2.2.2 rbegin()函数 rend()函数 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator int main()
{mapint, int m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));mapint, int::reverse_iterator it m1.rbegin();while (it ! m1.rend()){cout first it-first second: it-second endl;it;}return 0;
}4.3.2.3 map对象的容量操作
4.3.2.3.1 size()函数
size_type size() const;
获取数据个数int main()
{mapint, int m1;cout m1.size() endl;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));cout m1.size() endl;return 0;
}4.3.2.3.2 empty()函数
bool empty() const; 判断是否为空int main()
{mapint, int m1;cout m1.empty() endl;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));cout m1.empty() endl;return 0;
}4.3.2.4 map对象的增删查改及访问
4.3.2.4.1 insert()函数
pairiterator,bool insert (const value_type val);
在map中插入键值对val若map中有这个键值对插入失败,则返回一个pair对象
pair.first原来val位置的迭代器,pair.second false若map中没有这个键值对插入成功,则返回一个pair对象
pair.first新插入val位置的迭代器,pair.second trueiterator insert (iterator position, const value_type val);
不建议使用在position位置插入一个val并返回插入键值对位置的迭代器template class InputIteratorvoid insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素int main()
{mapint,int m1;/*pairiterator, bool insert(const value_type val);在set中插入一个元素val*/pairmapint,int::iterator, bool ret;for (int i 0; i 14; i 2){ret m1.insert(make_pair(i % 10, i % 10));cout 插入key ret.first-first 是否成功 ret.second endl;}for (auto e : m1){cout first e.first second e.second endl;}cout endl;// 插入一段迭代器区间的元素mapint, int m2;m2.insert(make_pair(520, 520));m2.insert(make_pair(1314, 1314));cout insert前m2中的元素 endl;for (auto e : m2){cout first e.first second e.second endl;}cout endl;m2.insert(m1.begin(), m1.end());cout insert后m2中的元素 endl;for (auto e : m2){cout first e.first second e.second endl;}cout endl;return 0;
}4.3.2.4.2 erase()函数
void erase (iterator position);
删除position位置的元素size_type erase (const value_type val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素int main()
{mapint, int m1;/*pairiterator, bool insert(const value_type val);在map中插入一个元素val*/for (int i 0; i 14; i 2){m1.insert(make_pair(i % 10, i % 10));}for (auto e : m1){cout first e.first second e.second endl;}cout endl;// 删除迭代器位置的元素m1.erase(m1.begin());for (auto e : m1){cout first e.first second e.second endl;}cout endl;// 删除元素并返回元素个数m1.erase(6);for (auto e : m1){cout first e.first second e.second endl;}cout endl;// 删除一段迭代器区间内的元素m1.erase(m1.begin(),--m1.end());for (auto e : m1){cout first e.first second e.second endl;}cout endl;return 0;
}4.3.2.4.3 swap()函数
void swap (map x);
交换两个map的数据空间int main()
{mapint,int m1;for (int i 0; i 14; i 2){m1.insert(make_pair(i % 10, i % 10));}cout swap前m1中的元素 endl;for (auto e : m1){cout first e.first second e.second endl;}cout endl;mapint, int m2;m2.insert(make_pair(520, 520));m2.insert(make_pair(1314, 1314));cout swap前m2中的元素 endl;for (auto e : m2){cout first e.first second e.second endl;}cout endl;m1.swap(m2);cout swap后m1中的元素 endl;for (auto e : m1){cout first e.first second e.second endl;}cout endl;cout swap后m2中的元素 endl;for (auto e : m2){cout first e.first second e.second endl;}cout endl;return 0;
} 4.3.2.4.4 clear()函数
void clear();
清除map中的有效数据int main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}m.clear();return 0;
} 4.3.2.4.5 find()函数 iterator find (const key_type k);
const_iterator find (const key_type k) const;
返回map中为关键码为k位置的迭代器int main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}mapint,int::iterator it m.find(6);cout first it-first second it-second endl;return 0;
}4.3.2.4.6 count()函数
size_type count (const key_type k) const;
返回map中为k元素的个数
由于map并不允许相同的元素存在
所以map中所有元素的个数都是1int main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}for (auto e : m){cout e.first 的个数 m.count(e.first) endl;}return 0;
}4.3.2.4.7 lower_bound()函数 iterator lower_bound (const key_type k);
const_iterator lower_bound (const key_type k) const;
返回第一个关键码 k对象位置的iterator/const_iteratorint main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}mapint, int::iterator it m.lower_bound(6);cout first it-first second it-second endl;return 0;
}4.3.2.4.8 upper_bound()函数 iterator upper_bound (const key_type k);
const_iterator upper_bound (const key_type k) const;
返回第一个关键码 k 对象位置的iterator/const_iteratorint main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}mapint, int::iterator it m.upper_bound(6);cout first it-first second it-second endl;return 0;
}4.3.2.4.9 equal_range()函数
pairconst_iterator,const_iterator equal_range (const key_type k) const;
pairiterator,iterator equal_range (const key_type k);
返回一个pair对象
pair.first 第一个关键码 k 对象位置的iterator/const_iterator
pair.second 第一个关键码 k 对象位置的iterator/const_iteratorint main()
{mapint, int m;for (int i 0; i 14; i 2){m.insert(make_pair(i % 10, i % 10));}pairmapint, int::iterator, mapint, int::iteratorret m.equal_range(6);cout first ret.first-first second ret.first-second endl;cout first ret.second-first second ret.second-second endl;return 0;
}4.3.2.4.10 operator[]
mapped_type operator[] (const key_type k);
返回关键码为key对应的value的引用mapped_type operator[] (const key_type k)
{return (*((this-insert(make_pair(k,mapped_type()))).first)).second
}int main()
{mapint, int m;m.insert(make_pair(5, 5));// 若map中有这个元素那么就返回key对应value的引用cout operator[]: m[5] endl;// 若map中没有这个元素那么map中将会插入这个元素// 使用默认构造初始化value并返回cout operator[]: m[10] endl;for (auto e : m){cout first e.first second e.second endl;}return 0;
}【总结】
map中的的元素是键值对map中的key是唯一的并且不能修改默认按照小于的方式对key进行比较map中的元素如果用迭代器去遍历可以得到一个有序的序列map的底层为平衡搜索树(红黑树)查找效率比较高 O ( l o g 2 N ) O(log_2 N) O(log2N)支持[]操作符operator[]中实际进行插入查找。 4.4 标准库中的multimap
4.4.1 multimap的介绍
multimap的文档介绍
Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key,value其中多个键值对之间的key是可以重复的。在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对:typedef pairconst Key, T value_type;在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的。multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。multimap在底层用二叉搜索树(红黑树)来实现。 注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。
注意
multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较multimap中没有重载operator[]操作因为multimap中的key可以重复如果重载operator[]操作那么找到的结果是未定义的。使用时与map包含的头文件相同 4.4.2 multimap的常用接口说明
注意multimap的接口与map的接口基本相似可以参考map的使用那么下面multimap将不会进行演示使用。
4.4.2.1 multimap对象的常用构造
4.4.2.1.1 无参构造函数
multimap (const key_compare comp key_compare());4.4.2.1.2 有参构造函数使用迭代器进行初始化构造
template class InputIteratormultimap (InputIterator first, InputIterator last,const key_compare comp key_compare());4.4.2.1.3 拷贝构造函数
multimap (const multimap x);4.4.2.2 multimap iterator 的使用
4.4.2.2.1 begin()函数 end()函数 iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator4.4.2.2.2 rbegin()函数 rend()函数 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 4.4.2.3 multimap 对象的容量操作
4.4.2.3.1 size()函数
size_type size() const;
获取数据个数4.4.2.3.2 empty()函数
bool empty() const; 判断是否为空4.4.2.4 multimap对象的增删查改及访问
4.4.2.4.1 insert()函数
iterator insert (const value_type val);
在multimap中插入一个键值对val并返回插入元素位置的迭代器
由于multimap可以存在相同的元素那么就不存在插入失败的情况iterator insert (iterator position, const value_type val);
不建议使用在position位置插入一个val并返回插入val位置的迭代器template class InputIteratorvoid insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素4.4.2.4.2 erase()函数
void erase (iterator position);
删除position位置的元素size_type erase (const value_type val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素4.4.2.4.3 swap()函数
void swap (multiset x);
交换两个multimap的数据空间4.4.2.4.4 clear()函数
void clear();
清除multimap中的有效数据4.4.2.4.5 find()函数 iterator find (const key_type k);
const_iterator find (const key_type k) const;
返回multimap中关键码为k位置的iterator/const_iterator4.4.2.4.6 count()函数
size_type count (const key_type k) const;
返回multimap中关键码为k元素的个数multimap中可以存在相同的元素4.4.2.4.7 lower_bound()函数 iterator lower_bound (const key_type k);
const_iterator lower_bound (const key_type k) const;
返回第一个关键码 k 对象位置的iterator/const_iterator4.4.2.4.8 upper_bound()函数 iterator upper_bound (const key_type k);
const_iterator upper_bound (const key_type k) const;
返回第一个关键码 k 对象位置的iterator/const_iterator4.4.2.4.9 equal_range()函数
pairconst_iterator,const_iterator equal_range (const key_type k) const;
pairiterator,iterator equal_range (const key_type k);
返回一个pair对象
pair.first 第一个关键码 k 对象位置的iterator/const_iterator
pair.second 第一个关键码 k 对象位置的iterator/const_iterator五、map和set在OJ中的应用
5.1 692. 前K个高频单词
给定一个单词列表 words 和一个整数 k 返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序 排序。
思路定义一个对象mapstring, int Mapstring用来记录单词int用来记录单词出现的次数。遍历vector并在Map中插入由于Map是按照单词的大小进行比较的再定义vectorpairstring, int tmp并用Map的迭代器区间对tmp进行初始化再使用单词出现的次数进行排序。需要注意的是pair比较大小的时候是使用pair.first进行比较的而单词的次数记录在pair.second中所以我们需要自己写一个仿函数进行比较单词出现次数多的在前面单词小的在前面。由于答案只需要单词那么再定义一个对象vectorstring ans记录答案访问tmp中前k个元素访问其中的单词并插入到ans中最后输出ans完成本题。
class Solution {
public:struct Cmp{bool operator()(const pairstring, int p1 ,const pairstring, int p2){// 出现频率高且按字典顺序return p1.second p2.second || (p1.second p2.second p1.first p2.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring, int Map;for(auto x : words){Map[x];}// 这里的vector是用来存储pair对象的vectorpairstring, int tmp(Map.begin(),Map.end());sort(tmp.begin() , tmp.end(), Cmp());// 需要输出vectorstring ,将pair中的string提取出来vectorstring ans;for(int i 0 ; i k ; i){ans.push_back(tmp[i].first);}return ans;}
};5.2 349. 两个数组的交集
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
思路set能对数据进行排序和去重定义两个set对象s1s2使用nums1和nums2的迭代器区间对set进行初始化定义vectorint ans记录答案定义两个set的迭代器it1和it2分别记录s1和s2的begin()对两组数据同时遍历迭代器指向元素小的因为小的元素不可能在和另外一组数据有相同的值若迭代器指向的元素相等将元素尾差到ans中有一个迭代器走到最后则说明两组元素不可能再有相同的值了将ans返回就能完成本道题。
上面是两个数组的交集的思路而两个数组的差集的思路与交集的思路只有在元素入ans的时候有区别。对两组数据同时遍历迭代器指向元素小的入ans并且迭代器因为小的元素不可能在和另外一组数据有相同的值若迭代器指向的元素相等两迭代器同时将ans返回就能实现得到两个数组的差集了。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {// 将两分数据进行去重setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());vectorint ans;setint::iterator it1 s1.begin();setint::iterator it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){// 两个数中小的迭代器// 两数相等时将数字尾差到vector中// 两迭代器同时if(*it1 *it2){it2;}else if(*it1 *it2){it1;}else{ans.push_back(*it1);it1;it2;}}return ans;}
};结尾
如果有什么建议和疑问或是有什么错误大家可以在评论区中提出。 希望大家以后也能和我一起进步 如果这篇文章对你有用的话希望大家给一个三连支持一下
