vector 动态数组

声明及初始化

1
2
3
4
5
6
#include<vector>
vector<int> a;
vector<int> b[233]; //第一维长度233,每一个元素是一个变长数组
struct rec{...};
vector<rec> c; //结构体动态数组
vector<int> a(n); //创建n个空间,接下来执行push操作,从n位置开始算起

访问

1
a[10];

size/empty

所有STL容器均支持这两种方法

1
2
3
vector<int> a;
a.size(); //return 元素个数
a.empty(); //判空 return 布尔值

clear

1
a.clear(); //清空

迭代器

  • STL中的指针,可以支持类似指针的++,–,->, *,加减
1
2
vector<int>::iterator it; //声明迭代器;
*it; it->name; it++; it--; it1 + 5;

begin/end

  • 左闭右开
1
2
3
4
a.begin(); //返回指向第一个元素的迭代器
a.end(); //返回指向最后一个元素的后一个位置的迭代器
(*a.begin()) <==> a[0]
(*a.end()) <==> a[n] 越界
  • 遍历
1
2
3
4
5
6
for(int i=0; i<a.size(); i++){
cout << a[i] << endl;
}
for(vector<int>::iterator it = a.begin(); it != a.end(); it++){
cout << *it << endl;
}
  • 反向遍历 rbegin() 指向最后一个 rend()指向第一个的前一个

front/back

1
2
a.front(); //返回首元素 等价于 (*a.begin()) <==> a[0]
a.back(); //返回尾元素 等价于 (*--a.end()) <==> a[a.size()-1]

push_back/pop_back

1
2
a.push_back(x); //将x插入尾部
a.pop_back(); //删除最后一个元素

实例-用vector 存图

1
2
3
4
5
6
7
8
9
10
11
12
const int maxedges = 100010;
vector<int> ver[maxedges], edge[maxedges];
//保存从x到y权值为z的有向边
void add(int x, int y, int z){
ver[x].push_back(y);
edge[x].push_back(z);
}
//遍历从x出发所有边
for(int i=0;i<ver[x].size();i++){
int y=ver[x][i], z = edge[x][i];
//有向边(x,y,z)
}

pair 二元组

  • 表示一个二元组,有两个成员:first 和second,分别表示第一元和第二元
  • 通过-> 或者.访问
  • pair 可以使用比较运算符:<、>、<=、>=、==、!=,其规则是先比较first,first 相等时再比较second
  • 除了定义pair对象,还可以即时生成pair对象–make_pair函数
    • 需要两个参数,分别为元素对的首元素和尾元素。
1
2
3
pair<double, double> p1;
cin >> p1.first >> p1.second;
Q.push( make_pair(1, 2) );

map 映射

声明

1
2
map<string, int> hash;
map<pair<int,int>, vector<int> > test;

size/empty/clear/begin/end

迭代器

  • 双向访问迭代器,就是可以双向遍历,关键是它不支持随机访问,即直接下标访问,因为[]里面是key,不是下标了,支持*访问得到是二元组<key,value>,++,–
1
2
3
map<int,int>::iterator it = h.begin();
pair<int,int> p = *it;
cout<<p.first<<p.second<<endl;

insert/erase

  • 插入参数是pair,删除参数可以是it,也可以是pair
  • 也可以直接插入
1
2
3
4
5
map<int,int> h;
h.insert(make_pair(1,2));
h[2] = 3; //直接插入
h.erase(make_pair(2,3));
h.erase(it);

find

1
h.find(x);//查找key为x的二元组,返回其迭代器,不存在,则返回h.end();

[] 非常好用的

  • h[key] 可以访问元素,修改元素
  • 若key不存在,则直接创建新元组(key,zero),这个zero是广义的,如0,空串。。浪费大量空间
  • 所以,在用[]查询前,先find看能否找到

实例-map统计字符串出现次数

  • n个字符串,m个问题,每个问题询问一个字符串出现次数
1
2
3
4
5
6
7
8
9
10
map<string, int> h; //建立字符串到次数的映射
char str[25];
for(int i=1;i<=n;i++){
scanf("%s",str); h[str]++; //这里隐含创建为h[str] =0,h[str]再++
}
for(int i=1;i<=m;i++){
scanf("%s",str);
if(h.find(str) == h.end()) puts('0');
else printf("%d\n", h[str]);
}