C++ | QaQ

冷知识

vector可以直接比大小…

C++ 基础语法

using

using ... = ...;
// example
using ll = long long;
typedef long long ll;

在语法的别名声明，using的使用类似于typedef，但用法更为精妙。

stoi

1 2	int stoi (const string& str, size_t* idx = 0, int base = 10); int stoi (const wstring& str, size_t* idx = 0, int base = 10);

stoi()的输入要不为空，否则可以使用atoi(().c.str())

sstream

istringstream类用于执行C++风格的字符串流的输入操作，支持>>;

ostringstream类用于执行C++风格的字符串流的输出操作，支持<<；

stringstream类同时可以支持C++风格的串流的输入输出操作，同时支持>>和<<；

即 stringstream = istringstream + ostringstream。

iota

numeric
详细的说明
定义在 numeric 头文件中的 iota() 函数模板会用连续的 T 类型值填充序列。前两个参数是定义序列的正向迭代器，第三个参数是初始的 T 值。第三个指定的值会被保存到序列的第一个元素中。保存在第一个元素后的值是通过对前面的值运用自增运算符得到的。当然，这意味着 T 类型必须支持 operator++()。

__builtin_popcount

统计二进制中1的个数

STL

C++ STL

不错的博客链接

distance

详细的说明
distance() 函数用于计算两个迭代器表示的范围内包含元素的个数
distance() 函数定义在<iterator>头文件，并位于 std 命名空间中
distance() 函数用于计算两个迭代器表示的范围内包含元素的个数，其语法格式如下：

template
typename iterator_traits::difference_type distance (InputIterator first, InputIterator last);

其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回[first, last)范围内包含的元素的个数。

注意，first 和 last 的迭代器类型，直接决定了 distance() 函数底层的实现机制：
- 当 first 和 last 为随机访问迭代器时，distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数，其时间复杂度为O(1)常数阶；
- 当 first 和 last 为非随机访问迭代器时，distance() 底层通过不断执行 ++first（或者 first++）直到 first==last，由此来获取 [first, last) 范围内包含元素的个数，其时间复杂度为O(n)线性阶。

find

详细的说明
find() 为在输入迭代器所定义的范围内查找单个对象的算法，它可以在前两个参数指定的范围内查找和第三个参数相等的第一个对象。

find 算法会返回一个指向被找到对象的迭代器，如果没有找到对象，会返回这个序列的结束迭代器。
1
InputIterator find (InputIterator first, InputIterator last, const T& val);

lower_bound

详细的说明
find()、find_if()、search() 等这些函数的底层实现都采用的是顺序查找（逐个遍历）的方式，在某些场景中的执行效率并不高。
C++ STL标准库中还提供有 lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。

lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

upper_bound

详细的说明

用于在指定范围内查找大于目标值的第一个元素

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

__gcd()

algorithm
__gcd(a, b)求解最大公因数

next_permutation

详细的说明

next_permutation() 会生成一个序列的重排列，它是所有可能的字典序中的下一个排列，默认使用 < 运算符来做这些事情。它的参数为定义序列的迭代器和一个返回布尔值的函数，这个函数在下一个排列大于上一个排列时返回 true，如果上一个排列是序列中最大的，它返回 false，所以会生成字典序最小的排列。

std::vector<int> range {1,2,3,4};
do {
    std::copy (std::begin(range), std::end(range), std::ostream_iterator<int>{std::cout, " "});
    std::cout << std::endl;
}while(std::next_permutation(std::begin(range), std::end(range)));

prev_permutation

详细的说明
next_permutation() 是按照字典升序的方式生成的排列。当我们想以降序的方式生成排列时，可以使用 prev_permutation()。

prev_permutation 和 next_permutation() 一样有两个版本，默认使用 < 来比较元素。因为排列是以降序的方式生成的，所以算法大多数时候会返回 true。当生成最大排列时，返回 false。

std::vector<double> data {44.5, 22.0, 15.6, 1.5};
do {
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<double> {std::cout, " "});
    std::cout << std::endl;
} while(std::prev_permutation(std::begin(data), std::end(data)));

binary_search

详细的说明
二分查找值

set

详细的说明](http://c.biancheng.net/view/7192.html))

后续程序中在使用 set 容器时，需手动注明 std 命名空间（强烈建议初学者使用,但不是必须的）

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

C++ 11 标准还为 set 类模板新增了移动构造函数，其功能是实现创建新 set 容器的同时，利用临时的 set 容器为其初始化。
set 类模板还支持取已有 set 容器中的部分元素，来初始化新 set 容器。
借助 set 类模板定义中第 2 个参数，我们完全可以手动修改 set 容器中的排序规则。
若干成员方法。。。

unique

详细的说明
unique() 算法可以在序列中原地移除重复的元素，这就要求被处理的序列必须是正向迭代器所指定的。在移除重复元素后，它会返回一个正向迭代器作为新序列的结束迭代器。可以提供一个函数对象作为可选的第三个参数，这个参数会定义一个用来代替 == 比较元素的方法。
容器的成员函数 erase() 会移除新的结束迭代器之后的所有元素，因此 end(words) 会返回 end_iter。

可以将 unique() 运用到字符串中的字符上：

1
2
3

string text {"There's no air in spaaaaaace!"};
text.erase(std::unique(std::begin(text), std::end(text),[](char ch1, char ch2) { return ch1 = ' '&& ch1 = ch2; }), std::end(text));
std::cout << text << std::endl; // Outputs: There's no air in spaaaaaace!

这里使用 unique() 会移除字符串 text 中的连续重复的空格。这段代码会用 unique() 返回的迭代器作为 text 成员函数 erase() 的第一个参数，而且它会指向被移除的第一个字符。erase() 的第二个参数是 text 的结束迭代器，因此在没有重复元素的新字符串之后的所有字符都会被移除。