C++ STL模板——题单#2

1.容器适配器——（stack）栈与（queue）队列

//stack
stack<int> s;
stack< int, vector<int> > st;  //覆盖基础容器类型，使用vector实现st
s.empty();  //判断stack是否为空，为空返回true，否则返回false
s.size();   //返回stack中元素的个数
s.pop();    //删除栈顶元素，但不返回其值
s.top();    //返回栈顶元素的值，但不删除此元素
s.push(item);   //在栈顶压入新元素item


//queue
queue<int> q; 
q.empty();  //判断队列是否为空
q.size();   //返回队列长度
q.push(item);   //队尾压入一个新元素
q.front();  //返回队首元素的值，但不删除该元素
q.back();   //返回队尾元素的值，但不删除该元素
q.top();    //返回具有最高优先级的元素值，但不删除该元素

2.Vector

vector<int>v;
vector<vector<int>>v2(N);	//二维向量 N:N行
v.push_back(a);		//在数组最后添加数据a
v.pop_back();		//删除数组的最后一个数据
v.size();			//容器中实际数据个数
v.clear();			//清除容器中所有数据
vector<int>::iterator it;//声明一个迭代器
v.begin();			//第一个元素
v.end();			//最后一个元素
//动态二维数组设置	法1
for(int i=0;i<v2.size();i++)
{
    v2[i].resize(M)//M:M列;
}
//动态二维数组设置	法2
vector<vector<int> > obj(N, vector<int>(M));

3.deque——双端队列

deque<int>deq;
deq.front();	//返回第一个元素
deq.back();		//返回最后一个元素。
deq.push_front(x);	//把元素x插入到双向队列的头部
deq.pop_front();	//弹出双向队列的第一个元素
deq.push_back(x);	//把元素x插入到双向队列的尾部
deq.pop_back();	//弹出双向队列的最后一个元素

4.list——双向链表

list<int>ls;
ls.assign();	//给list赋值 
ls.back(); 	//返回最后一个元素 
ls.begin(); 	//返回指向第一个元素的迭代器 
ls.clear(); 	//删除所有元素 
ls.empty(); 	//如果list是空的则返回true 
ls.end(); 	//返回末尾的迭代器 
ls.erase(); 	//删除一个元素 
ls.front(); 	//返回第一个元素 
ls.get_allocator(); 	//返回list的配置器 
ls.insert(); 	//插入一个元素到list中 
ls.max_size(); 	//返回list能容纳的最大元素数量 
ls.merge(); 	//合并两个list 
ls.pop_back(); 	//删除最后一个元素 
ls.pop_front(); 	//删除第一个元素 
ls.push_back(); 	//在list的末尾添加一个元素 
ls.push_front(); 	//在list的头部添加一个元素 
ls.rbegin(); 	//返回指向第一个元素的逆向迭代器 
ls.remove(); 	//从list删除元素 
ls.remove_if(); 	//按指定条件删除元素 
ls.rend(); 	//指向list末尾的逆向迭代器 
ls.resize(); 	//改变list的大小 
ls.reverse(); 	//把list的元素倒转 
ls.size(); 	//返回list中的元素个数 
ls.sort(); 	//给list排序 
ls.splice(); 	//合并两个list 
ls.swap(); 	//交换两个list 
ls.unique(); 	//删除list中相邻重复的元素

5.map/multimap

map的键值key不可重复，而multimap可以

map<string,int> my_map;

//插入元素
my_map.insert(pair<int,string>(1,"first"));
my_map[1]="first";
my_map[2]="second";

//查找元素
my_map["first"]=1;
cout<<my_map.count("first")<<endl;
my_map.find(1)==my_map.end() //没找到

//删除元素
my_map.erase(my_map.find(1))


mp.begin();	//头部
mp.clear();	//清空所有元素
mp.count();	//返回指定元素出现次数
mp.empty();	//若map为空返回true
mp.end();	//返回尾部
mp.erase();	//删除一个元素
mp.find();	//查找一个元素
mp.insert();	//插入元素
mp.key_comp();	//返回比较元素key的元素
mp.lower_bound();	//返回键值>=给定元素个数
mp.max_size();	//可以容纳最大元素个数
mp.size();	//返回map元素个数
mp.upper_bound();	//返回键值>给定元素的第一个位置
mp.value_comp();	//返回比较元素value的函数

• map中的元素是自动按Key升序排序

• map自定义排序：PTA L1-034 点赞

//用pair,直接map会报错
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.second == b.second)return a.first > b.first;
	return a.second > b.second;
}

map<ll, int>pyq;
for (int i = 0; i < n; i++)
{
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        ll num;
        cin >> num;
        pyq[num]++;
    }
}
//将map数据转化成vector<pair<ll,int>>
map<ll, int>::iterator it;
vector < pair<ll, int>>vec(pyq.begin(), pyq.end());
sort(vec.begin(), vec.end(), cmp);
cout << vec[0].first << " " << vec[0].second << endl;

6.set/multiset

set容器内的元素会被自动排序，升序。

若想改从大到小，可以进行重载

bool operator()(int v1, int v2)
{
	return v1 > v2;
}

• 列表字符串操作

//字符串转集合
string phone="156528333"
set<char>phone_set;
for(int i=0;i<phone.length();i++)phone_set.insert(phone[i]);
//获取集合长度
phone_set.size();
//获取字符串中某字符出现次数
int num=count(phone.begin(),phone.end(),'1');

7.题单例题:

四个数的总和为0

有4个集合A、B、C、D，每个集合都是由m个整数组成。（m<=2000）

要求分别从四个集合中挑出一个元素a、b、c、d，使得a+b+c+d=0。（同一集合中每个元素的值不大于2的28次方）

问有多少种不同的选法？

解题方法：

建立multiset四个集合

利用map映射，mp[a+b]++;记录a与b相加数值；

再cnt+=mp[-(c+d)];——若-(c+d)=(a+b)则说明该方案可行，计数；

multiset<ll>a, b, c, d;
ll x;
for (int i = 0; i < m; i++)
{
    cin >> x;
    a.insert(x);
}
for (int i = 0; i < m; i++)
{
    cin >> x;
    b.insert(x);
}
for (int i = 0; i < m; i++)
{
    cin >> x;
    c.insert(x);
}
for (int i = 0; i < m; i++)
{
    cin >> x;
    d.insert(x);
}
ll cnt = 0;
map<int, int>mp;

for (auto it_a : a)
{
    for (auto it_b : b)
	{
        mp[it_a + it_b]++;
	}
}
for (auto it_c : c)
{
	for (auto it_d : d)
    {
    	cnt+=mp[-(it_c + it_d)];
    }
}
cout << cnt ;

平衡膳食

我们假设一个人吃一顿饭至少要摄入三种不同类型的维生素才能满足营养需求。

现在这里有含维生素 A 的食物 a 份，含维生素 B 的食物 b 份，含维生素 C 的食物 c 份和含维生素 D 的食物 d 份，请问这些食物最多可以满足多少人的营养需求。

解题技巧：

四个种类的食物数量进行排序，每次都是最多的三个减减，直到没法三个组成。

int p[4];
int cnt = 0;
cin >> p[0] >> p[1] >> p[2] >> p[3];
sort(p, p + 4);
while(p[1]!=0)
{
    p[1]--;
    p[2]--;
    p[3]--;
    sort(p, p + 4);
    cnt++;
}
cout << cnt << endl;