程序设计与算法（三）第九周 标准模板库STL（二）（1）

set和multiset

关联容器：set, multiset, map, multimap

• 内部元素有序排列，新元素插入的位置取决于它的值，查找速度块
• 除了各容器都有的函数外，还支持以下成员函数
• find:查找等于某个值的元素（x小于y和y小于x同时不成立即为相等）
• lower_bound:查找某个下界
• upper_bound:查找某个上界
• equal_range:同时查找上界和下界
• count:计算等于某个值的元素个数（x小于y和y小于x同时不成立即为相等）
• insert:用以插入一个元素或一个区间

预备知识：pair模板

template <class _T1, class _T2>
struct pair{
    typedef _T1 first_type;
    typedef _T2 second_type;
    _T1 first;
    _T2 second;
    pair():first(), second(){}
    pair(const _T1&_a, const _T2&_b):first(_a),second(_b){}
    template <class _U1, class _U2>
            pair(const pair<_U1, _U2>& _p):first(_p.first), second(_p.second){};
};

• map/multimap容器里放着的都是pair模板类的对象，且按照first从大到小排序
• 第三个构造函数用法示例：
• pair

multiset

template <typename _Key, typename _Compare = std::less<_Key>,
        typename _Alloc = std::allocator<_Key> >

Pred(就是上面的_Compare)类型的变量决定了multiset中的元素，“一个比另一个小”是怎么定义的。multiset运行过程中，比较两个元素x,y的大小的做法，就是生成一个Pred类型的变量，假定op,若表达式op(x,y)返回true,则x比y小。Pred的缺省类型是less< key>.

less模板定义：是靠<来比较大小的

template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

multiset的成员函数

• iterator find(const T&val); 在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()
• iterator insert(const T&val); 将val插入到容器中并返回其迭代器
• void insert(iterator first, iterator last); 将区间[first, second)插入容器
• int count(const T&val); 统计有多少个元素的值和val相等
• iterator lower_bound(const T&val); 查找一个最大的位置it，使得[begin(), it)中所有元素都比val小
• iterator upper_bound(const T&val); 查找一个最小位置的it，使得[it, end())中所有的元素都比val大
• pair

#include <iostream>
#include <set>

using namespace std;

template <class T>
void Print(T first, T last)
{
    for(;first!=last;++first)
        cout<<*first<<" ";
    cout<<endl;
}

class A{
private:
    int n;
public:
    A(int _n):n(_n){}
    friend bool operator<(const A &a1, const A &a2){return a1.n<a2.n;}
    friend ostream &operator<<(ostream &o, const A &a2){o<<a2.n;return o;}
    friend class MyLess;
};

struct MyLess{
    bool operator()(const A &a1, const A &a2)
    {
        return (a1.n%10)<(a2.n%10);
    }
};
typedef multiset<A> MSET1;
typedef multiset<A, MyLess> MSET2;

int main()
{
    const int SIZE = 6;
    A a[SIZE]={4,22,19,8,33,40};
    MSET1 m1;
    m1.insert(a, a+SIZE);
    m1.insert(22);
    cout<<"1)"<<m1.count(22)<<endl;
    cout<<"2)";
    Print(m1.begin(), m1.end());
    MSET1::iterator pp = m1.find(19);
    if(pp!=m1.end()) cout<<"found"<<endl;
    cout<<"3)";
    cout<<*m1.lower_bound(22)<<","<<*m1.upper_bound(22)<<endl;
    pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));//左闭右开
    cout<<"4)";
    Print(m1.begin(), m1.end());
    cout<<"5)";
    cout<<*pp<<endl;//指向被删除的元素的后一个
    MSET2 m2;
    m2.insert(a, a+SIZE);
    cout<<"6)";
    Print(m2.begin(),m2.end());
    return 0;
}

1)2
2)4 8 19 22 22 33 40 
found
3)22,33
4)4 8 19 33 40 
5)33
6)40 22 33 4 8 19

set

template<typename _Key, typename _Compare = std::less<_Key>,
       typename _Alloc = std::allocator<_Key> >

