C++ 有序关联容器

在C++当中最常用的关联容器就是map和set，其中map表示映射，set表示集合。
map和set内部实现的数据结构是红黑树，查询和插入的时间复杂度为O(log n)。

map和set的定义与初始化：

普通类型

typedef pair<int,int> pii;
vector<int> ve;
vector<pii> vpi;
int main()
{
ios::sync_with_stdio(false);
//参数列表时
map<int,int> mi={{1,2},{2,3}};
set<int> si={1,2,3,4};
//使用pair给map初始化
map<int,int> mi2={make_pair(1,2),make_pair(2,3)};
//使用其他同类型的容器初始化map和set
map<int,int> mi3(vpi.begin(),vpi.end());
set<int> si2(ve.begin(),ve.end());
return 0;
}

结构体类型，存储在map和set当中需要重载运算符<

#include<bits/stdc++.h>
using namespace std;
struct node
{
int a,b,c;
node()
{
a=1,b=2,c=3;
}
bool operator <(const node &n)const
{
return this->a<n.a;
}
};
typedef pair<node,string> pns;
vector<pns> vp;
vector<node> vn;
int main()
{
ios::sync_with_stdio(false);
map<node,string> mns(vp.begin(),vp.end());
set<node> sn(vn.begin(),vn.end());
return 0;
}

map和set的赋值：

首先记录一下pair类型，pair类型顾名思义就是一个二元组。里面的元素分别是first和second，pair里面重载了关系运算符，使用起来很方便，尤其是在函数需要返回两个值的时候。

#include<bits/stdc++.h>
using namespace std;
typedef pair<string,int> psi;
psi fun(string s,int i)//返回一个string,int类型的pair
{
return make_pair(s,i);
}
int main()
{
ios::sync_with_stdio(false);
string s="abc";
int a=123;
cout<<fun(s,a).first<<" "<<fun(s,a).second<<endl;
return 0;
}

关联容器当中的类型别名

#include<bits/stdc++.h>
using namespace std;
map<string,int> msi;
set<string> ss;
int main()
{
ios::sync_with_stdio(false);
map<string,int>::key_type s1="asd";
map<string,int>::mapped_type a=123;
map<string,int>::value_type p={"abc",123};
return 0;
}

添加元素

set添加元素的方式可以使用insert函数以及emplace函数。其中insert是直接插入元素，emplace构造并插入元素。

#include<bits/stdc++.h>
using namespace std;
set<string> ss;
int main()
{
ios::sync_with_stdio(false);
string tmp="aaa";
vector<string> vs={"asd","qwe","bdf"};
ss.insert(tmp);//插入单个元素
ss.insert(vs.begin(),vs.end());//插入迭代器范围的元素
ss.emplace("ppp");//插入构造元素
return 0;
}

map添加元素与set差不多，不过多了一个下标的添加操作。

#include<bits/stdc++.h>
using namespace std;
map<string,int> msi;
vector<pair<string,int>> vpsi={{"qwe",111},{"rrr",222}};
int main()
{
ios::sync_with_stdio(false);
string tmp="asd";
int a=123;
msi.insert(make_pair(tmp,a));
msi.insert(vpsi.begin(),vpsi.end());
msi["qweeee"]=99;
return 0;
}

map和set的删除和修改：

删除元素可以使用erase函数来完成，其参数可以有三种：

①参数是关键字，返回删除元素的个数，这里用multiset来实现

#include<bits/stdc++.h>
using namespace std;
vector<int> vi={1,2,3,4,5,1,4,1};
int main()
{
ios::sync_with_stdio(false);
multiset<int> si(vi.begin(),vi.end());
int siz=si.erase(1);//输出3
cout<<siz<<endl;
return 0;
}

map版本

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> vi={{1,1},{2,3},{3,5},{4,3}};
int main()
{
ios::sync_with_stdio(false);
map<int,int> mi(vi.begin(),vi.end());
int siz=mi.erase(3);
cout<<siz<<endl;
return 0;
}

②参数是指向某个元素迭代器，会删除这个元素。不会删除所有该关键字，返回一个指向下一个元素的迭代器

#include<bits/stdc++.h>
using namespace std;
vector<int> vi={1,2,3,4,5,1,4,1};
int main()
{
ios::sync_with_stdio(false);
multiset<int> si(vi.begin(),vi.end());
auto it=si.begin();
auto next=si.erase(it);
for(auto x:si)
cout<<x<<" ";
cout<<endl;
cout<<*next<<endl;
return 0;
}

map版本

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> vi={{1,1},{2,3},{3,5},{4,3}};
int main()
{
ios::sync_with_stdio(false);
map<int,int> mi(vi.begin(),vi.end());
auto it=mi.begin();
auto next=mi.erase(it);
cout<<next->first<<" "<<next->second<<endl;
return 0;
}

