容器

Posted on | In | Visitors:

This is my blog.
在STL中容器非常重要，有时候数组难以解决活着很麻烦时，容器的优势便显示出来了。

vector

头文件 <vector>

变量声明 vector<type>name;

优点：

1.不限制长度
2.访问数据更安全
3.有正向反向迭代器
4.动态插入和删除

各项参数

参数 用途
push_back 在数组的最后添加一个数据
pop_back 去掉数组的最后一个数据
at 得到编号位置的数据
begin 得到数组头的指针
end 得到数组的最后一个单元+1的指针
front 得到数组头的引用
back 得到数组的最后一个单元的引用
size 当前使用数据的大小
erase 删除指针指向的数据项
clear 清空当前的vector
rgebin 得到vector反转后的开始指针
rend 得到vector反转后的结束指针
empty 判断vector是否为空
swap 与另一个vector交换数据

注：a.erase(pos)删除pos位置的数据，传回下一个数据的位置

a.erase(begin,end) 删除[begin,end）区间的数据，传回下一个数据的位置

其他：setw(int len)控制格式长度

emplace_back与push_back的区别

其他

当vector作为参数时，使用引用传参数，可以避免不必要的值复制。当然若是不希望vector变化，就只能穿形参喽。

set

set实现了红黑树的平衡二叉检索树，，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。
利用set插入时，是按从小到大排序的这一特性，可以简单的解决一些问题（如：UVA10815）。

头文件 <set>

变量声明 set<type>name;

优点：

1.检索快速

各项参数

参数 用途
insert 插入
erase 删除指定键值的元素
clear 清空当前的set
find 查找指定键值的元素

注 还有set_union取并集，set_intersection取交集

multiset

set里的元素不可以重复，但是multiset可以。

map

map是一类关联式容器。就是从键(key)到值(value)的映射。因为重载了运算符[]，map像是数组的高级版。
例如可以用一个mapmonth_name来表示“月份名字到月份编号”的映射，然后用month_name[“july”]=7;这样的方式来赋值。map又称为“关联数组”。sample_footnote

sample_footnote. 转自刘汝佳的《算法入门经典》 ↩

头文件 <map>

变量声明 map<type1，type2>name;

优点：

1.快速插入删除记录
2.可以自己配对

各项参数

map

例题：UVA156

找出不能通过字母重排得到文本中另一个单词（判断时不区分大小写），输出所有符合的单词，按字典序排序，所有大写字母在所有小写字母的前面。输入以‘#’结束

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string,int>cnt;
vector<string>words;
//将单词标准化
string repr(const string& s){
		string ans=s;
		for(int i=0;i<ans.length();i++){
			ans[i]=tolower(ans[i]);
		sort(ans.begin(),ans.end());
		return ans;
}
int main(){
		int n=0;
		string s;
		while(cin>>s){
				if(s[0]=='#')break;
				words.push_back(s);
				string r=repr(s);
				if(!cnt.count(r)) cnt[r]=0;
				cnt[r]++;
		}
		vector<string>ans;
		for(int i=0;i<words.size();i++)
			if(cnt[repr(words[i])]==1) 
				ans.push_back(words[i]);
		sort(ans.begin(),ans.end());
		for(int i=0;i<ans.size();i++)
			cout<<ans[i]<<endl;
		return 0;
	}

由此我们可以看到，如果没有良好的程序设计，就无法发挥STL的威力，如果没有想到“标准化”这个思路，就很难用map简化。

iterator

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。
目前我所需要用到迭代器的，使用在以上容器遍历之时。
给个栗子吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include <vector>
using namespace std;
vector<int>a;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        a.push_back(x);
    }
    vector<int>::iterator it=a.begin();
    for(;it!=a.end();it++){
        cout<<*it<<endl;
    }
    return 0;
}

pair

pair是一种模板类型，其中包含两个数据值，两个数据的类型可以不同，基本的定义如下：
pair<int,string>a;
对于pair类，由于它只有两个元素，分别名为first和second，因此直接使用普通的点操作符即可访问其成员。

一些常用函数

在使用STL容器时，配套上一些函数，会使程序更加优美。当然，这些函数也可以使用在容器的原型—数组之上。
1.sort(begin,end,compare());//默认从小到大 2.lower_bound(begin,end,x);//返回第一个小于x的地址

推荐一个网站http://www.cplusplus.com
转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