#include <iostream>
#include <set>
using namespace std;
int main()
{
    typedef set<int>::iterator IT;
    int a[5]={3,4,6,1,2};
    set<int> st(a, a+5);
    pair<IT,bool> result;
    result = st.insert(5);
    /*
     这里insert返回的是一个pair
    std::pair<iterator, bool>
      insert(value_type&& __x)
      {
    std::pair<typename _Rep_type::iterator, bool> __p =
      _M_t._M_insert_unique(std::move(__x));
    return std::pair<iterator, bool>(__p.first, __p.second);
      }
     */
    if(result.second){
        cout<<*result.first<<" inserted"<<endl;
    }
    if(st.insert(5).second){
        cout<<*result.first<<endl;
    }
    else
        cout<<*result.first<<" already exists"<<endl;
    //equal_range:同时求lower_bound和upper_bound，返回一个pair
    //lower_bound:最右边的迭代器，再向右侧就比4大了，upper_bound反之
    pair<IT, IT> bounds = st.equal_range(4);
    cout<<*bounds.first<<","<<*bounds.second;
    return 0;
}

5 inserted
5 already exists
4,5

map/multimap

multimap

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 class map
    {
    public:
      typedef _Key                                          key_type;
      typedef _Tp                                           mapped_type;
      typedef std::pair<const _Key, _Tp>                    value_type;
      typedef _Compare                                      key_compare;
      typedef _Alloc                                        allocator_type;

key代表了关键字

multimap中的元素由<关键字，值>组成，每个元素是一个pair对象，关键字就是first成员变量，其类型是key

multimap 中允许多个元素的关键字相同。元素按照first成员变量从小到大排列，缺省情况下用less< key>定义关键字的“小于关系

#include <iostream>
#include <map>
using namespace std;
int main() {
    typedef multimap<int, double, less<int> >mmid;
    mmid pairs;
    cout<<"1)"<<pairs.count(15)<<endl;
    /*
     typedef std::pair<const _Key, _Tp>                    value_type;
     */
    pairs.insert(mmid::value_type(15, 2.7));
    pairs.insert(mmid::value_type(15, 99.3));
    cout<<"2)"<<pairs.count(15)<<endl;//求关键字等于某个值的元素个数
    pairs.insert(mmid::value_type(30, 111.11));
    pairs.insert(mmid::value_type(10, 22.22));
    pairs.insert(mmid::value_type(25, 33.333));
    pairs.insert(mmid::value_type(20, 9.3));
    for(mmid::const_iterator i=pairs.begin();i!=pairs.end();i++)
    {
        cout<<"("<<i->first<<","<<i->second<<")"<<",";
    }
    return 0;
}

1)0
2)2
(10,22.22),(15,2.7),(15,99.3),(20,9.3),(25,33.333),(30,111.11),

multimap例题

#include <iostream>
#include <map>
#include <string>
using namespace std;
class CStudent{
public:
    struct CInfo{
        int id;
        string name;
    };
    int score;
    CInfo info;
};

typedef multimap<int, CStudent::CInfo> MAP_STD;//缺省情况下，是根据key值比较大小的
int main()
{
    MAP_STD mp;
    CStudent st;
    string cmd;
    while(cin>>cmd){
        if(cmd=="Add"){
            cin>>st.info.name>>st.info.id>>st.score;
            mp.insert(MAP_STD::value_type(st.score, st.info));//mp.insert(make_pair(st.score, st.info));
        }
        else if(cmd=="Query"){
            int score;
            cin>>score;
            MAP_STD::iterator p=mp.lower_bound(score);//找到比score小的那个值[begin,it)
            if(p!=mp.begin())
            {
                --p;
                score = p->first;
                MAP_STD::iterator maxp = p;
                int maxId = p->second.id;
                for(;p!=mp.begin() && p->first==score;--p){
                    //遍历所有成绩和score相等的学生
                    if(p->second.id>maxId){
                        maxp = p;
                        maxId = p->second.id;
                    }
                }
                if(p->first==score)
                {
                    // 如果上面循环是因为p==mp.begin()
                    //而终止，则p指向的元素还要处理
                    if(p->second.id>maxId){
                        maxp = p;
                        maxId = p->second.id;
                    }
                }
                cout<<maxp->second.name<<" "<<maxp->second.id<<" "<<maxp->first<<endl;
            } else
                cout<<"Nobody"<<endl;
        }
    }
    return 0;
}

