第七关——STL

19:56:13 初见和告别之间，回想只剩星星点点。——许嵩《最佳歌手》

今天话不多说，进入正题吧。

STL

STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说，STL是一些"容器"的集合，这些"容器"有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的"容器"和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用安装额外的库文件。

在C++标准中，STL被组织为下面的13个头文件:<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory.h>、<numeric>、<queue>、<set>、<stack>和<utility>。

今天要讲的主要是<vector>、<list>、<map>、<set>、<queue>、<stack>；

map

Map是STL 的一个关联容器，它提供一对一(其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值)的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。

• 如：

map<int,string> maphai;

map<char,int> maphai;

map<string,char> mapstring;

map<string,int> mapstring;

map<int,char>mapint;

map<char,string>mapchar;

• 例：

具体用法就直接看例题吧。

shoping

这道题就可以用map解决会方便很多。

#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string,int> shop;
int main()
{
    int n,m,p;
    while(cin>>n)
    {
        string s;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            shop[s]=0;
        }
        cin>>m;
        while(m--)
        {
 
            for(int i=1;i<=n;i++)
            {
                cin>>p>>s;
                shop[s]+=p;
            }
            int flag=shop["memory"];
            int rank=1;
            map<string,int>::iterator it;
            for(it=shop.begin();it!=shop.end();it++)
            {
                if((*it).second>flag)
                    rank++;
            }
            cout<<rank<<endl;
        }
        shop.clear();
    }
    return 0;
}

20:13:45 初雪飘过风吹霜，是否给我一次机会重来呀。——吴亦凡《贰叁》

vector

vector是表示可变大小数组的序列容器。

就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

函数

• 向量大小： vec.size();

• 向量最大容量： vec.max_size();

• 更改向量大小： vec.resize();

• 向量真实大小： vec.capacity();

• 向量判空： vec.empty();

• 多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值

• 末尾添加元素： vec.push_back();

• 末尾删除元素： vec.pop_back();

• 任意位置插入元素： vec.insert();

• 任意位置删除元素： vec.erase();

• 交换两个向量的元素： vec.swap();

• 清空向量元素： vec.clear();

算法

• 遍历

vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)
    cout << *it << endl;



for (size_t i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
}

• 翻转（元素）

#include <algorithm>
reverse(vec.begin(), vec.end());

• 排序

#include <algorithm>
sort(vec.begin(), vec.end()); //从小到大
//从大到小排序，可以采用上面反转函数，也可以采用下面方法:
bool Comp(const int& a, const int& b) {
    return a > b;
}
sort(vec.begin(), vec.end(), Comp);

list

list是C++标准模版库(STL)中的部分内容。实际上,list容器就是一个双向链表,可以高效地进行插入删除元素。

使用list容器之前必须加上<vector>头文件：#include<list>;

函数（c为一个list）

• c.begin()      返回指向链表第一个元素的迭代器。

• c.end()      返回指向链表最后一个元素之后的迭代器。

• c.rbegin()      返回逆向链表的第一个元素,即c链表的最后一个数据。

• c.rend()      返回逆向链表的最后一个元素的下一个位置,即c链表的第一个数据再往前的位置。

• operator=      重载赋值运算符。

• c.assign(n,num)      将n个num拷贝赋值给链表c。

• c.assign(beg,end)      将[beg,end)区间的元素拷贝赋值给链表c。

• c.front()      返回链表c的第一个元素。

• c.back()      返回链表c的最后一个元素。

• c.empty()  判断链表是否为空。

• c.size()      返回链表c中实际元素的个数。

• c.max_size()      返回链表c可能容纳的最大元素数量。

• c.clear()      清除链表c中的所有元素。

• c.insert(pos,num)      在pos位置插入元素num。

• c.insert(pos,n,num)      在pos位置插入n个元素num。

• c.insert(pos,beg,end)      在pos位置插入区间为[beg,end)的元素。

• c.erase(pos)　　　　删除pos位置的元素。

• c.push_back(num)      在末尾增加一个元素。

