1. 截取字符串

   string.substr(pos, n);
   * 从位置pos处截取长度为n的字符串

扩展：
string.substr(pos);
* 从位置pos处截取到字符串的末尾
2. 进制转换

```
cin >> hex/dec/oct >> num;
cout << hex/dec/oct << num;
```

• hex表示十六进制；dec表示十进制；oct表示八进制。

• 转译字符串str中的整数值

  stoi(str, pos, base)
  舍弃所有空白符，直到找到首个非空白符，然后取尽可能多的字符组成底base的整数表示，并将它们转换成一个整数值。
  若base为0，则自动检测数值进制；若前缀为0，则底为八进制，若前缀为0x或0X，则底为十六进制，否则底为十进制。

  atoi(const char *p)
  * 参数为字符串指针，若是string，需要这样使用：aoti(string.c_str())

• 一行输入

  getline(cin, str)
  将一行输入保存在str中
  扩展：
  getline(cin, str, ch)
  将输入按照ch进行分隔，保存在str中

• 翻转

  reverse(container.begin(), container.end())
  * 翻转[first, last)范围中的元素顺序

• 最大值和最小值

  INT_MAX和INT_MIN
  * 需要包含头文件include <climits>

• 判断是否为字母字符
  isalpha(c)

  • 判断字符c是否为字母，包括大写字母和小写字母
  • isdigit(c)判断字符c是否为数字

• 读取字符

  cin.get()
cin>>会忽略掉所有的前导白色空格，所以使用cin>>就不可能仅输入一个空格或回车符。
  cin对象中的get()成员函数可以读取单个字符，包括任何白色空格字符。
  * 如果程序需要存储正在读取的字符，则可以通过以下任意一种方式调用get()成员函数。

  ```
  cin.get(ch);
  或
  ch = cin.get();
  ```
  

  • 如果程序正在使用get()成员函数简单地暂停屏幕直到按回车键，并且不需要存储字符，则该函数也可以这样调用：
    cin.get();

• 字符串流输入

  stringstream input(str)
  * 需要包含头文件#include <sstream>，input是一个stringstream对象，用str初始化，所以可以将str原样输入。
  * input可以实现基于字符串的流上的输入与输出操作。
  * cout << input.str()可以将input的内容输出到屏幕上
  * input.str("")或input.clear()可以将input清空

• 开根号

  sqrt(x)
  * 需要包含头文件#include <cmath>

• STL容器

  容器分为顺序容器和关联容器。

  vector
  函数：push_back()、pop_back()、size()、clear()、insert()、erase()、front()、back()、at()、empty()、resize()、emplace()、emplace_back()、operator[]()、operator=()、capacity()、reserve()
  两种访问方式：下标访问[]和通过迭代器访问*(it + i)，除了vector和string之外的容器都不支持*(it + i)的访问方式，这和线性有关。
  * 面对两维的数组，低维是高维的地址。

  deque
  * 函数：push_back(), push_front(), pop_back(), pop_front(), insert(), emplace(), emplace_back(), emplace_front(), clear(), empty(), erase(), size(), resize(), at(), operator[](), back(), front(), begin(), end()

  list
  * 函数：back(), front(), size(), empty(), resize(), push_back(), push_front(), pop_back(), pop_front(), emplace(), emplace_back(), emplace_front(), reverse(), sort(), unique()

  set
  * 函数：insert(), size(), find(), erase(), empty(), clear(), emplace(), count(), lower_bound()-返回指向大于（或等于）某值的第一个元素的迭代器, upper_bound()-返回大于某个值元素的迭代器, equal_range()-返回集合中与给定值相等的上下限的两个迭代器

  stack
  * 函数：empty(), size(), top(), push(), pop(), emplace()

  queue
  * 函数：empty(), size(), front(), back(), push(), pop(), emplace()

  priority_queue
  函数：push(), pop(), top(), size(), empty(), emplace()
  C++默认的优先队列是大根堆,小根堆的实现方法：priority_queue<int, vector<int>, greater<int>>

  map
  * 函数：empty(), size(), operator[], at, insert(), erase(), clear(), emplace(), find(), count(), lower_bound(), upper_bound(), equal_range(), begin(), end()

