C++ STL_Java

一.map

1.定义于头文件 #include。

2.map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。

3.基本操作函数:

begin() 返回指向 map 首元素的迭代器。

end() 返回指向 map 末元素后一元素的迭代器。

size() 返回容纳的元素数。

count() 返回拥有关键 key 的元素数。

find() 返回迭代器指向当前查找元素的位置否则返回map::end()位置。

lower_bound() 返回键值>=给定元素的第一个位置。

upper_bound() 返回键值>给定元素的第一个位置。

insert() 插入元素。

erase() 擦除元素。

clear() 从容器擦除所有元素。此调用后 size() 返回零。

empty() 检查容器是否无元素，即是否 begin() == end() 。若容器为空则为 true ，否则为 false。

4.例题 https://vjudge.d0j1a1701.cc/problem/HackerRank-cpp-maps

AC代码

#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n' 
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;

const int N=2e6+10;
int t,n,m,a,b,c,y,z,u,v,w,p[N];
string x;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	mapmp;           //创建map映射
	int i,j,k,q,type,cnt=1;
	cin>>q;
	while(q--)
	{
		cin>>type;
		cin>>x;
		if(type==1)
		{
			cin>>y;
			mp[x]+=y;            //和数组一样操作即可
		} 
		else if(type==2)
		{
			mp.erase(x);         //擦除元素x		
		} 
		else 
		{
			cout< 
 
二.set 
1.定义于头文件 #include。 
2.set 是关联容器，含有 Key 类型对象的已排序集。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现。 
3.基本操作函数: 
begin()                返回指向 set首元素的迭代器。 
end()                   返回指向 set 末元素后一元素的迭代器。 
size()                   返回容纳的元素数。 
count()                返回拥有关键 key 的元素数。 
find()                   返回迭代器指向当前查找元素的位置否则返回set::end()位置。 
lower_bound()    返回键值>=给定元素的第一个位置。 
upper_bound()   返回键值>给定元素的第一个位置。 
insert()                插入元素。 
erase()               擦除元素。 
clear()                 从容器擦除所有元素。此调用后 size() 返回零。 
empty()              检查容器是否无元素，即是否 begin() == end() 。若容器为空则为 true ，否则为 false。 
4.例题 https://vjudge.d0j1a1701.cc/problem/HackerRank-cpp-sets 
AC代码 
#include"bits/stdc++.h"
using namespace std;
int main()
{
	int n,x,y;
	ios::sync_with_stdio(false);
	sets;
	cin>>n;
	while(n--)
	{
		cin>>x>>y;
		if(x==1) s.insert(y);
		if(x==2) s.erase(y);
		if(x==3)
		{
			if(s.find(y)!=s.end()) cout<<"Yes"< 
三.vector 
1.定义于头文件 #include。 
2.vector 是封装动态数组的顺序容器。连续存储元素，这意味着不仅可通过迭代器，还能用指向元素的常规指针访问元素。这意味着指向 vector 元素的指针能传递给任何期待指向数组元素的指针的函数。vector 的存储是自动管理的，按需扩张收缩。 vector 通常占用多于静态数组的空间，因为要分配更多内存以管理将来的增长。 vector 所用的方式不在每次插入元素时，而只在额外内存耗尽时重分配。 
3.基本操作函数: 
begin()                返回指向vector首元素的迭代器。 
end()                   返回指向 vector末元素后一元素的迭代器。 
size()                   返回容纳的元素数。 
front()                  访问第一个元素。 
back()                 访问最后一个元素。 
lower_bound()    返回键值>=给定元素的第一个位置。 
upper_bound()   返回键值>给定元素的第一个位置。 
insert()                插入元素。 
erase()               擦除元素。 
clear()                 从容器擦除所有元素。此调用后 size() 返回零。 
empty()              检查容器是否无元素，即是否 begin() == end() 。若容器为空则为 true ，否则为 false。 
push_back()       将元素添加到容器末尾。 
pop_back()        移除末元素。 
4.例题 Vector-Erase - HackerRank vector-erase - Virtual Judge (d0j1a1701.cc) 
AC代码 
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n' 
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;

const int N=2e6+10;
int t,n,m,a,b,c,x,y,z,u,v,w,p[N];
char s[N],s1[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	vectorv;
	cin>>n;
	for(int i=0;i>x;
		v.push_back(x);
	}
	cin>>m;
	v.erase(v.begin()+m-1);              //删除vector中的第m个元素 
	cin>>a>>b;
	v.erase(v.begin()+a-1,v.begin()+b-1);//删除vector[a,b)中的元素 
	cout< 
四.lower_bound 
1.定义于头文件 #include。 
2lower_bound的作用是在数组a中从a[1]开始到a[n]按照cmp函数来比较进行二分查找第一个大于等于x的数的位置，如果有第一个大于等于x的数则返回该数的地址，否则返回a[n+1]的地址。
 这里面的cmp是可以不写的。
 lower_bound的返回值是查找到的数据的地址，如果要转换为int，需减去数组a。 
用一般的数组实现 
lower_bound(a+1,a+n+1,x,cmp);    //数组a存放一个有序序列，1是起始地址，n+1是结束地址，x是待查找的数值，cmp多用于对结构体的查找   

 3.例题 Lower Bound-STL - HackerRank cpp-lower-bound - Virtual Judge (d0j1a1701.cc) 
（结合vector中的函数以及迭代器实现） 
AC代码 
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n' 
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;

const int N=2e6+10;
int t,n,m,a,b,c,x,y,z,u,v,w,p[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	vectorv;
	int i,j,k,q,type,cnt=1;
	cin>>n;
	for(i=0;i>a;
		v.push_back(a);
	}
	cin>>q;
	while(q--)
	{
		cin>>y;
//查找第一个大于等于 y 的位置
		vector::iterator low=lower_bound(v.begin(),v.end(),y); 
//找到 y ，并确定它的位置即 low-v.begin()      
		if(v[low-v.begin()]==y) cout<<"Yes"<<" "<<(low-v.begin()+1)<<"n";
		else cout<<"No"<<" "<<(low-v.begin()+1)<<"n";
	}
	return 0;
}

C++ STL

Java相关栏目本月热门文章