变量与基础运算

字节 B = Byte,位 b = bit,1 Byte = 8 bit,8 Mb = 1 MB

• bool 布尔 true/false 1byte
• char 字符 1byte
  • 一个字符用单引号 char 'a',' ','\n';
• int 整型 4byte
  • -2^31~2^31-1
  • -2147483648 ~ 2147483647
• float 单精度浮点数 4byte
  • 有效数字位数 6-7位
  • 科学计数法 1.235*10^2 = 1.235e2
• double 双精度浮点数 8byte
  • 有效数字位数 15-16位
• long long ll整型 8byte
  • -2^63~2^63-1
• long double
  • 有效数字位数 18-19位
• 变量声明
  • int a, b = 2, c = b;
  • float d = 1.5, f = 1.235e2;
  • char j = 'a',k = 'b';
  • long long 类型的常量 long long l = 10000000000ll; 赋值的时候，如果大于2^31-1，那么后面需要加上ll/LL
• stdio format int: %d,float: %f,double: %lf,char: %c,long long: %lld
• % 去除数的余数 与数学中去模区别在 其因前面数字存在负数，结果变为负数。
• 后置++是先运行本条语句，再++；前置++是先++，再运行本条语句

int a = 6; int b = a++; cout << a << " " << b << endl; // 7 6 int c = 6; int d = ++c; ccout MM c MM " " << d << endl; // 7 7

• 变量强制转换
  • float/double -> int 下去整
  • char <-> int ascii
• 隐性运算关系
  • int 与 float 运算 结果为 float/double
  • char 与 int 运算 结果为 int
  • int 与 ll 运算 结果为 ll
  • float 与 double 结果为 double

CPP STL 标准模板库

https://oi.wiki/lang/csl/

板子

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue, greater> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
      
    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

STL 容器

迭代器 Iterator

• 迭代器本身可以看作一个数据指针

vector<int> v0;
vector<int>::iterator it = v0.begin();
vector<int>::iterator it2 = v0.end();
// 左闭右开的结构 [begin,end) end是最后一个元素的index+1

cout << *it << endl; // index 0
cout << *(it2-1) << endl; // index 1
    
// c++ 11 可以用 auto
auto it3 = v0.begin();

// 循环
for (int i = 0; i < v0.size(); ++i) {
    cout << v0[i] << " ";
}
for (auto i = v0.begin(); i != v0.end(); ++i) {
    cout << *i << " ";
}

序列式容器

Vector 向量 -

动态数组结构 类似于顺序线性表

vector<int> v0;
vector<int> v1[233]; // 第一维度长233静态长度，第二位长度动态变化

// 结构体初始化
struct Rec{
    int x,y;
};
vector<Rec> v2;

v0.size(); // 实际长度 O(1)
v0.empty(); // 是否为空 bool O(1)
v0.clear(); // 清空

vector<int> v1({1,2,3,4,5,6,7,9,10});
v1.front() // 首个元素 1 相当于 v1.begin()
v1.back(); // 结尾的元素 10 位于 v1.end() 之前 

v1.push_back(11); // 再最后加一个元素 O(1)
v1.pop_back(); // 删除最后一个元素 O(1)

deque 双端队列, list 链表

关联式容器

set 集合

• 不含有重复元素
• 重复元素可以用 multiset #### map 集合

map<Key, T> yourMap;

// 遍历
for (auto item : yourMap) cout << item << endl;

容器适配器: 栈与队列

• 栈/堆栈/Stack std::stack

是一种遵循 先入后出 逻辑的线性数据结构。 仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

int main() {
    // std::stack<TypeName> s;  // 使用默认底层容器 deque，数据类型为 TypeName
    // std::stack<TypeName, Container> s;  // 使用 Container 作为底层容器
    // std::stack<TypeName> s2(s1);        // 将 s1 复制一份用于构造 s2
    
    stack<int> stack; // 初始化
    cout << stack.empty() << endl; // 询问容器是否为空 1

    for (int i = 1; i <= 100; ++i) {
        stack.push(i); // 向栈中插入元素 i
    }

    cout << stack.top() << endl; // 访问栈顶元素 100 （如果栈为空，此处会出错）
    cout << stack.size() << endl; // 查询容器中的元素数量 100

    stack.pop(); // 删除栈顶元素
    cout << stack.top() << endl; // 99

    cout << stack.size() << endl; // 查询容器中的元素数量 99

    cout << stack.empty() << endl; // 询问容器是否为空 0
    return 0;
}

• 队列 Queue 是一种遵循先入先出规则的线性数据结构。 顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

int main() {
//    std::queue<TypeName> q;  // 使用默认底层容器 deque，数据类型为 TypeName
//    std::queue<TypeName, Container> q;  // 使用 Container 作为底层容器
//    std::queue<TypeName> q2(q1);  // 将 s1 复制一份用于构造 q2   
    
    queue<int> queue;
    cout << queue.empty() << endl; // true

    for (int i = 1; i <= 100 ; ++i) {
        queue.push(i);
    }

    cout << queue.front() << endl; // 1
    queue.pop(); // 出队

    cout << queue.front() << endl; // 2
    cout << queue.size() << endl; // 99

    cout << queue.empty() << endl; // false
    return 0;
}

STL 算法库

<algorithm>