前文

初三下学期进入新的学习，对于前两年的学习内容因为各种原因上课打游戏，睡觉，看视频已经遗忘，忘记如何使用，算是重新学习一次信息学，希望能尽快将以前的内容弥补上来，争取能在CSP-2020取得一个好成绩吧

STL

1. vector

vector，应该算是STL中使用较多的一种容器之一，他的用法其实数组有一点相似，但是更加优越（不然为什么STL这么强）。

优越在什么地方呢？在使用数组时，因为题目要求，数组的长度决定了一定的内存，但是题目的内存限制我们在做题的时候不太容易把控，太小会RE，太大会MLE，那么vector就可以解决这个问题。

vector可以将他理解为一个可以变长的数组，他的长度会随着需要而改变。

这是关于vector的定义，当然我们现在只是相当于定义了一个一维数组，我们也可以定义二维数组等，这里其实有两种定义方法，我个人更喜欢使用第二种第一种不太理解

#include<vector>    //头文件

using namespace std;   //这句是必须要加的

vector<typename> a;  //typename是数据类型，如下：

vector<int> a;

vector<char> a;

vector<node> a;

···

（1）vector<typename,vector<typename> > a;  //一维长度固定，第二维可变化

（2）vector<typename> a[SIZE];    //a[0]~a[SIZE-1]都为vector，一维二维都可以变化

接下来就是关于vector的访问，也有两种方式，一种是下标访问（同数组相似），另一种是迭代器访问（个人用得较多），听同学说会快一点，具体如何我还没有仔细研究过

vector<int> a;

for(int i=1;i<=5;i++){

	a.push_back(i)

}

for(int i=1;i<=5;i++){

	cout<<a[i]<<" ";

}     //下标访问

for(vector<int>::iterator it=a.begin();it!=a.end();it++){

	cout<<*it<<" ";

}    //迭代器访问（稍微难打一点）

输出：1 2 3 4 5

注：涉及到的函数之后会提及，以上要注意it!=a.end()，并不支持it<a.end()

①push_back(x) 将元素x添加到vector中，时间复杂度为O(1)

②pop_back(x) 将vector尾元素删除，时间复杂度尾O(1)

③size（）没有参数，返回victor中的元素个数，时间复杂度尾O(1)

④clear（）没有参数，将vector清空，时间复杂度尾O（N），N为元素个数

⑤还有insert( ),erase( )等函数，因为使用不多，这里不多阐述

另外，很多STL容器中的范围应该都是左闭右开，即[ a.begin( ) , a.end( ) )，可以了解和注意一下这个地方

例题：

（1）http://codeup.cn/problem.php?cid=100000596&pid=0

（2）http://codeup.cn/problem.php?cid=100000596&pid=1

其中第二题可以直接使用set函数解决，在之后会说，思路和代码都很简单。

重点说第一题，前几次做的时候，我用的是set和map之类的做法，但是做出来都是超出内存和输出问题（？？？这玩意之前我还真心不知道是什么），调了差不多半个多小时，决定用vector（毕竟vector的题）。

虽然用set和map可以很好地解决排序的问题，因为set和map都可以自动排序，但在其他时间和内存方面，是不如vector优越的，当然需要用到map套vector。

我们用一个二维的vector来解决这一道题，我们是a[name]中的元素代表学习的课程，每一次学习新的课程后push_back进去，我们要求的学习课程数量就是a[name].size()，对于其中的升序排列问题，最开始我觉得应该自己手动排列一下，学长看我想了很久说这东西可以直接sort（qiao），范围就是a[name].begin()~a[name].end()

至于输出名字，直接用char和string输入，然后直接输出并执行以上的操作就行了。但是会导致内存太大，对于vector的处理已经差不多了，我们应该想办法在名字上做优化。

因为输出名字很好办（如上），但是对于一个vector<string(或char)>来说太大，所以我们考虑哈希的方法，将char或者string转换为int类型。题目中说，每个人的名字又三个英文字母加一个数字组成，长度固定为4，因为最后一个为数字，可以忽略掉，长度变为3。这就是使我们的哈希变得更快，不需要任何循环，直接return就可以（说得不清楚，代码中有体现），那么这道题也就解决了。

#include<bits/stdc++.h>

using namespace std;

int n,m;

int x,y;

char nann[4];

int ha[4] = {1,27,729,19683};  //哈希值

int has(char na[]){

    return na[0]*ha[0]+na[1]*ha[1]+na[2]*ha[2]+na[3]*ha[3];  //不需要用到循环，因为长度确定，直接return降低时间复杂度

}

map<int,vector<int> >a;

//map套vector，int关键字代替名字（用哈希将char转化为int）

//vector中的值指学习的课程

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){

        cin>>x>>y;

        for(int j=1;j<=y;j++){

            scanf("%s",nann);

            int k=has(nann);

            a[k].push_back(x);   //哈希处理名字，将课程加入

        }

    }

    for(int i=1;i<=n;i++){

        scanf("%s",nann);

        int k=has(nann);

        printf("%s %d ",nann,a[k].size( ));   //课程数=元素个数

        sort(a[k].begin(),a[k].end());    //对所学课程排序（升序）

        for(vector<int>::iterator it=a[k].begin( );it!=a[k].end( );++it){

            printf("%d ",*it);

        }       //迭代器遍历学的课程

        puts("");

    }

    return 0;

}

巴特西

STL初步学习（vector）

前文

STL

1. vector

例题：

最新文章

热门文章