• c.pop_back()      删除末尾的元素。

• c.push_front(num)      在开始位置增加一个元素。

• c.pop_front()      删除第一个元素。

• c1.swap(c2);      将c1和c2交换。

list<int> a1{1,2,3,4,5};
list<int>::iterator it;
for(it = a1.begin();it!=a1.end();it++){
    cout << *it << "	";    
}
cout << endl;



list<int> a1{1,2,3,4,5};
list<int>::reverse_iterator it
for(it = a1.rbegin();it!=a1.rend();it++){
    cout << *it << "	";
}



list<int> a1 {1,2,3,4,5},a2;
a2 = a1;
list<int>::iterator it;
for(it = a2.begin();it!=a2.end();it++){
    cout << *it << endl;
}



int a[5] = {1,2,3,4,5};
    list<int> a1;
    list<int>::iterator it;
    a1.assign(2,10);
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    a1.assign(a,a+5);
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;



list<int> a1{1,2,3,4,5};
if(!a1.empty())
cout << "a1 is not empty" << endl;
else
cout << " a1 is empty" << endl;
cout << a1.size() << endl;
cout << a1.max_size() << endl;



list<int> a1{1,2,3,4,5};
    list<int>::iterator it;
    cout << "clear before:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << "	";
    }
    cout << endl;
    a1.clear();
    cout << "clear after:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << "	";
    }
    cout << endl;



list<int> a1{1,2,3,4,5};
    list<int>::iterator it;
    cout << "insert before:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.insert(a1.begin(),0);
    cout << "insert(pos,num) after:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.insert(a1.begin(),2,88);
    cout << "insert(pos,n,num) after:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;

    int arr[5] = {11,22,33,44,55};
    a1.insert(a1.begin(),arr,arr+3);
    cout << "insert(pos,beg,end) after:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;



list<int> a1{1,2,3,4,5};
    list<int>::iterator it;
    cout << "erase before:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    a1.erase(a1.begin());
    cout << "erase after:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;



list<int> a1{1,2,3,4,5};
    a1.push_back(10);
    list<int>::iterator it;
    cout << "push_back:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.pop_back();
    cout << "pop_back:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.push_front(20);
    cout << "push_front:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    a1.pop_front();
    cout << "pop_front:";
    for(it = a1.begin();it!=a1.end();it++){
        cout << *it << " ";
    }
    cout << endl;



list<int> a1{1,2,3,4,5},a2,a3;
    a2.swap(a1);
    list<int>::iterator it;
    cout << "a2.swap(a1):";
    for(it = a2.begin();it!=a2.end();it++){
        cout << *it << " ";
    }
    cout << endl;
    
    swap(a3,a2);
    cout << "swap(a3,a2):";
    for(it = a3.begin();it!=a3.end();it++){
        cout << *it << " ";
    }
    return 0;

士兵队列训练问题

list链表，每轮先erase报2的，再erase报3的

一定要特别注意每一轮删除之前要判断s.size()是否大于3！！！

#include <stdio.h>
#include <list>
using namespace std;
 
