跟着Stanford的cs系列补了一下C++。虽然打ACM一直在用C++，但是也只是用的C with cin cout，看课的同时练练听力磨磨耳朵，也有很多收获。

Stream

$Stream$（流），分为输入流（$istream$），输出流（$ostream$）和双向流（$iostream$），其中 $istream$ 又分为 $ifstream$ 与 $istringstream$ ，分别用于文件与字符串的输入，$ostream$ 与 $iostream$ 同理。其中 $cin$ ，$cout$ 分别是输入流与输出流的一个实例，专用于向控制台或命令行输入输出。

以字符串相关的流为例，对于输出流有：

1
2
3
4
5
6
7
8
9
ostringstream s("cat is cute ");
cout<<s.str()<<endl;//cat is cute
s<<"car";
cout<<s.str()<<endl;//car is cute

ostringstream p("cat is cute",ostringstream::ate);
cout<<s.str()<<endl;//cat is cute
s<<"car";
cout<<s.str()<<endl;//cat is cute car

要注意什么时候插入时是从头插入，什么时候是插入在尾部。

对于输入流，有：

1
2
3
4
5
6
7
8
9
istringtream s("i am 18.5 years old");
string n,m,p;
int a;
s>>n>>m>>a;
getline(s,p);
//n="i"
//m="am"
//a="18"
//s=".5 years old"

对于输入流有4个标志符 $s.good(),s.fail(),s.eof(),s.bad()$ ，其中 $s.fail()$ 判断是否类型错误，$s.eof()$ 表示是否到达流的末尾。

要注意 cin 和 getline的区别，在缓冲区读取时，cin 读到空格或 '\n' 时会马上停下，当再次读入时才会跳过空格或 '\n' ；而 getline 读入时遇到 '\n' 时会直接跳过并停下。

Template

$Template$（模板）用法比较简单，如下：

1
2
3
4
5
template<typename T>
T add(T a,T b)
{
    return a+b;
}

在调用时可以指明 add<T>(x,y) ，也可以直接传入参数。还可以传入函数。

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
#include<bits/stdc++.h>
using namespace std;

bool lesst5(int t)
{
    return t<=5;
}

template<typename T,typename U>
int countt(T begin,T end,U condition)
{
    int tot=0;
    for(auto i=begin;i!=end;++i)
    {
        if(condition(*i))tot++;
    }
    return tot;
}

// int lim=5;

int main()
{
    vector<int>vec{0,1,2,3,4,5,6,7};

    cout<<countt(vec.begin(),vec.end(),lesst5);
    system("pause");
    return 0;
}

Lambda function

形式：

1
auto func=[]()->returntype{};

[] 中捕获的参数为在函数内部可以用到的参数（全局变量除外），可以按值捕获，也可以按引用捕获，[&] 表示按引用捕获所有变量，[=] 同理。

() 表示函数使用的形参。returntype可以省略。如：

1
2
3
4
auto func=[val](int x)
{
	return x<val;
}

Lambda表达式也可实现调用自身，使用：

1
2
3
4
5
6
auto dfs=[...](auto &self,...)
{
	//function
    self(self,...)
}
dfs(dfs,...)

如使用Lambda表达式

构造全排列：

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
#include<iostream>
#include<vector>
#include<iterator>

int main()
{
    int n;
    std::cin>>n;
    std::vector<int>per,check(n);
    auto gene=[&](auto &self,int st)
    {
        if(st==n)
        {
            std::copy(per.begin(),per.end(),std::ostream_iterator<int>(std::cout," "));
            std::cout<<std::endl;
            return ;
        }

        for(int i=1;i<=n;++i)
        {
            if(!check[i-1])
            {
                check[i-1]=1;
                per.push_back(i);
                self(self,st+1);
                check[i-1]=0;
                per.pop_back();
            }
        }
    };

    gene(gene,0);
    system("pause");
}

另外，Lambda表示式还有很多用处，如用在排序中：

1
2
3
4
5
6
7
auto comp=[](string a,string b)
{
	return a.size()<b.size();
};

vector<string>str{...}
sort(str.begin(),str.end(),comp);

再比如自定义某些STL排序顺序

1
2
3
4
5
6
7
auto func = [](int a, int b) { return a > b; };

//实现小根堆
std::priority_queue<int, std::vector<int>, decltype(func)> q(func);

//set从大到小排序
std::set<int, decltype(func)> q(func);

STL functions

Copy

一般语法：

1
std::copy(first, last, d_first);

first 与 last 表示被复制的容器的起始与结束迭代器，d_first 表示目标容器的起始迭代器。

要保证目标容器以分配空间，即：

1
2
3
4
5
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);  // 确保目标容器有足够的空间

// 复制 source 中的元素到 destination 中
std::copy(source.begin(), source.end(), destination.begin());

若不分配，则需使用 back_inserter

1
2
3
4
5
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination;  // 不需要预先分配空间

// 使用 back_inserter 将 source 的内容复制到 destination
std::copy(source.begin(), source.end(), std::back_inserter(destination));

$copy$ 还可以直接打印容器元素。

1
std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, "\n"));

将 vec中的元素复制到 ostream_iterator 中，实现输出，每两个元素以回车间隔。

nth_element

可以在 $O(n)$ 时间内找到第 $n$ 小的元素。

1
std::nth_element(vec.begin(),vec.begin()+x,vec.end());

将第 $x+1$ （0指引）小的元素放在 vec[x] 上，保正 vec[0~x-1] 比 vec[x] 小（无序），vec[x+1~n-1] 比 vec[x] 大（无序）。也可以加入自定义比较函数。

Stable_partition

在 $O(nlogn)$ 时间内进行排序，将容器内符合条件的元素放在前面，不符合条件的放在后面，且相对顺序不变。

1
2
3
4
5
std::vector<int>numbers={1,2,3,4,5,6,7,8,9,10};

// 使用 stable_partition 将偶数移到前面
auto is_even=[](int n){return n%2==0;};
std::stable_partition(numbers.begin(),numbers.end(),is_even);

remove_if

可以将所有不满足条件的数放在容器末尾，并且返回一个迭代器指向第一个被移除的数的位置。

1
2
3
4
5
6
7
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 使用 std::remove_if 将奇数移到序列末尾，并获得新末尾的迭代器
auto rmv=[](int n){return n%2==1};
auto newEnd=std::remove_if(numbers.begin(),numbers.end(),rmv);

numbers.erase(newEnd, numbers.end());

Const correctness

在代码中正确使用 const 关键字。

Const and pointer

1
2
3
int *const p;//constant pointer to a non-constant int
const int *p;//non-constant pointer to a constant int
const int *const p;//constant pointer to a constant int

Const and member functions

1
2
3
4
5
6
7
8
9
10
11
12
13
struct a
{
	void func1()const;//保证不修改对象状态
	void func2(); 
};
...
void f(const a &p,a &q)
{
	p.func1();//ok
	p.func2();//not ok
	q.func1();//ok
	q.func2();//ok
}