• ++i和i++的区别

  • ++i为前置运算符，i++为后置运算符。
    ```
    CDemo CDemo::operator()
    {
    // 前置
    ++n;
    return *this;
    }

  CDemo CDemo::operator (int k)
  {
  // 后置
  CDemo tmp(*this); // 记录修改前的对象
  n;
  return tmp; // 返回修改前的对象
  }
  `` * 后置要多生成一个局部对象tmp，因此执行速度比前置的慢。因此，对循环控制变量i，要养成写i，不写i`的习惯。

• 迭代器的一些知识

  • 要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。

  • 迭代器按照定义方式可以分为以下四种：正向迭代器、反向迭代器、常量正向迭代器、常量反向迭代器。
    > 正向迭代器：容器类名::iterator 迭代器名;
    >
    > 相对应地，begin()和end()

    反向迭代器：容器类名::reverse_iterator 迭代器名;

    相对应地，rbegin()和rend()

  • 注意，容器适配器stack、queue和priority_queue没有迭代器。容器适配器有一些成员函数，可以用来对元素进行访问。

  • 迭代器的功能分类
    > 正向迭代器。假设p是一个正向迭代器，则p支持以下操作：++p, p++, *p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。

    双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若p是一个双向迭代器，则--p和p--都是有定义的。--p使得p朝和++p相反的方向移动。

    随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若p是一个随机访问迭代器，i是一个整型变量或常量，则p还支持以下操作：p+=i, p-=i, p+i, p-i, p[i]。此外，两个随机访问迭代器p1, p2还可以用<, >, <=, >=运算符进行比较。p1<p2的含义是：p1经过若干次（至少一次）++操作后，就会等于p2。其他比较方式的含义与此类似。表达式p2 - p1也是有定义的，其返回值是p2所指向元素和p1所指向元素的序号之差（也可以说是p2和p1之间的元素个数减一）。

    容器	迭代器功能
    vector	随机访问
    deque	随机访问
    list	双向
    set/multiset	双向
    map/multimap	双向
    unordered_map/unordered_multimap	前向迭代器
    unordered_set/unordered_multiset	前向迭代器
    stack	不支持迭代器
    queue	不支持迭代器
    priority_queue	不支持迭代器

  • 在C++中，数组也是容器。数组的迭代器就是指针，而且是随机访问迭代器。例如，对于数组int a[10], int *类型的指针就是其迭代器，则a, a+1, a+2都是a的迭代器。

