wp-studio01 / blog

My Blog

Here is HelloWorld

Platform&Tools

Languages

blog's Issues

STL map使用方法

STL map使用方法

背景知识

map，STL用来建立映射的容器

数组就是一个简单的映射

比如说，a[5]=8;这句话就是把8映射到5

但是这只能实现int值映射，这正是map的**：建立自定义类型映射

map对象声明与使用

map<type1,type2> object;

type1和type2为映射类型：

object[type1对象]=type2对象;

map性质

map内部被去重排序，效率极高。

map遍历

见STL之map遍历

C++获取系统运行时间

C++获取系统运行时间

函数名称及作用

GetTickCount，获取系统运行时间，毫秒为单位，精度18ms

参数

本函数无参数

返回值

系统运行毫秒数

实例

拿GetTickCount作为srand的随机种子

srand(GetTickCount());

等待几秒

int lasttime=GetTickCount();
while(GetTickCount()-lasttime>1000);

新系统！

猛戳我

我的第一个帖子

test

别人也可以发帖？

？？？

STL之map遍历

STL之map遍历

经典方法：

for(auto i=a.begin();i!=a.end();i++)//a为map对象
{
    cout<<i->first<<" "<<i->second<<endl;
}

c++11 STL专用循环

for(auto& i : a)
{
    cout<<i.first<<" "<<i.second<<endl;
}

迭代器高级用法

迭代器高级用法

C++的迭代器功能很强大，但是先前介绍的只是冰山一角，这里，就深入了解一下迭代器

头文件：#include<iterator>

迭代器类型

迭代器分为输入，输出，正向，双向，随机访问

咳，不说了，一个表格清晰易懂

	输入迭代器	输出迭代器	正向迭代器	双向迭代器	随机访问迭代器
*it	不支持	支持	支持	支持	支持
(*it)=a	支持	不支持	支持	支持	支持
it++	支持	支持	支持	支持	支持
it--	不支持	不支持	不支持	支持	支持
it+i	不支持	不支持	不支持	不支持	支持
it-i	不支持	不支持	不支持	不支持	支持

再通过一个表介绍各种容器的迭代器类型

	输入迭代器	输出迭代器	正向迭代器	双向迭代器	随机访问迭代器
vector	支持	支持	支持	支持	支持
queue	不支持	不支持	不支持	不支持	不支持
stack	不支持	不支持	不支持	不支持	不支持
list	支持	支持	支持	支持	不支持
forward_list	支持	支持	支持	不支持	不支持
map	支持	支持	支持	支持	不支持

插入迭代器

引入

copy函数只有在目标容器有足够的空间时才能正常运行，否则会出错

copy还会覆盖原有元素，如果要保留原元素并插入呢？

back_insert_iterator

对此迭代器输出将导致在尾部插入相应元素

警告：此迭代器只对可以在尾部做快速插入的容器有效

front_insert_iterator

对此迭代器输出将导致在头部插入相应元素

警告：此迭代器只对可以在头部做快速插入的容器有效

insert_iterator

对此迭代器输出将导致在迭代器指向元素的前面插入相应元素

反向迭代器

如果你要对容器反向输出，最好用反向迭代器

代码片段：

vector<int> a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
for(auto i=a.rbegin();i!=a.rend();i++)
{
    cout<<*i<<" ";
}//输出5 4 3 2 1

导致反向输出

今个字数差不多了，STL迭代器是个很庞大的项目，讲不完的，就写到这吧

STL迭代器入门

STL迭代器入门

STL很方便，但是这不是它的极限，迭代器是可以将容器的力量发挥到极致的工具

迭代器就像是指针（其实就是指针的typedef），没学过指针的小盆友可以粗略地理解成下标

迭代器有很多知识，很多，很杂，这里先入个门，拿vector开刀

声明迭代器

vector<int>::iterator it;

解引用迭代器

*it

看到了吧，迭代器就像是指针

获取迭代器

可是我们有了迭代器不知道怎么得到迭代器啊？

