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~