• 值传递、指针传递和引用传递

  在C语言中只存在值传递一种方式，包括值传递和指针传递。

  普通的值传递意味着将实参的值拷贝给函数的形参，对于形参的修改不能影响到实参；指针传递则是将实参的地址传递给函数的形参（指针），函数新建一个局部指针变量指向实参的内存地址，对*p的操作将影响到实参的值，但是对p的操作则不会影响到实参的地址和实参的内容，究其本质，就是指针传递也属于值传递方式。

  引用传递

  引用传递是给实参在局部变量中起了一个别名，实参和形参绑定为同一对象，所以对形参的操作就是对实参的操作。

  函数参数传递方式	其他称呼	实参	形参	本质
  值传递	传值	普通变量	普通变量	普通变量传递数值
  指针传递、地址传递	传地址（传址）	引用变量	指针变量	指针变量传递地址
  引用传递	传引用	普通变量	引用变量	普通变量传递引用

  这里谈论指针传递和引用传递的区别，根本区别：指针传递中形参和实参指向同一对象，引用传递中形参和实参是同一对象。

  从概念上讲，指针从本质上讲就是存放变量地址的一个变量，在逻辑上是独立的，它可以被改变，包括其所存放的地址的改变（改变指向）和其指向的地址中所存放的数据的改变（改变指向变量的值）。

  而引用是一个别名，它在逻辑上是不独立的，它的存在具有依附性，所以引用必须在一开始就被初始化，而且其引用的对象在其整个生命周期中是不能被改变的（自始至终只能依附于同一个变量）。

  在C++中，指针和引用经常用于函数的参数传递，然而，指针传递参数和引用传递参数是有本质上的不同的：

  • 指针传递参数本质上是值传递的方式，它所传递的是一个地址值。值传递过程中，被调函数的形式参数作为被调函数的局部变量处理，即在栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成为了实参的一个副本。值传递的特点是被调函数对形式参数的任何操作都是作为局部变量进行，不会影响主调函数的实参变量的值。（这里是在说实参指针本身的地址值不会变）
  • 而在引用传递过程中，被调函数的形式参数虽然也作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中存放的地址访问主调函数中的实参变量。正因为如此，被调函数对形参的任何操作都影响了主调函数中的实参变量。

  最后，总结一下指针和引用的相同点和不同点：
  相同点：
  * 都是地址的概念。指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名。
  不同点
  * 指针是一个实体，而引用仅是个别名；
  * 引用只能在定义时被初始化一次，之后不可变；指针可变。引用“从一而终”，指针可以“见异思迁”。
  * 引用不能为空，指针可以为空。
  * sizeof 引用得到的是所指向变量（对象）的大小，而sizeof 指针得到的是指针本身的大小。
  * 指针和引用的自增(++)运算意义不一样。
  * 引用是类型安全的，而指针不是（引用比指针多了类型检查）。