莫担心，现在有个vector<int>对象叫a，它的头一个元素的迭代器叫做a.begin()，最后一个元素的后面（也就是超尾）的迭代器叫做a.end()

迭代器算法

sort

排序算法

sort(a.begin(),a.end());

显然没写完

自己百度去吧

C++程序内包含二进制文件并提取

C++程序内包含二进制文件并提取

在main.cpp内写下此函数、

bool ExtractResource(LPCTSTR strDstFile, LPCTSTR strResType, LPCTSTR strResName)
{
	HANDLE hFile = ::CreateFile(strDstFile, GENERIC_WRITE, NULL, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_TEMPORARY, NULL);
	if (hFile == INVALID_HANDLE_VALUE)
		return false;
	HRSRC      hRes    = ::FindResource(GetModuleHandle(NULL), strResName, strResType);
	HGLOBAL    hMem    = ::LoadResource(NULL, hRes);
	DWORD      dwSize  = ::SizeofResource(NULL, hRes);
	DWORD dwWrite = 0;
	::WriteFile(hFile, hMem, dwSize, &dwWrite, NULL);
	::CloseHandle(hFile);
	return true;
}

再在resource.rc内写下这样的代码

1/*你的ID*/ RCDATA "你的文件名"

运行ExtractResource("提取文件名",RT_RCDATA,MAKEINTRESOURCE(1/*你的ID*/));即可

C++的快读快写

C++的快读快写

快读：

int read()
{
    int n=0,f=1;
    char c;
    c=getchar();
    if(c=='-') f=-1;
    else n=c-'0';
    while((c=getchar())>='0'&&c<='9')
    {
        n*=10;
        n+=c-'0';
    }
    return n*f;
}

快写：

void write(int n)
{
    int Stack[20],top=0;
    while(n)
    {
        Stack[top++]=n%10;
        n/=10;
    }
    while(top)
    {
        putchar(Stack[--top]+'0');
    }
}

抓紧研发新的系统

新的系统正在研发了，旧的系统不好用

变量命名法

变量命名法

变量的命名是个大问题，如果没有好的命名，后期可能连自己都不知道变量代表什么

变量命名规则：第一个字母是前缀，后面是几个单词，单词首字母大写

例如，bool型变量，表示是否显示总值：

bIsVisibleTotal

前缀是有讲究的：

前缀	含义
c	char
b	bool
d	int
f	double

其他还有一些，自己探索吧

这种东西叫做驼峰命名法

algorithm头文件常用函数

algorithm头文件常用函数

algorithm头文件是stl算法函数，几乎都要用到迭代器

（不过，stl使用泛型编程，所以迭代器可以是用户定义的类类型）

sort

原型：

template<typename _RandomAccessIterator>//RandomAccessIterator指出这是一个随机访问迭代器
	inline void
	sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

排序算法，接受两个随机访问迭代器作为参数，排序区间[first,last)

min,max

大家都会，不讲了

reverse

原型：

template<typename _BidirectionalIterator>//BidirectionalIterator指出这是一个双向迭代器
	inline void
	reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)

反转区间[first,last)

find

原型：

template<typename _InputIterator, typename _Tp>//InputIterator指出这是一个输入迭代器
	inline _InputIterator
	find(_InputIterator __first, _InputIterator __last,
	     const _Tp& __val)

寻找[first,last)中等于val的值，找到则返回他的迭代器，找不到则返回last迭代器

count

原型：

template<typename _InputIterator, typename _Tp>//InputIterator指出这是一个输入迭代器
	typename iterator_traits<_InputIterator>::difference_type
	count(_InputIterator __first, _InputIterator __last, const _Tp& __value)

返回[first,last)中的value出现次数

transform

原型：

template<typename _InputIterator, typename _OutputIterator,
	         typename _UnaryOperation>
	_OutputIterator
	transform(_InputIterator __first, _InputIterator __last,
	          _OutputIterator __result, _UnaryOperation __unary_op)

