容器
Vector
C++中的Vector相当于动态数组，连续存储空间，支持随机存取，可根据元素数量自动扩展内存。
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
v.reserve(10); // 预分配空间
v = { 0,1,2,4 };
v.emplace(v.begin() + 3, 3);
if (!v.empty())
v.emplace_back(5);
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << "size: " << v.size() << " capacity:" << v.capacity() << endl;
v.shrink_to_fit(); // 释放内存
cout << "size: " << v.size() << " capacity:" << v.capacity() << endl;
return 0;
}
String
#include<iostream>
#include<string>
using namespace std;
int main()
{
char s1[] = "hello";
string s2 = s1;
s2 += " world";
s2[5] = '_';
cout << s2 << endl;
cout << s2.substr(0, s2.find('_')) << endl;
return 0;
}
Set
C++中的Set是有序集合，内部不允许存在重复元素。
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s = { 3,2,1,0 };
s.insert(1);
s.erase(3);
if (s.find(0) != s.end())
cout << "0 is in s" << endl;
else
cout << "0 is not in s" << endl;
for (set<int>::iterator i = s.begin(); i != s.end(); i++)
cout << *i << ' ';
return 0;
}
Map
C++中的Map是有序哈希表。
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<int, int> table = { {3,30},
{1,10} };
table[2] = 20;
table.erase(1);
map<int, int>::iterator i = table.find(2);
if (i != table.end())
cout << "key: " << i->first
<< " val: " << i->second << endl;
return 0;
}
迭代器
仿函数
算法
sort
STL提供的算法全部包含在<algorithm>库中。比如针对vector数组的排序：
vector<int> v = { 3,1,2 };
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
cout << v[i] << ' '; // 1 2 3
### 仿函数
由于运算符重载机制的存在，当重载```()```运算符时，对象便可以模仿函数的行为。仅实现了```()```重载的对象称为仿函数。仿函数主要是配合STL使用的，那么为什么要用仿函数而不用普通函数呢？首先看一下普通函数能做的，下述代码使用函数指针来实现逆序排序：
```c++
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool Greater(const int& x, const int& y) {
return x > y;
}
int main()
{
vector<int> v = { 3,1,2 };
sort(v.begin(), v.end(), Greater);
for (int i = 0; i < v.size(); i++)
cout << v[i] << ' '; // 3 2 1
return 0;
}
```c++
bool GT(const int& i, const int& thresh) {
return i > thresh;
}
int main()
{
vector<int> v = { -1,-5,1,6,7 };
int res = count_if(v.begin(), v.end(), GT);
cout << res << endl;
return 0;
}
然而上述代码会报错，原因就在于count_if的谓词参数是Unary的，即只接受一元谓词，上述代码如果要改的话只能将thresh写成全局变量。相比于普通函数，仿函数的好处在于可以以成员属性的方式来隐藏一些状态。在该例子中，使用仿函数来实现的代码如下所示：
class GT {
int thresh;
public:
GT(const int& thresh) {
this->thresh = thresh;
}
bool operator()(const int& i) {
return i > this->thresh;
}
};
int main()
{
vector<int> v = { -1,-5,1,6,7 };
int res = count_if(v.begin(), v.end(), GT(0));
cout << res << endl;
return 0;
}
实际上，C++官方库自带了若干仿函数，如对数组的逆序排序可写成：
// #include<functional>
sort(v.begin(), v.end(), greater<int>());
for_each
C++中的for_each算法相当于Python中的map函数，简而言之就是对于一个可迭代对象，对其中的每一个元素都使用同一个函数做处理。如下所示：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void addOne(int& x) {
x += 1;
}
int main()
{
vector<int> v = { 3,1,2 };
for_each(v.begin(), v.end(), addOne);
for (int i = 0; i < v.size(); i++)
cout << v[i] << ' ';
return 0;
}
find
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class GT1 {
public:
bool operator()(const int& x) {
return x > 1;
}
};
int main()
{
vector<int> v = { 3,1,2 };
if (find(v.begin(), v.end(), 1) != v.end())
cout << "find it!" << endl;
if(find_if(v.begin(),v.end(),GT1())!=v.end())
cout << "find a item GT 1!" << endl;
return 0;
}
merge
```c++
vector<int> v1 = { 0,2 };
vector<int> v2 = { 1,3 };
vector<int> v3;
v3.resize(v1.size() + v2.size());
merge(v1.begin(), v1.end(),
v2.begin(), v2.end(),
v3.begin());
replace
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class LT0 {
public:
bool operator()(const int& x) {
return x < 0;
}
};
int main()
{
vector<int> v = { -1,0,1,2 };
replace(v.begin(), v.end(), 0, 9);
replace_if(v.begin(), v.end(), LT0(), 0);
return 0;
}
accumulate
// #include<numeric>
vector<int> v = { -1,0,1,2 };
int acc = accumulate(v.begin(), v.end(), 0);
set
这里的set不是指容器set，而是指集合相关的算法。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v1 = { 0,1 };
vector<int> v2 = { 1,2 };
vector<int> v3, v4, v5;
vector<int>::iterator it;
v3.resize(min(v1.size(), v2.size()));
it = set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(), v3.begin());
v3.resize(it - v3.begin()); // {1}
v4.resize(v1.size() + v2.size());
it = set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(), v4.begin());
v4.resize(it - v4.begin()); // {1,2,3}
v5.resize(max(v1.size(), v2.size()));
it = set_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(), v5.begin()); // 属于v1但不属于v2
v5.resize(it - v5.begin()); // {0}
return 0;
}