map

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    class map
    {
    public:
      typedef _Key                                          key_type;
      typedef _Tp                                           mapped_type;
      typedef std::pair<const _Key, _Tp>                    value_type;
      typedef _Compare                                      key_compare;
      typedef _Alloc                                        allocator_type;

map的[ ]成员函数

若pairs为map模板类的对象，pairs[key]返回对关键字等于key的元素的值(second成员变量)的引用。若没用关键字为key的元素，则会往pairs里插入一个关键字为key的元素，其值用无参构造函数初始化，并返回其值的引用。

如: map

#include <map>
#include <iostream>
using namespace std;
template <class Key, class Value>
ostream & operator<<(ostream &o, const pair<Key, Value>&p){
    o<<"("<<p.first<<","<<p.second<<")";
    return o;
};
int main()
{
    typedef map<int, double, less<int> >mmid;
    mmid pairs;
    cout<<"1)"<<pairs.count(5)<<endl;
    pairs.insert(mmid::value_type(15, 2.7));
    pairs.insert(make_pair(15, 99.3));
    cout<<"2)"<<pairs.count(15)<<endl;
    pairs.insert(mmid::value_type(20,9.3));
    mmid::iterator i;
    cout<<"3)";
    for(i=pairs.begin();i!=pairs.end();i++)
        cout<<*i<<",";
    cout<<endl;
    cout<<"4)";
    int n=pairs[40];
    for(i=pairs.begin();i!=pairs.end();i++)
    {
        cout<<*i<<",";
    }
    cout<<endl;
    cout<<"5)";
    pairs[15]=6.28;
    for(i=pairs.begin();i!=pairs.end();i++)
        cout<<*i<<",";
    return 0;
}

1)0
2)1
3)(15,2.7),(20,9.3),
4)(15,2.7),(20,9.3),(40,0),
5)(15,6.28),(20,9.3),(40,0),

容器适配器：上面没有迭代器

stack：栈：后进先出，只能插入删除，访问栈定元素

可用vector, list, deque来实现。缺省情况下，用deque实现。用vector和deque实现，比用list实现性能好

template<typename _Tp, typename _Sequence = deque<_Tp> >

stack上可以进行以下操作：push：插入元素；pop：弹出元素；top：返回栈顶元素的引用

queue:队列

和stack基本类似，可以用list和deque实现。缺省情况下用deque实现。

template<typename _Tp, typename _Sequence = deque<_Tp> >

同样有push，pop，top函数。但是push发生在队尾；pop，top发生在队头。先进先出。有back成员函数可以返回队尾元素的引用

priority_queue

template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >

和queue类似，可以用vector和deque实现。缺省情况下用vector实现。

priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素，执行top操作时，返回的是最大元素的引用。默认的元素比较器是:less< T>……….push和pop的时间复杂度：O(log(n))，top的时间复杂度O(1)

#include <queue>
#include <iostream>
using namespace std;
int main()
{
    priority_queue<double> pq1;
    pq1.push(3.2);
    pq1.push(9.8);
    pq1.push(9.8);
    pq1.push(5.4);
    while(!pq1.empty()){
        cout<<pq1.top()<<" ";
        pq1.pop();
    }
    cout<<endl;
    priority_queue<double, vector<double>, greater<double> > pq2;
    pq2.push(3.2);
    pq2.push(9.8);
    pq2.push(9.8);
    pq2.push(5.4);
    while(!pq2.empty()){
        cout<<pq2.top()<<" ";
        pq2.pop();
    }
    return 0;
}

9.8 9.8 5.4 3.2 
3.2 5.4 9.8 9.8 

容器适配器返回元素个数

stack, queue, priority_queue都有:

empty() 成员函数用于判断适配器是否为空

size() 成员函数返回适配器中元素的个数