AcWing语法基础课学习笔记第八讲 STL、位运算、常用库函数

向右看齐 2024-03-16 10:20 34阅读 0赞

### AcWing语法基础课学习笔记 ###

#### 文章目录 ####

*   *  AcWing语法基础课学习笔记
     *   *   *  第八讲 STL、位运算、常用库函数
             *   *  1. \#include \`\`
                 *   *  1.1 声明
                     *  1.2 \`size\`/\`empty\`
                     *  1.3 \`clear\`
                     *  1.4 迭代器
                     *  1.5 \`begin\`/\`end\`
                     *  1.6 \`front\`/\`back\`
                     *  1.7 \`push\_back()\`和\`pop\_back()\`
                 *  2. \#include \`\`
                 *   *  2.1 声明
                     *  2.2 循环队列\`queue\`
                     *  2.3 优先队列\`priority\_queue\`
                 *  3. \#include \`\`
                 *  4. \#include \`\`
                 *  5. \#include \`\`
                 *   *  5.1 声明
                     *  5.2 \`size\`/\`empty\`/\`clear\`
                     *  5.3 迭代器
                     *  5.4 \`begin\`/\`end\`
                     *  5.5 \`insert\`
                     *  5.6 \`find\`
                     *  5.7 \`lower\_bound\`/\`upper\_bound\`
                     *  5.8 \`erase\`
                     *  5.9 \`count\`
                 *  6. \#include \`\`
                 *   *  6.1 声明
                     *  6.2 \`size\`/\`empty\`/\`clear\`/\`begin\`/\`end\`
                     *  6.3 \`insert\`/\`erase\`
                     *  6.4 \`find\`
                     *  6.5 \`\[\]\`操作符
                 *  7. 位运算
                 *  8. 常用库函数
                 *   *  8.1 \`reverse\`翻转
                     *  8.2 \`unique\`去重
                     *  8.3 \`random\_shuffle\`随机打乱
                     *  8.4 \`sort\` 排序
                     *  8.5 \`lower\_bound\`/\`upper\_bound\` 二分

![在这里插入图片描述][39675a8f65bb4523a1b9872cee28421a.png_pic_center]

##### 第八讲 STL、位运算、常用库函数 #####

> STL

STL是提高C++编写效率的一个利器。—— 闫学灿

###### 1. \#include `<vector>` ######

`vector`是变长数组，支持随机访问，不支持在任意位置 O(1) 插入。为了保证效率，元素的增删一般应该在末尾进行。

###### 1.1 声明 ######

#include <vector>   // 头文件
    vector<int> a;      // 相当于一个长度动态变化的int数组
    vector<int> b[233]; // 相当于第一维长233，第二位长度动态变化的int数组
    struct rec{…};
    vector<rec> c;      // 自定义的结构体类型也可以保存在vector中

###### 1.2 `size`/`empty` ######

`size`函数返回`vector`的实际长度（包含的元素个数），`empty`函数返回一个`bool`类型，表明`vector`是否为空。二者的时间复杂度都是 `O(1)`。

> !!! 所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。

###### 1.3 `clear` ######

`clear`函数把`vector`清空。

###### 1.4 迭代器 ######

迭代器就像STL容器的“指针”，可以用星号`*`操作符解除引用。

一个保存int的vector的迭代器声明方法为：

vector<int> a;
    
    vector<int>::iterator it = a.begin();

`vector`的迭代器是“随机访问迭代器”，可以把`vector`的迭代器与一个整数相加减，其行为和指针的移动类似。

可以把`vector`的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

###### 1.5 `begin`/`end` ######

`begin`函数返回指向`vector`中第一个元素的迭代器。

例如`a`是一个非空的`vector`，则`*a.begin()`与`a[0]`的作用相同。

所有的容器都可以视作一个“前闭后开”的结构，`end`函数返回`vector`的尾部，即第n 个元素再往后的“边界”。`*a.end()`与`a[n]`都是越界访问【`*--a.end()` 才是"最后一个元素"】，其中`n = a.size()`。

下面两份代码都遍历了`vector<int> a`，并输出它的所有元素。

for (int i = 0; i < a.size(); i ++)
        cout << a[i] << endl;
    
    for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
        cout << *it << endl;

![在这里插入图片描述][7d531b770bf343a29bc91e8f57e2a065.png_pic_center]

> 当然其实那一长串可以换成`auto`
> 
> ![在这里插入图片描述][31ae2d8a933941c0ae0464fe7b6c9b16.png_pic_center]

> 其实迭代器用的不多

###### 1.6 `front`/`back` ######

`front`函数返回`vector`的第一个元素，等价于`*a.begin()`和`a[0]`。

`back`函数返回`vector`的最后一个元素，等价于`*--a.end()`和`a[a.size() – 1]`。

###### 1.7 `push_back()`和`pop_back()` ######

`a.push_back(x)`把元素x插入到`vector a`的尾部。  
`b.pop_back()`删除`vector a`的最后一个元素。

> 【扩展】
> 
> `vector` 的扩容是倍增的，10、20、40…

###### 2. \#include `<queue>` ######

头文件`queue`主要包括`循环队列queue`和`优先队列priority_queue`两个容器。

###### 2.1 声明 ######

queue<int> q;
    struct rec{…}; 
    queue<rec> q;                        //结构体rec中必须定义小于号【优先队列】
    
    priority_queue<int> q;                              // 大根堆
    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
    priority_queue<pair<int, int>> q;

> 重载运算符
> 
>     struct Rec
>     {
>         int a, b;
>         bool operator< (const Rec& t) const
>         {
>             return a < t.a;
>         }
>     }
>     
>     priority_queue<Rec> d; // 大根堆重载小于号
> 
> 小根堆重载大于号
> 
>     struct Rec
>     {
>         int a, b;
>         bool operator> (const Rec& t) const
>         {
>             return a > t.a;
>         }
>     }
>     
>     priority_queue<int, vector<int>, greater<int>> q; // 小根堆重载大于号

###### 2.2 循环队列`queue` ######

push    // 从队尾插入
    pop     // 从队头弹出
    front   // 返回队头元素
    back    // 返回队尾元素

###### 2.3 优先队列`priority_queue` ######

push    // 把元素插入堆
    pop     // 删除堆顶元素
    top     // 查询堆顶元素（最大值）

> 循环队列、优先队列、栈… 都没有`clear` 函数，除了这仨，其他STL 容器都有
> 
> 把队列重新初始化，就可以清空一个队列了

###### 3. \#include `<stack>` ######

头文件`stack`包含栈。声明和前面的容器类似。

push    // 向栈顶插入
    pop     // 弹出栈顶元素

###### 4. \#include `<deque>` ######

双端队列`deque`是一个支持在两端高效插入或删除元素的**连续线性存储空间**。

它就像是`vector`和`queue`的结合。

*  与`vector`相比，`deque`在头部增删元素仅需要 `O(1)` 的时间；
 *  与`queue`相比，`deque`像数组一样支持随机访问。

[]              // 随机访问
    begin/end       // 返回deque的头/尾迭代器
    front/back      // 队头/队尾元素
    push_back       // 从队尾入队
    push_front      // 从队头入队
    pop_back        // 从队尾出队
    pop_front       // 从队头出队
    clear           // 清空队列

###### 5. \#include `<set>` ######

头文件`set`主要包括`set`和`multiset`两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。【都是有序的】

`set`和`multiset`的内部实现是一棵红黑树，它们支持的函数基本相同。

###### 5.1 声明 ######

set<int> s;
    struct rec{…}; 
    set<rec> s;  // 结构体rec中必须定义小于号【重载】
    multiset<double> s;

###### 5.2 `size`/`empty`/`clear` ######

与`vector`类似

###### 5.3 迭代器 ######

`set`和`multiset`的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号`*`解除引用，仅支持`++`和`--`两个与算术相关的操作。

设`it`是一个迭代器，例如`set<int>::iterator it;`

若把`it ++`，则`it`会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把`it --`，则`it`将会指向排在“上一个”的元素。

###### 5.4 `begin`/`end` ######

返回集合的首、尾迭代器，时间复杂度均为 `O(1)`

`s.begin()`是指向集合中最小元素的迭代器。

`s.end()`是指向集合中最大元素的下一个位置的迭代器【访问就越界】。换言之，就像`vector`一样，是一个“前闭后开”的形式。因此`-- s.end()`是指向集合中最大元素的迭代器。

###### 5.5 `insert` ######

`s.insert(x)`把一个元素`x`插入到集合`s`中，时间复杂度为 `O(logn)`。

在`set`中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

###### 5.6 `find` ######

`s.find(x)`在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回`s.end()`。时间复杂度为 `O(logn)`。

###### 5.7 `lower_bound`/`upper_bound` ######

这两个函数的用法与`find`类似，但查找的条件略有不同，时间复杂度为 `O(logn)`。

*  `s.lower_bound(x)`查找大于等于`x`的元素中最小的一个，并返回指向该元素的迭代器。
 *  `s.upper_bound(x)`查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

###### 5.8 `erase` ######

设it是一个迭代器，`s.erase(it)`从`s`中删除迭代器`it`指向的元素，时间复杂度为 `O(logn)`。

设`x`是一个元素，`s.erase(x)`从`s`中删除所有等于`x`的元素，时间复杂度为 `O(k+logn)`，其中 `k` 是被删除的元素个数。

###### 5.9 `count` ######

`s.count(x)`返回集合`s`中等于`x`的元素个数，时间复杂度为 `O(k+logn)`，其中 `k` 为元素`x`的个数。

###### 6. \#include `<map>` ######

`map`容器是一个键值对`key-value`的映射，其内部实现是一棵以`key`为关键码的红黑树。

`Map`的`key`和`value`可以是任意类型，其中`key`必须定义小于号运算符。

###### 6.1 声明 ######

map<key_type, value_type> name;
    
    //例如：
    map<long long, bool> vis;
    map<string, int> hash;
    map<pair<int, int>, vector<int>> test;

###### 6.2 `size`/`empty`/`clear`/`begin`/`end` ######

均与`set`类似。

###### 6.3 `insert`/`erase` ######

与`set`类似，但其参数均是`pair<key_type, value_type>`。

###### 6.4 `find` ######

`h.find(x)`在变量名为`h`的`map`中查找`key`为`x`的二元组。

###### 6.5 `[]`操作符 ######

`h[key]`返回`key`映射的`value`的引用，时间复杂度为 `O(logn)`。

`[]`操作符是`map`最吸引人的地方。我们可以很方便地通过`h[key]`来得到`key`对应的`value`，还可以对`h[key]`进行赋值操作，改变`key`对应的`value`。

> 【补充】讲义中没提到的
> 
>     #include <unordered_set> // 无序set，哈希表，它和set 的区别就是 `lower_bound`/`upper_bound` 两个函数，而且操作时间复杂度是O(1)的
>     
>     int main()
>     {
>         unordered_set<int> s;  // 不能存储重复元素
>         unordered_multiset<int> k; // 可以存储重复元素
>     }
> 
>     #include <unordered_map>
>     
>     int main()
>     {
>         unordered_map<int, int> c; // 哈希表, O(1), 不支持二分
>         unordered_multimap<int, int> c;
>     }
> 
>     #include <bitset>
>     
>     int main()
>     {
>         bitset<1000> a; //长度为1000的二进制串(01串)
>         
>         a.count(); // 返回1的个数
>         a.set(3); //第3位置1
>         a.reset(3); //第3位置0
>     }
> 
>     int main()
>     {
>         // 二元组pair
>         pair<int, string> a;
>         a = {3, "dingjiaxiong"};
>         
>         a = make_pair(4, "abc"); // c++
>         
>         // pair 支持比较运算，双关键字
>     }

> 位运算和常用库函数

C++帮我们实现好了很多有用的函数，我们要避免重复造轮子。 —— 闫学灿

###### 7. 位运算 ######

![在这里插入图片描述][378907c0a6fe438a806b3a66de95be75.png_pic_center]

常用操作：

1.  求`x`的第`k`位数字 `x >> k & 1`
2.  `lowbit(x) = x & -x`，返回`x`的最后一位`1`

###### 8. 常用库函数 ######

> 在`<algorithm>` 中

###### 8.1 `reverse`翻转 ######

翻转一个`vector`：

reverse(a.begin(), a.end());

翻转一个数组，元素存放在下标`1 ~ n`：

reverse(a + 1, a + n + 1);
    
    // reverse(a, a + n); 下标从0 开始

> `O(n )` 的时间复杂度

###### 8.2 `unique`去重 ######

返回去重（只去掉**相邻**的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。

把一个`vector`去重：

int m = unique(a.begin(), a.end()) – a.begin();

把一个数组去重，元素存放在下标`1 ~ n`：

int m = unique(a + 1, a + n + 1) – (a + 1);

`m`: 不同元素的数量

###### 8.3 `random_shuffle`随机打乱 ######

用法与`reverse`相同。

> 随机数种子
> 
>     #include <ctime>
>     
>     int main()
>     {
>         srand(time(0));
>     }

###### 8.4 `sort` 排序 ######

对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。

把一个`int`数组（元素存放在下标`1 ~ n`）从大到小排序，传入比较函数：

int a[MAX_SIZE];
    bool cmp(int a, int b) // a是否应该排在b 的前面
    {
        return a > b;
    }
    sort(a + 1, a + n + 1, cmp); // 自定义
    
    // 默认从小到大
    
    // 从大到小也可以直接用greater
    sort(a, a + n, greater<int>());

把自定义的结构体`vector`排序，重载“小于号”运算符：

struct Rec
    {
        int id, x, y;
    };
    
    vector<Rec> a;
    
    bool operator <(const Rec &a, const Rec &b)
    {
            return a.x < b.x || a.x == b.x && a.y < b.y;
    }
    
    sort(a.begin(), a.end());

###### 8.5 `lower_bound`/`upper_bound` 二分 ######

`lower_bound`的第三个参数传入一个元素`x`，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于`x`的元素的位置的迭代器（指针）。

`upper_bound`的用法和`lower_bound`大致相同，唯一的区别是查找第一个大于`x`的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

在有序`int`数组（元素存放在下标`1 ~ n`）中查找**大于等于**`x`的最小整数的下标：

int i = lower_bound(a + 1, a + 1 + n, x) - a;
    
    int i = lower_bound(a, a + n, x) - a; // 下标从0开始

在有序`vector<int>`中查找**小于等于**`x`的最大整数（假设一定存在）：

int y = *--upper_bound(a.begin(), a.end(), x);

> 开始做题~~

`AcWing 67. 数字在排序数组中出现的次数`

class Solution {
    public:
        int getNumberOfK(vector<int>& nums , int k) {
            
            int cnt = 0;
            
            for(int x : nums)
                if(x == k)
                    cnt ++;
            
            return cnt;
            
        }
    };

> `vector`的遍历

`AcWing 68. 0到n-1中缺失的数字`

class Solution {
    public:
        int getMissingNumber(vector<int>& nums) {
            
            unordered_set<int> s;
            for(int i = 0; i <= nums.size(); i ++) s.insert(i);
            
            for(auto x : nums) s.erase(x);
            
            return *s.begin();
        }
    };

> 哈希表

`AcWing 32. 调整数组顺序使奇数位于偶数前面`

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
             
            int i = 0, j = array.size() - 1;
            
            while(i < j)
            {
                while(i < j && array[i] % 2) i ++;
                while(i < j && array[j] % 2 == 0) j --;
                
                if(i < j) swap(array[i], array[j]);
            }
            
        }
    };

> 可双指针

`AcWing 17. 从尾到头打印链表`

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> printListReversingly(ListNode* head) {
            
            vector<int> res;
            
            for(auto p = head; p ; p = p->next) res.push_back(p->val);
            
            reverse(res.begin(), res.end());
            
            return res;
        }
    };

> `a.push_back(x)`把元素x插入到`vector a`的尾部。
> 
> 然后翻转整个`vector`

`AcWing 20. 用两个栈实现队列`

class MyQueue {
    public:
        /** Initialize your data structure here. */
        
        stack<int> s1, s2;
        
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            s1.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            while(s1.size() > 1) s2.push(s1.top()), s1.pop();
    
            int t = s1.top();
            s1.pop();
            while(s2.size()) s1.push(s2.top()), s2.pop();        
            
            return t;
        }
        
        /** Get the front element. */
        int peek() {
            while(s1.size() > 1) s2.push(s1.top()), s1.pop();
    
            int t = s1.top();
            while(s2.size()) s1.push(s2.top()), s2.pop();        
            
            return t;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return s1.empty();
        }
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = MyQueue();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.peek();
     * bool param_4 = obj.empty();
     */

> 有一个帮手协助

`AcWing 53. 最小的k个数`

class Solution {
    public:
        vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
            
            sort(input.begin(), input.end());
            
            vector<int> res;
            
            for(int i = 0; i < k; i ++) res.push_back(input[i]);
            
            return res;
        }
    };

> 先排序，再输出

`AcWing 75. 和为S的两个数字`

class Solution {
    public:
        vector<int> findNumbersWithSum(vector<int>& nums, int target) {
            
            unordered_set<int> s;
            
            for(auto x : nums)
            {
                if(s.count(target - x)) return {x, target - x};
                s.insert(x);
            }
            
        }
    };

> 哈希表

`AcWing 51. 数字排列`

class Solution {
    public:
        vector<vector<int>> permutation(vector<int>& nums) {
            
            sort(nums.begin(), nums.end());
            
            vector<vector<int>> res;
            
            do{
                res.push_back(nums);
            }while(next_permutation(nums.begin(), nums.end()));
            
            return res;
        }
    };

> 库函数，`next_permutaion(begin(), end());` 返回下一个排列

`AcWing 26. 二进制中1的个数`

class Solution {
    public:
        int NumberOf1(int n) {
            int res = 0;
            
            while(n) n -= n & -n, res ++;
            
            return res;
        }
    };

> `lowbit(x) = x & -x`，返回`x`的最后一位`1`
> 
> 也可以用循环
> 
>     class Solution {
>     public:
>         int NumberOf1(int n) {
>             int res = 0;
>             
>             for(int i = 0; i < 32; i ++)
>                 if(n >> i & 1)
>                     res ++;
>             
>             return res;
>         }
>     };
> 
> ![在这里插入图片描述][af688271b3454ff5821339aa85e0515f.png_pic_center]

`AcWing 862. 三元组排序`

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 10010;
    
    struct Data
    {
        int x;
        double y;
        string z;
        
        bool operator< (const Data &t) const
        {
            return x < t.x;
        }
    }a[N];
    
    int main()
    {
        int n;
        cin >> n;
        
        for(int i = 0; i < n; i ++) cin >> a[i].x >> a[i].y >> a[i].z;
        
        sort(a, a + n);
        
        for(int i = 0; i < n; i ++) printf("%d %.2lf %s\n", a[i].x, a[i].y, a[i].z.c_str());
        
        return 0;
    }

> 结构体排序
> 
> 【注意】使用`printf()` 输出`string` 要 使用`.c_str()`

![在这里插入图片描述][bdb8997ad80145769eb2e3b2fc0621ef.png_pic_center]

> OK， 语法基础完结

![在这里插入图片描述][ea75fbab597e4eca9ee663305648fd12.png_pic_center]

￥49.00 值的！

![在这里插入图片描述][41c82d5396784d718d382f8b577a9d05.png_pic_center]

算法基础，我来了。

[39675a8f65bb4523a1b9872cee28421a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1494433781fc43a6b31dbd43cb9b24ca.png
[7d531b770bf343a29bc91e8f57e2a065.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/48179c102695415db70d80e10d0f8077.png
[31ae2d8a933941c0ae0464fe7b6c9b16.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1f5c6719bfb04497ac47f4e8f1651ed2.png
[378907c0a6fe438a806b3a66de95be75.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/631f9b911cde457c85c84a12e267b557.png
[af688271b3454ff5821339aa85e0515f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b0653a53b0b34ac18c20b4a959a3f1ea.png
[bdb8997ad80145769eb2e3b2fc0621ef.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1b5abe59647c4dadae88771304c73627.png
[ea75fbab597e4eca9ee663305648fd12.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c6e2c63024c14a9489986589bf71b542.png
[41c82d5396784d718d382f8b577a9d05.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/8cba364bd4474eb58d91f29f5af50c3f.png