③删除一个迭代器表示范围的元素，参数是[b,e)返回e

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> vi={{1,1},{2,3},{3,5},{4,3}};
int main()
{
ios::sync_with_stdio(false);
map<int,int> mi(vi.begin(),vi.end());
auto beg=mi.begin();
auto en=++beg;
auto it=mi.erase(beg,en);
for(auto x:mi)
cout<<x.first<<" "<<x.second<<endl;
return 0;
}

set与map的查找操作：

由于set与map是用红黑树实现的，查找速度是log(n)，性能非常优秀。

在set和map当中，基本的用于查找的成员函数有count(),find()和empty()
关于更多成员函数的详细信息和例子，可以参考C++官网

在普通的map和set当中count和find都可以用来判断容器当中是否存在某个元素，不同地方在于count返回容器中要查询的元素的个数，find函数如果找到该元素则返回指向该元素的迭代器，否则指向容器的尾部迭代器

empty函数就是判断容器是否为空

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
set<int> s={1,2,3,4,5,5,5,5};
map<int,int> m={{1,1},{2,3},{3,4}};
cout<<s.empty()<<" "<<m.empty()<<endl;//0 0
cout<<s.count(5)<<" "<<s.count(10)<<endl;//1 0
cout<<m.count(1)<<" "<<m.count(4)<<endl;//1 0
if(s.find(1)!=s.end())
cout<<1<<endl;//1
else
cout<<0<<endl;
if(m.find(2)!=m.end())
cout<<2<<endl;//2
else
cout<<0<<endl;
return 0;
}

set的集合操作：

set也叫做集合，所以会支持集合一些操作。

可以用仿函数来实现容器顺序

不光是set可以实现，其他容器也可以实现。

交集用泛型算法set_intersection实现
并集用泛型算法set_union实现
差集用泛型算法set_difference实现

参数分别为
(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
(第一个容器的迭代器起始，第一容器迭代器的末尾，第二个迭代器的起始，第二个迭代器的末尾，输出结果迭代器，自定义函数)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
set<int,greater<int>> s1={1,2,3,4,5};
set<int,greater<int>> s2={1,2,5,6,7,4};
vector<int> ns(100);
auto ind=set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),ns.begin(),greater<int>());//求交集,ind返回结尾指针
for(auto it=ns.begin();it!=ind;it++)
cout<<*it<<" ";//5 4 2 1
cout<<endl;
ind=set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),ns.begin(),greater<int>());//求并集
for(auto it=ns.begin();it!=ind;it++)
cout<<*it<<" ";//7 6 5 4 3 2 1
cout<<endl;
ind=set_difference(s1.begin(),s1.end(),s2.begin(),s2.end(),ns.begin(),greater<int>());//求差集,第一个集合有，第二个没有的
for(auto it=ns.begin();it!=ind;it++)
cout<<*it<<" ";//3
cout<<endl;
return 0;
}

multiset和multimap：

multiset与普通的set的不同之处在于一个键对应多个值，也就不再类似数学当中集合的概念，multiset与set一样，也是value和key是同一个值。

multimap和普通map的区别在于一个key值可以对应多个value。

multiset和multimap的赋值，添加和删除元素与set和map没有太大区别。

例子，利用multiset当中的成员函数lower_bound和upper_bound查找某一个值所在的范围。

lower_bound和upper_bound也是泛型算法，查找某一个有顺序容器的下界和上界

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
vector<int> vi={1,2,1,1,23,4,123,42,34};
multiset<int> musi(vi.begin(),vi.end());
auto fir=musi.lower_bound(1);//找到第一个1
auto las=musi.upper_bound(1);//找到最后一个1
cout<<distance(musi.begin(),fir)<<endl;//利用distance函数输出距离
cout<<distance(musi.begin(),las)<<endl;
cout<<distance(fir,las)<<endl;
return 0;
}

对应查找某个元素，尤其是count函数的返回值不仅仅会是1和0了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
multiset<int> s={1,2,3,4,5,5,5,5};
multimap<int,int> m={{1,1},{2,3},{3,4},{1,4}};
cout<<s.empty()<<" "<<m.empty()<<endl;//0 0
cout<<s.count(5)<<" "<<s.count(10)<<endl;//4 0
cout<<m.count(1)<<" "<<m.count(4)<<endl;//2 0
if(s.find(1)!=s.end())
cout<<1<<endl;//1
else
cout<<0<<endl;
if(m.find(2)!=m.end())
cout<<2<<endl;//2
else
cout<<0<<endl;
return 0;
}

to be continue~

最后

以上就是妩媚电话为你收集整理的C++ 有序关联容器的全部内容，希望文章能够帮你解决C++ 有序关联容器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。