• 字符数组的长度

  strlen(char*)
  * 传入参数为字符数组名，字符数组以\0结尾，返回该字符数组的长度（不包括\0）

  扩展：\
  在C中，有两种类型的字符串表示形式：C-风格字符串 和 **C引入的string类
  C-风格字符串**:C风格的字符串起源于C语言，并在C++中继续得到支持。字符串实际上是使用NULL字符\0终止的一维字符数组。因此，一个以NULL结尾的字符串，包含了组成字符串的字符。在C语言中，字符串有两种存储方式，一种是通过字符数组存储，另一种是通过字符指针存储。

  字符数组的初始化方式：
  char a[6] = {'H', 'e', 'l', 'l', 'o', '\0'};(其中，数组的维度可以省略，编译器会自动计算；结尾的’\0’不能省略，这是判断字符数组是否结束的标志)
  char a[6] = "Hello";(其中，Hello是字符串常量，编译器在用字符串常量初始化字符数组时，会自动把’\0’放在字符串的末尾。)

  字符指针的初始化方式：
  * char *a = "Hello; // 指针直接往上戳

  一个字符串常量为什么会给一个指针赋值？字符串常量是一个表达式，既然是表达式就会有值，字符串常量的值就是该字符串第一个字母的首地址。同一个字符串常量，它们的值（地址）相同。字符串常量和字符数组不同，无法通过下标（指针间接引用）来直接修改。如果要修改字符串的值，我们只能使用字符数组的形式来存储字符串，可以这样声明：char str[] = "Hello";，这样就可以修改了，它两本质上的不同是存储的位置不同。

  实际上,char *a = "Hello";的写法是不规范的。因为a指向了字符串常量，不可以通过a修改字符串常量，即a是指向静态字符的指针，按照“类型相同赋值”的原则来写代码：const char *a = "Hello";

  字符常量、字符串常量
  字符常量是用单引号括起来的一个字符，如a、A，实质是一个整型值。
  字符变量的类型说明符为char，字符变量定义格式为：char a;。字符变量用来存储字符常量，字符值是以ASCII码的二进制形式存放在变量的内存单元之中的。字符型与整形可以进行算数运算。
  字符串常量是用双引号括起来的一个或多个字符，如"Hello"。
  字符串常量有两种定义方式：（字符数组）数组方式定义字符串：当数组名用于表达式时，它们的值也是个指针常量，我们可以对它们进行下标引用、间接访问以及指针运算。（字符串指针）：指针常量定义字符串：当一个字符串常量出现在表达式中时，它的值是个指针常量，编译器把这些指定字符的一份拷贝存储在内存的某个位置，并存储一个指向第一个字符的指针，其中一个是指针的地址，一个是字符串的地址。

  C++中有大量的函数用来操作以NULL结尾的字符串：
  | 函数 | 功能 |
  | :—: | :—: |
  | strcpy(s1, s2) | 复制字符串s2到字符串s1 |
  | strcat(s1, s2) | 连接字符串s2到字符串s1的末尾 |
  | strlen(s1) | 返回字符串s1的长度 |
  | strcmp(s1, s2) | 返回s1与s2的比较结果 |
  | strchr(s1, ch) | 返回一个指针，指向字符串s1中字符ch第一次出现的位置 |
  | strstr(s1, s2) | 返回一个指针，指向字符串s1中s2第一次出现的位置 |
  | | |

  C中的string类**: C标准库提供了string类类型，支持上述所有的操作，另外还增加了其他更多的功能，比如：
  | 函数 | 功能 |
  | :—: | :—: |
  | str.push_back() | 将一个字符插入到str尾部 |
  | str.append(s)/append(n, c) | 将一个双引号字符串s/n个c追加到str尾部 |
  | str.insert(pos, args) | 在pos之前插入args |
  | str.front()/str.back() | 返回字符串str的首个/最后一个元素（char类型）的引用 |
  | str.erase() | 删除 |
  | str.clear() | 删除 |
  | str.empty() | 判断str是否为空 |
  | str.size()/str.length() | 返回str的长度 |
  | str.find(args)/str.rfind(args) | 查找str中args出现的第一次位置/最后一次位置 |
  | str.find_first_of(args) | 在str中查找args中任何一个字符最早出现的位置 |
  | to_string(val) | 将数值val转换为string并返回，val可以是任何算数类型 |
  | stoi(str)/atoi(ch) | 字符串str/字符ch 转换为整数并返回 |
  | str.substr(pos, n) | 从索引pos开始，提取连续的n个字符，包括pos位置的字符 |
  | reverse(str.begin(), str.end()) | 反转str |
  | | |
  * 和C-风格字符串不同，string的结尾没有结束标志\0
  * 转换为C-风格字符串：有时候必须要使用C-风格字符串（例如打开文件时的路径），为此，string类提供了一个转换函数c_str()（使用方法：string.c_str()），该函数能够将string字符串转换为C-风格字符串，并返回该字符串的const**指针（const char*）。

  sizeof

  • sizeof是一个操作符，sizeof后如果是类型必须加括弧，如果是变量名可以不加括弧。
  • sizeof返回的是变量声明后所占的内存数，不是实际长度。
  • 数组做sizeof的参数不退化，传递给strlen就退化为指针了。
  • 大部分编译器在编译的时候就把sizeof计算过了，这就是sizeof(x)可以用来定义数组维数的原因。
  • sizeof一个引用得到的结果是sizeof一个被引用的对象的大小。

• 原码、反码和补码

  • 第一位代表正负，0表示正数，1表示负数。
  • 正数的原码、反码和补码相同。
  • 负数的反码是保持符号位不变，其余为取反；负数的补码是反码 +1 。
  • 也可以这样计算一个负数的补码：比如 1+（-1）=0，那么，（-1）= 0 - 1，0的补码为 [0000 0000]补， 1的补码为 [0000 0001]，0的补码不够用，补一位 [1 0000 0000]补，那么 0 - 1 = [1 0000 0000]补 - [0000 0001]补 = [1111 1111]补。