int main()
{
    //freopen("in.txt", "r", stdin);
    int n, i;
    list<int>s;
    list<int>::iterator it;
    int T;
    scanf("%d", &T);
    while (T--){
        s.clear();
        scanf("%d", &n);
        for (i = 1; i <= n; i++)s.push_back(i);
        while (s.size()>3){
            for (i = 1, it = s.begin(); it != s.end();){
                if (i % 2 == 0){
                    it = s.erase(it);
                    i = 1;
                }
                else{
                    ++it;
                    ++i;
                }
            }
            if (s.size() > 3){
                for (i = 1, it = s.begin(); it != s.end();){
                    if (i % 3 == 0){
                        it = s.erase(it);
                        i = 1;
                    }
                    else{
                        ++it;
                        ++i;
                    }
                }
            }
        }
        for (it = s.begin(); it != s.end();++it){
            if (it != s.begin())printf(" ");
            printf("%d", *it);
        }
        printf("
");
    }
    return 0;
}

20:42:39 我这句语气原来好想你，不就是我们爱过的证据。——梁静茹《可惜不是你》

set

set是STL中一个很有用的容器，用来存储同一种数据类型的数据结构（可以称之为K的模型），基本功能与数组相似。

set与数组不同的是，在set中每个元素的值都是唯一的。

而且set插入数据时，能够根据元素的值自动进行排序。

set中数元素的值并不能直接被改变.

函数

• begin() 返回指向第一个元素的迭代器

• clear() 清除所有元素

• count() 返回某个值元素的个数

• empty() 如果集合为空，返回true(真)

• erase() 删除集合中的元素

• find() 返回一个指向被查找到元素的迭代器，如果没找到则返回end()

• get_allocator() 返回集合的分配器

• insert() 在集合中插入元素

• lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器

• size() 集合中元素的数目

• swap() 交换两个集合变量

• upper_bound() 返回大于某个值元素的迭代器

产生冠军

这道题的意思大概是：

比赛中互有胜负，将所有人放入一个集合中，输的人放入另外一个集合中。只有唯一1个人没有输时，才产生冠军。

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main()
{
    int n;
    set<string> all, lose;
    string Winner, loser;
    while(cin >> n && n != 0) {
        all.clear();
        lose.clear();
        while(n--) {
            cin >> Winner >> loser;
            all.insert(Winner);
            all.insert(loser);
            lose.insert(loser);
        }
        if(all.size() - lose.size() == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

21:01:30 让我为你唱一首歌，全世界都陪你听着。——《让我为你唱首歌》

queue（stack）

队列也是一种逻辑数据结构，其具有先进先出的特性，只能在队的前端进行删除， 在队的后端进行插入。针对这种特性，可以实现一些较为复杂的逻辑。在实际应用中，部分程序也正需要这样一种顺序进出的数据处理方式。使用这样的逻辑处理方式，使得我们可以将更多精力放在如何处理顺序逻辑之外的事情，对于编程、开发来讲，提供了极大的方便。

函数

• back()返回一个引用，指向队列的最后一个元素。

• empty()函数返回真(true)如果队列为空，否则返回假(false)。

• front()返回队列第一个元素的引用。

• pop()函数删除队列的一个元素

• push() 在末尾加入一个元素

• size() 返回队列中元素的个数

Text Reverse

这道题要注意有一个吸收回车符，特别容易忘。

#include<bits/stdc++.h>
using namespace std;
int main() {
    stack<char> s;
    int n;
    cin>>n;
    getchar();
    while(n>0) {
        n--;
        while(5){
            char a;
            a=getchar();
            if(a==' '||a=='
'||a==EOF)
            {
                while(s.size())
                {
                    cout<<s.top();
                    s.pop();
                }
                cout<<" ";
            }
            else
            s.push(a);
            if(a=='
'||a==EOF)  
            break;
        }
        cout<<endl;
    }
    return 0;
}

ACboy needs your help again!

对每次操纵进行模仿，输出成果

#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
    int a, b, c;
    char s[10];
    scanf("%d", &a);
    while(a--){
        scanf("%d %s", &b, s);
        if(s[2] == 'F'){
            queue <int> que;
            for(int i = 0; i < b; i++){
                scanf("%s", s);
                if(s[0] == 'I'){
                    scanf("%d", &c);
                    que.push(c);
                }
                else{
                    if(que.empty()){
                        printf("None
");
                    }
                    else{
                        printf("%d
", que.front())；
                        que.pop();
                    }
                }
            }
        }
        else{
            stack <int> ata;
            for(int i = 0; i < b; i++){
                scanf("%s", s);
                if(s[0] == 'I'){
                    scanf("%d", &c);
                    ata.push(c);
                }
                else{
                    if(ata.empty()){
                        printf("None
");
                    }
                    else{
                        printf("%d
", ata.top());
                        ata.pop();
                    }
                }
            }
        }
    }
    return 0;
}

_{我对你（博客）就不说再见了，毕竟也不是多想再见。21:31:22}