将区间[first,last)中所有元素应用unary_op运算符，并将结果存储到result中

你可能很好奇这个东西有什么用，可以将字符串转换成全小写

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
    cin>>s;
    transform(s.begin(),s.end(),s.begin(),tolower);
    cout<<s;
}

想要一样的blog？10分钟搞定

这个也是参考了xgugugu的教程，但是那个已经停更了，我再更一个，永远开放

首先下载这个仓库

然后打开blog.json

URL记录的是你的网址

user记录的是你的用户名

menu是顶上的菜单从右到左显示的

repo记录的是你的仓库名

其他可以参考我的blog.json

其他的别改，上传到你的仓库里

设置Pages，等待5分钟，即可

Git专题讲解

待续

时间复杂度

时间复杂度

时间复杂度是描述程序运行时间的一个标准

大O表示法是时间复杂度的表示方法

例如：

$O(n\log n)$

大O里面的东西代表要执行几次代码

区间贪心典型模板

区间贪心典型模板

区间选择

学校早年只有一个大礼堂和n个活动，给出活动的起始时间和结束时间，求出最多安排几个活动

输入样例

5
1 4
2 6
5 8
1 8
4 8

输出样例

2

数据范围

0<起始时间<结束时间<1000

0<n<=1000

分析

很明显，处理前要排序

按什么排序呢？

按结束时间排序，因为结束时间越靠前，后面就可以安排更多的活动

完整代码：

#include <bits/stdc++.h>
using namespace std;
struct Node
{
	int b,e;
}a[100005];
int ed=0,cnt;
bool cmp(Node x,Node y)
{
	return x.e<y.e;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].b>>a[i].e;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i].b>ed)
		{
			ed=a[i].e;
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

使用vector和array代替数组

使用vector和array代替数组

vector和array都是代替数组的东西

vector

声明与访问

vector<int> a;

a[5]=8;

常用成员函数

push_back(value_type a)

在向量（向量就是vector，下同）末尾添加一个元素

警告：使用push_back可能使此向量的所有迭代器失效

pop_back()

删除向量末尾的元素

insert(value_type a,iterator it)

在it的前面插入a

警告：使用insert可能使插入点之后的迭代器失效

erase(iterator it)

删除it这个元素

警告：使用erase可能使删除点之后的迭代器失效

resize(int n)

没什么用，重置向量大小

警告：如果使用这个函数，则不能使用push_back,pop_back,insert,erase函数

使用STL map来实现桶

使用STL map来实现桶

桶，大家都用过吧，但是对于数据范围比较大（或者没有数据范围）的，就没有用武之地了

使用map来实现桶可以规避这种问题（没猜错的话还不会爆内存）

桶排序，数据范围long long

#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<long long,int> tong;
    int n;
    cin>>n;
    while(n--)
    {
        int t;
        cin>>t;
        tong[t]++;
    }
    for(auto& i : tong)//C++11新增，C++98的用下面这行
    //for(auto i=tong.begin();i!=tong.end();i++)
    //使用这行的方法稍微不一样
    //i.second换成i->second；i.first换成i->first
    {
        while(i.second)
        {
            cout<<i.first<<" ";
            i.second--;
        }
    }
    return 0;
}

很好的规避了开桶数组爆内存的问题

用STL的set来去重排序

用STL的set来去重排序

引入

如果题目说到去重排序，我们肯定想到了桶，实际上set也可以实现。

set有一个成员insert函数，可以实现插入时自动去重排序。

使用

set<int> a;
a.insert(5);
a.insert(4);
a.insert(3);
a.insert(5);
a.insert(2);
a.insert(1);
for(auto& i : a)//这个方法可以参考另一篇笔记
{
    cout<<i<<" ";
}//输出1 2 3 4 5

解决raw.githubusercontent.com无法访问的问题

打开国内的Gitee，找到克隆Github仓库按钮，克隆你需要的仓库，然后在程序里使用国内Gitee的raw链接就行了

测试两下

测试两下