• 判断字符类型：大/小写字母、标点、数字等

  #include <cctype>中含有对string中字符操作的库函数，如下：
  isalnum(c) // 当是字母或数字时为真 isalpha(c) // 当是字母时为真 isdigit(c) // 当是数字时为真 islower(c) // 当是小写字母时为真 isupper(c) // 当是大写字母时为真 isspace(c) // 当是空白（空格、回车、换行、制表符等）时为真 isxdigit(c) // 当是十六进制数字时为真 ispunct(c) // 当是标点符号时为真（即c不是控制字符、数字、字母、 // 可打印空白中的一种） isprint(c) // 当是可打印字符时为真（即c是空格或具有可见形式） isgraph(c) // 当不是空格但可打印时为真 iscntrl(c) // 当是控制字符时为真 tolower(c) // 若c是大写字母，转换为小写输出，否则原样输出 toupper(c) // 类似上面的

• EOF

  • EOF是“end of file”的缩写，表示文字流的结尾，这里的文字流可以是文件（file），也可以是输入流（stdin）。
  • EOF不是特殊字符，而是一个定义在stdin.h的常量，一般等于 -1。
  • while(scanf("%d", &n), n) \
    功能：当输入为n且n!=0时继续循环，当n为0时结束循环。
  • while(scanf("%d", &n)!=EOF)和while(~scanf("%d", &n)) \
    功能：当读到文件结尾时终止循环，因为EOF为 -1，取反后为 0。

• bitset

  bitset需要引入头文件#include <bitset>
bitset的初始化：bitset<n> bitvec(num)
bitset的一些操作: bitvec.count()可以返回1的个数、bitvec.set()将所有位置位，即变为1、bitvec.reset()将所有位复位，即变为0。

• lambda表达式

  • lambda表达式的构成：[capature list](parameter list) -> return type {function body;}，其中，参数列表和返回类型可以省略。
  • 捕获列表有两种捕获方式：显式捕获，如[c]、[&c]；隐式捕获，如值捕获[=]和引用捕获[&]。

• lowbit

  lowbit可以查找一个正整数的二进制表示中最低位的1及其后面的0所对应的值。比如，5可以表示为0101，所以lowbit(5) = 1；10可以表示为1010，所以lowbit(10) = 2。lowbit实现语句如下：
  int lowbit(int x) { return x & (-x); }
  证明：假设n>0，设n的二进制表示中，第k位为1，第0至第k-1位都为0。那么，对n按位取反后 ~n 的二进制表示中，第k位为0，第0至第k-1位都为1，然后对 ~n 加1，则得到 ~n+1 的第0位至第k-1位都为0，第k位为1，第k+1位至最高位与n相反，此时执行n & (~n+1)将得到第k位的1以及其后面的0。而 -n = ~n + 1 。

• sort() 自定义排序规则
  > sort()中可以传入自定义的排序规则，实现方式包括：
  > * 函数对象
  > * 重载小于号运算符
  > * 定义一个接受2个参数并返回bool类型值的函数

  • 函数对象
    ```
    // 定义函数对象类
    class cmp { // 调用方式：sort(vec.begin(), vec.end(), cmp());注意括号
    public:
    // 重载()运算符
    bool operator() (const string & a, const string & b)
    {
    // 按照字符串的长度，做升序排序（即存储的字符串从短到长）
    return a.size() < b.size();
    }
    };

  // 值得一提的是，在定义函数对象类时，也可以将其定义为模板类。比如：
  // 定义函数对象模板类
  template [HTML_REMOVED] // typename也可以使用class代替
  class cmp { // 调用方式：sort(vec.begin(), vec.end(), cmp[HTML_REMOVED]());
  public:
  // 重载()运算符
  bool operator() (const T & a, const T & b)
  {
  // 按照值的大小，做升序排序
  // 注意，此方式必须保证T类型元素可以直接使用关系运算符
  // （比如这里的<运算符）做比较
  return a < b;
  }
  };
  * 重载小于号运算符
  // 重载小于号运算符的实现方法分类：全局函数、成员函数、友元函数。其中，当以成员函数的方式重载<运算符时，该成员函数必须声明为const类型，且参数也必须为const类型。参数需要是自定义结构，比如结构体或类都可以，但是pair就不可以。

  // 全局函数
  // 重载<运算符，参数都必须为const类型
  bool operator< (const myClass & a, const myClass & b)
  {
  // 以字符的长度为标准比较大小
  return a.getStr().size() < b.getStr().size();
  }

  // 成员函数
  // 当以成员函数的方式重载<运算符时，该成员函数必须声明为const类型，
  // 且参数也必须为const类型
  bool operator< (const myClass & b) const
  {
  // 以字符的长度为标准比较大小
  return this->getStr().size() < b.getStr().size();
  }

  // 友元函数
  // 以友元函数的方式重载<运算符时，要求参数必须使用const修饰
  // 类中友元函数的声明
  friend bool operator< (const myClass & a, const myClass & b);
  // 类外部友元函数的具体实现
  bool operator< (const myClass & a, const myClass & b)
  {
  // 以字符串的长度为标准比较大小
  return a.getStr().size() < b.getStr().size();
  }
  ```

  • 函数指针
    // 传入的参数类型和需要排序的数据类型一致 // 如果第一个参数需要排在第二个参数前面时，返回true；反之返回false。 // 简单来说就是，a对应第一个参数，b对应第二个参数。 // 比较a和b，如果是想升序，那么就定义当a<b的时候返回true; // 如果是想降序，那么就定义当a>b的时候返回true; bool cmp (int a, int b) // 调用方式：sort(vec.begin(), vec.end(), cmp); { return a < b; }

