一.关联式容器的介绍
C++STL包含了序列式容器和关联式容器:
- 序列式容器里面存储的是元素本身,其底层是线性的数据结构,就譬如我们之前学习的vector,list,deque等等。
- 关联式容器里面存储的是<key,value>的键值对,在数据检索时比序列式容器效率更高。就譬如我们现在要学习的map和set等。
这里需要给大家提醒的一点是:
我们之前学习的queue、stack、priority_queue属于容器适配器,他们会使用别的容器来适配。
下面,我们开始介绍下键值对这个东西。
键值对是用来表示一一对应关系的一种结果,这个结构中一般是包含两个成员变量key和value。
- key表示键值。
- value表示与key对应的信息。
二.键值对
在SGI-STL中,关于键值对的定义如下所示:
template<class K,class V>
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中的first表示键值,second则表示实值,在给关联式容器插入数据时,会构建pair对象
就譬如以下代码,就可以构建出一个键值key为string,实值value为int的匿名键值的键值对pair对象。
pair<string,int>("haha",1);
这样的写法有些繁琐,因此库中设计了一个函数模板make_pair,可以根据传入的参数调用pair构建对象并返回,如下:
make_pair("hehe",123);
下面,我们给出make_pair的定义:
template<class T1,class T2>
pair<T1,T2> make_pair(T1 x,T2 y)
{return (pair<T1,T2>(x,y));
}
这个函数在实际应用时,会被编译器优化为内联函数,因此不会产生太大的消耗。
比如我们若是要创建一个字典,那么这个字典中的英文单词与中文含义应该是一一对应的,也就是说,我们应该能够通过单词找到它对应的中文含义。
这样的情况,我们就可以利用键值对来完成这个任务。
三.set的使用
3.1set的定义
在我们之前介绍二叉搜索树时,我们大家可以发现其的模板参数只用了一个T1,而我们的set的底层就是一种特殊的二叉树,我们可以将其理解为只有一个实值value的特殊模型。
下图为cpp库中set的定义:
其中:
- 参数1:T即是set的实值
- 参数2:compare是中序遍历结果的排列,默认是升序
- 参数3:空间配置器
下面,我们来学习以下set的定义方式:
根据CPP官方文档,我们可以总结出如下的定义方式:
方式1:构造一个空的容器
set<int> s1;
方式2:拷贝构造
set<int> s1(s2);
方式3:迭代器区间构造
vector<int> s2={1,2,3,4,5,6,7,8,9,10};
set<int> s1(s2.begin(),s2.end());
方式4:构造空容器,并指定比较方式
set<int,greater<int>> s4;
3.2迭代器
作为STL的容器,set也是支持迭代器操作的。
对于set的迭代器而言,我们需要掌握的是以下的内容:
- 二叉搜索树的中序遍历为有序,因此我们这里的迭代器++应该是到中序的下一个结点
- set的迭代器是一个双向迭代器, 是支持++和–的。
我们可以在官方文档中看到如下内容:
另外,由于我们使用的是平衡搜索二叉树,因此它是不支持修改的,因此set中的迭代器都是const的,都是不能修改的。
如下:
3.3set的使用
下面我们来看看set的相关操作:
功能 | 用途 |
---|---|
迭代器 | 遍历容器 |
empty | 判断是否为空 |
size | 返回元素个数 |
max_size | 返回最大存储量 |
insert | 指定位置元素插入 |
erase | 删除 |
swap | 交换两个容器 |
clear | 清空容器内的元素 |
find | 返回寻找到的元素的迭代器位置 |
count | 返回容器指定键值的数量 |
下面,我们通过下面的这段代码来实践下:
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };set<int> s1(arr1.begin(), arr1.end());//迭代器遍历cout << "迭代器遍历结果:" << endl;set<int>::iterator it = s1.begin();while (it != s1.end()){cout << *it << " ";it++;}cout << endl;cout << "---------------------------" << endl;cout << "empty:" << s1.empty() << endl;cout << "size:" << s1.size() << endl;cout << "max_size:" << s1.max_size() << endl;//数据插入cout << "---------------------------" << endl;cout << "insert(5):";s1.insert(5);for (auto e : s1){cout << e << ' ';}cout << endl;//数据删除cout << "---------------------------" << endl;cout << "erase(5):";s1.erase(5);for (auto e : s1){cout << e << ' ';}cout << endl;//数据交换、查找、清理cout << "---------------------------" << endl;set<int> s2 = { 100,200,300 };s1.swap(s2);for (auto e : s1)cout << e << ' ';cout << endl;for (auto e : s2)cout << e << ' ';cout << endl;cout << "s2.find(8):";//cout << (s2.find(8) != s2.end()) << endl;//1cout << "s2.clear():" << endl;s2.clear();for (auto e : s2)cout << e << ' ';cout << endl;return 0;
}
打印结果如下:
最后,我们再谈一谈count,虽然count可以用来查找元素键值的数量的,但,对于set来说,由于不允许冗余的存在,因此count在这里实现的是查找元素是否存在。
实践代码如下:
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };set<int> s1(arr1.begin(), arr1.end());for (int i = 0; i < 10; i++){if (s1.count(i))cout << i << "在set中" << endl;elsecout << i << "不在set中" << endl;}return 0;
}
打印结果如下:
除了上述的使用方法之外,我们还可以通过更改比较方式来更改set中数值的排序方式。
如下:
int main()
{vector<int> arr1 = { 7,8,9,6,5,4,1,2,3 };set<int,greater<int>> s1(arr1.begin(), arr1.end());for (auto e : s1)cout << e << ' ';cout << endl;return 0;
}
结果如下:
这样,我们就完成了降序排列元素。
四.set的特点
set具有以下特点:
- 只有键值,键值就是实值,所以传递参数时只需要传递一个值。
- 自带去重机制,不允许数据冗余
- 使用迭代器遍历时,默认为升序
- 普通迭代器也不允许修改。
五.multset
5.1multset的使用
multset是set的另一个版本,对于multset来说,不同点有二:
- multset允许数据冗余。
- count可以在这里得到真正的使用。
我们先把CPP官网的图贴到下面:
这里,我们不再赘述multset的操作,先演示下数据冗余的效果。
int main()
{vector<int> arr1 = { 7,7,8,9,6,5,4,1,2,3 };multiset<int> s1(arr1.begin(), arr1.end());for (auto e : s1)cout << e << ' ';cout << endl;return 0;
}
结果如下:
然后,我们现在再来使用以下count函数
cout << s1.count(7) << endl;
结果:2
因此,在multset中,count函数可以计算出相同元素的数量。
5.2multset的查找以及结构
由于multset是允许冗余的,因此就出现了一个问题:如果我们要使用查找函数
那么,返回的是哪个元素呢?
我们来实验下:
int main()
{vector<int> arr1 = { 7,7,8,9,6,5,4,1,2,3 };multiset<int> s1(arr1.begin(), arr1.end());auto it = s1.begin();while (it != s1.end()){cout << *it << ":" << &*it << endl;it++;}cout << "s1.find(7):" << &*s1.find(7) << endl;return 0;
}
我们发现,我们查找到的是中序遍历中第一次出现的元素。
下面,我们看下multset的结构:
六.map
6.1map的介绍
map是二叉搜索树改造的key/value模型,是一个真正意义上的键值对模型。
应用场景很多,如下:
- 中英文词典
- 电话号码查询快递信息
- 电话号码+验证码
首先,我们先来看以下map的文档介绍:
其中
- 参数1:键值
- 参数2:实值
- 参数3:比较方式
- 参数4:空间配置器
在map中,会用到之前说过的pair结构,也就是说,first表示键值,second表示实值。
6.2map的定义方式
下面,我们来学习一下map的定义方式
通过上图,我们可以得知,可以有如下定义:
方式一: 指定key和value的类型构造一个空容器
map<int,string> ml;//键值为int,实值为string
方式二: 拷贝构造某类型容器
map<int,string> m2(m1);
方式三: 迭代器区间构造
map<int,string> m3(m2.begin(),m2.end());
方式四: 指定比较方式
map<int,string,greater<int>> m4;
我们下面实际的应用一下
int main()
{vector<pair<string, int>> arr = { make_pair("1",11),make_pair("2",22),make_pair("3",33) };map<string, int> m1;map<string, int> m2(arr.begin(),arr.end());cout << "m1:" << ' ';for (auto e : m1)cout << e.first << ':' << e.second << " ";cout << endl;cout << "m2:" << ' ';for(auto e:m2)cout << e.first << ':' << e.second << " ";cout << endl;return 0;
}
打印结果:
m1:
m2: 1:11 2:22 3:33
6.3map的使用
功能 | 用途 |
---|---|
迭代器 | 遍历容器 |
empty | 判空 |
size | 当前容器元素数 |
max_size | 容器的最大容量 |
operator[] | 按照键值(key/first),访问实值(value/second) |
insert | 指定位置插入 |
erase | 指定位置删除 |
swap | 交换两个容器 |
clear | 清空容器元素 |
find | 查找实值,并返回迭代器位置 |
count | 统计容器中指定键值(key/first)的数量 |
对于map而言,除了新增了一个operator[]和部分函数的返回值不一样之外,与set没啥区别。
下面,我们实践一下。
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{vector<pair<string, int>> arr={ make_pair("kuku",1),make_pair("kiki",2) };map<string, int> m1(arr.begin(), arr.end());cout << "迭代器遍历结果:";map<string, int>::iterator it1 = m1.begin();while (it1 != m1.end()){cout << "<" << it1->first << ";" << it1->second << ">";//注意,这里用的是->操作符++it1;}cout << endl;//判空,解引用,size和maxsizecout << "empty:" << m1.empty() << endl;cout << "[]:" << m1["kuku"] << endl;//这里要通过键值访问cout << "size:" << m1.size() << endl;cout << "maxsize:" << m1.max_size() << endl;//插入m1.insert(make_pair("lili",3));cout << "insert:" <<(--m1.end())->first<< (--m1.end())->second<<endl;//删除m1.erase("lili");cout << "erase:";for (auto e : m1){cout << "<" << e.first << ',' << e.second << ">,";}cout << endl;//交换,查找,清理map<string, int> m2 = {make_pair("trousers",44),make_pair("trou",66) ,make_pair("trouser",55)};m1.swap(m2);for (auto e : m1)cout << e.first << ' ' << e.second << ' ';cout << endl;for (auto e : m2)cout << e.first << ' ' << e.second << ' ';cout << endl;cout << (m1.find("kuku")!=m1.end()) << endl;//find返回的是一个迭代器cout << "m2.clear" << endl;m2.clear();cout<<m2.empty();
}
打印结果如下:
下面,我们详细的介绍几个函数
6.4 insert函数
由于insert函数要返回两个值:
- 是否插入成功
- 插入成功的迭代器位置
由于要返回两个值,因此insert的函数返回值应该是一个pair类型的。
pair<iterator,bool> insert(const value_type& val);
6.5 find和count函数
在map中,find和count都可以用来判断元素是否存在,但他们有以下的区别:
- find返回的是迭代器
- count返回的是键值数
6.6 map中的修改
map是可以修改pair中的第二个值的,也就是value。
我们可以通过迭代器进行修改,如下:
map<string,int>::iterator it1=m1.begin()++;
it1->second=77;
下面,我们可以用map来实现水果统计的代码:
vector<string> word={"苹果","梨子","桃子","苹果","梨子","桃子","苹果","梨子"};
map<string,int> table;
for(auto& e:word)
{if(!table.count(e))table.insert(make_pair(e,i));elsetable.find(e)->second++;
}
for(auto e:table)
{cout << "<" << e.first << ',' << e.second << ">,";
}
6.7 map中的operator[]
operator[]是返回实值,方括号内为键值。如果键值不存在的话,那么会插入信的键值对。
因此,operator是一个功能非常强大的东西。
我们可以结束operator[],把上面的统计水果改为下述代码:
int main()
{vector<string> word={"苹果","梨子","桃子","苹果","梨子","桃子","苹果","梨子"};map<string,int> table;for(auto& e:word){table[e]++;}for(auto e:table){cout << "<" << e.first << ',' << e.second << ">,";}
}
下面,我们介绍以下operator[]的实现:
- 调用insert,插入一个make_pair对象
- 获取到first,即获取到iterator
- 通过迭代器,获取到second
通过这样的一套形式,我们就可以实现一个operator
也就是说,是长这个样子的
(this->insert(make_pair(k,mapped_type()))).first)->second
因此,我们的operator[]是非常强大的,它有以下功能:插入+修改+查找。
七.map的特点
- 包含键值和实值,插入时需要插入pair对象
- 自带去重机制,不允许数据冗余(键值)
- 使用迭代器遍历时,默认为升序(依靠键值排序)
- 普通迭代器允许修改实值,const迭代器什么都不允许修改。
八.multimap
对于multimap而言,我们只需要注意两个点
- 允许键值冗余
- 没有重载operator[]