• scanf()

  • scanf()函数是scan format的缩写，意思是输入格式化。
  • 在使用scanf()时，尽量只输入控制字符，而不输入其他非控制字符；如果输入非控制字符，需要在输入时原样输入才可以。比如用逗号分隔，在输入时也需要用逗号分隔。
  • 在很多情况下都需要输入字符或字符串，在使用scanf()输入单个字符char时经常会读入空格、换行等而出现一些问题，
    • 推荐使用字符串数组的方式读入int op[2]; scanf("%s", op);
    • 或者使用特殊的读入方法，比如char op, str[N]; scanf(" %c%s", &op, str);可以忽略0~n个空格、换行符、tab等
    • 或者在读入前清空缓冲区scanf("%*[^\n]");scanf("%*c");

• 负数取模

  int t = (x % N + N) % N
  * 负数取模为负数，这样做可以将负数变为正数，同时不改变正数的取模结果

• memset()

  int h[N]; memset(h, -1, sizeof h);
  需要包含头文件#include <cstring>
memset()的作用是将数字以 单个字节逐个拷贝 的方式放到指定的内存中去
  memset()的正规用法是只能用来初始化char类型的数组的，也就是说，它只接受0x00-0xFF的赋值。因为char是1字节，memset()是按照字节赋值的，相当于把每个字节都设为那个数，所以char类型的数组可赋任意值
  而对于常用的int类型，int类型的变量一般占4个字节，对于memset(h, i, sizeof h);1转为二进制00000001，当作一字节，一字节8位，int为4字节，所以初始化完每个数为“00000001 00000001 00000001 00000001”（即十进制的16843009），memset(h, 0, sizeof h);，对每一个字节赋值0的话就变成了“00000000 00000000 00000000 00000000”（即十进制中的0），memset(h, -1, sizeof h);对每一个字节赋值-1的话就变成了“11111111 11111111 11111111 11111111”（即十进制中的-1），所以memset()可以直接初始化0和-1
  * 如果想初始最大化，第一位为符号位，不能为1，剩下全是1，也就是7个1，01111111化为十六进制刚好为0x7f，所以memset(h, 0x7f, sizeof h);就可以了，但是在通常的场合下，最精巧的无穷大常量取值是0x3f3f3f3f，所以需要memset(h, 0x3f, sizeof h);

• switch语法

  switch (condition) { case condition_1 : ...; break; case condition_2 : ...; break; case condition_3 : ...; break; [default] : ...; break; // 有无 default 都可以 }

  扩展：

  • case后的语句执行是执行一个段落，所以可以不用加花括号{}，但是要加上break，否则会执行下一个case语句
  • continue和break之前必须是以分号;结尾的完整语句。