C++语法基础--STL、位运算、常用库函数
一、STL
1、vector
vector 是一种序列容器，允许在运行时动态地插入和删除元素。使用时需要包含#include<vector>这个头文件。
- size返回vector的实际长度，empty函数返回一个bool类型，表明vector是否为空。
- 二者的时间复杂度都是 O(1)。所有的STL容器都支持这两个方法。
- 迭代器就像STL容器的指针，可以用*操作符解除引用。
- vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。
- begin()函数返回指向vector中的第一个元素的迭代器。
- end()函数返回vector的尾部，就是最后一个元素的下一个。
- front()表示返回vector的第一个元素。
- back()表示返回vector的最后一个元素。
- push_back(x)表示在vector的末尾插入元素x。
- pop_back()表示删除vector的末尾元素。
vector实例
#include<iostream> #include<vector> using namespace std; int main(){ // 创建vector a vector<int> a; // 添加元素 a.push_back(1); a.push_back(2); a.push_back(3); a.push_back(4); a.push_back(5); // 获取vector a 的长度并判断是否非空 int len = a.size(); bool is_empty = a.empty(); cout<<len<<" "<<is_empty<<endl; // 返回第一个和最后一个元素 int first = a.front(); int last = a.back(); cout<<first<<" "<<last<<endl; // 删除最后一个元素 a.pop_back(); // 删除指定的某个元素-----删除第三个元素 a.erase(a.begin() + 2); // 更新第一个和最后一个元素 first = a.front(); last = a.back(); cout<<first<<" "<<last<<endl; // 使用迭代器遍历vector----输出vector a中的所有元素 for(vector<int>::iterator it = a.begin(); it < a.end(); it++){ cout<< *it <<endl; } // 通过下标访问元素 cout<<a[2]<<endl; // 清空所有元素 a.clear(); // 获取vector a 的长度并判断是否非空 len = a.size(); is_empty = a.empty(); cout<<len<<" "<<is_empty<<endl; return 0; }通过使用上述介绍的所用函数，具体展现了每一个函数的用法和作用。
push_back和pop_back函数
front和back函数
begin和end函数
迭代器
erase函数
可以使用 erase() 方法删除 vector 中的元素。
clear函数
可以使用 clear() 方法清空 vector 中的所有元素。
size和empty函数
声明
#include<iostream> #include<vector> using namespace std; int main(){ vector<int> a;//一个长度是动态变化的int数组 vector<int> b[233]; //第一维长度是233，第二维是动态变化的int数组 return 0; }2、queue
使用时需要包含#include<queue>头文件。queue主要包括循环队列queue和优先队列priority_queue两个容器。遵循元素在队首添加，队尾移出的规则。
实例
#include<iostream> #include<queue> using namespace std; int main(){ // 创建优先队列 priority_queue<int> q; // 添加元素 q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); // 创建一个临时队列m------默认是最大堆（也就是升序排列） priority_queue<int> m = q; while(m.empty() != 1){ cout<<m.top()<<endl; m.pop(); } // 删除队首元素 q.pop(); q.pop(); // 输出q队列元素 while(q.empty() != 1){ cout<<q.top()<<endl; q.pop(); } return 0; }top函数
返回队列顶部的元素（并不删除）。
pop函数
移除队列顶部的元素。
push函数
向队列中添加一个元素。
优先队列priority_queue
实例
#include<iostream> #include<queue> using namespace std; int main(){ // 创建queue queue<int> q; // 添加元素 q.push(1); q.push(2); q.push(3); q.push(4); // 创建一个临时队列m queue<int> m = q; // 遍历所有元素 while(m.empty() != 1){ // 如果队列不为空，则输出队首元素 cout<<m.front()<<endl; // 输出之后弹出队首元素 m.pop(); } //输出q队列的队首和队尾元素 cout<<q.front()<<endl; cout<<q.back()<<endl; // 输出q队列的长度 cout<<q.size()<<endl; return 0; }back函数
back()返回队尾元素。
front函数
front()返回队首元素。
pop函数
pop()移除队首元素。
push函数
push()在队尾添加一个元素。
循环队列queue
声明
#include<iostream> #include<queue> using namespace std; int main(){ queue<int> q; priority_queue<int> a; //大根堆 priority_queue<int, vector<int>, greater<int>> b;//小根堆 priority_queue<pair<int,int>>c; return 0; }3、stack
使用时需要包含#include<stack>头文件。
实例
#include<iostream> #include<stack> using namespace std; int main(){ // 创建 stack<int> s; // 栈顶添加元素 s.push(1); s.push(2); s.push(3); s.push(4); // 遍历元素 stack<int> t = s; while(t.empty() != 1){ cout<<t.top()<<endl; t.pop(); } // 删除s的栈顶元素 s.pop(); s.pop(); // 删除s中的元素 while(s.empty() != 1){ cout<<s.top()<<endl; s.pop(); } return 0; }top函数
返回栈顶元素，但不删除。
pop函数
移除栈顶元素。
push函数
在栈顶添加一个元素。
声明
4、deque
实例
#include<iostream> #include<deque> using namespace std; int main(){ // 创建队列 deque<int> q; // 添加元素 q.push_front(1); q.push_back(2); q.push_front(3); q.push_back(4); int len = q.size(); bool is_empty = q.empty(); cout<<len<<" "<<is_empty<<endl; // 遍历所有元素 for(deque<int>::iterator it = q.begin(); it < q.end(); it++){ cout<< *it <<endl; } // 删除元素 q.pop_back(); q.pop_front(); len = q.size(); is_empty = q.empty(); cout<<len<<" "<<is_empty<<endl; // 遍历所有元素 for(deque<int>::iterator it = q.begin(); it < q.end(); it++){ cout<< *it <<endl; } // 清空 q.clear(); len = q.size(); is_empty = q.empty(); cout<<len<<" "<<is_empty<<endl; return 0; }clear函数
clear()表示清空队列
pop_front和pop_back函数
pop_front()从队头出队，pop_back()从队尾出队
push_front和push_back函数
push_front()从队头出队，push_back()从队尾入队
front和back函数
返回队头和队尾元素
begin和end函数
返回deque的头为迭代器
声明
#include<iostream> #include<deque> using namespace std; int main(){ deque<int> q; return 0; }5、set
使用时需要包含#include<set>头文件。
- size()用来获取容器的长度。
- empty()用来判断容器是否非空。
- clear()用来清空容器元素。
- set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号*解除引用，仅支持++和--两个与算术相关的操作。
- 设it是一个迭代器，例如set<int>::iterator it;
- 若把it ++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it --，则it将会指向排在“上一个”的元素。
- 返回首、尾迭代器，时间复杂度均为 O(1)。
- s.begin()是指向集合中最小元素的迭代器。
- s.end()是指向集合中最大元素的下一个位置的迭代器。
- s.insert(x)把一个元素x插入到集合s中，时间复杂度为 O(logn)。
- 在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
- 这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。
- s.lower_bound(x)查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
- s.upper_bound(x)查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
- 设it是一个迭代器，s.erase(it)从s中删除迭代器it指向的元素，时间复杂度为 O(logn)。
- 设x是一个元素，s.erase(x)从s中删除所有等于x的元素，时间复杂度为 O(k+logn)，其中 k 是被删除的元素个数。
实例
#include<iostream> #include<set> using namespace std; int main(){ // 创建实例 set<int> s; // 添加元素 s.insert(1); s.insert(2); s.insert(3); s.insert(4); s.insert(5); // 获取长度并判断是否非空 int len = s.size(); bool is_empty = s.empty(); cout<<len<<" "<<is_empty<<endl; // 遍历元素(输出) for(set<int>::iterator it = s.begin(); it != s.end(); it++){ cout<< *it <<endl; } // 删除元素 s.erase(3); len = s.size(); is_empty = s.empty(); cout<<len<<" "<<is_empty<<endl; // 遍历元素(输出) for(set<int>::iterator it = s.begin(); it != s.end(); it++){ cout<< *it <<endl; } // 查找元素2 if(s.find(2) != s.end()){ cout<<"2 is yes"<<endl; }else{ cout<<"2 is no"<<endl; } // 输出出现的次数 int count = s.count(0); cout<<count<<endl; return 0; }count函数
s.count(x)返回集合s中等于x的元素个数，时间复杂度为 O(k+logn)，其中 k 为元素x的个数。
erase函数
lower_bound和upper_bound函数
find函数
s.find(x)在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为 O(logn)。
insert函数
begin和end函数
迭代器
size、empty、clear函数
声明
#include<iostream> #include<set> using namespace std; int main(){ set<int> s; return 0; }6、map
使用时需要包含#include<map>头文件
实例
#include <iostream> #include <map> #include <string> using namespace std; int main() { // 创建一个 map 容器，存储员工的姓名和年龄 map<string, int> employees; // 插入员工信息 employees.insert(make_pair("Alice",30)); employees.insert(make_pair("Bob",25)); employees.insert(make_pair("Charlie",35)); // 遍历 map 并打印员工信息 for (map<string, int>::iterator it = employees.begin(); it != employees.end(); ++it) { // it->first是键，it->second是值 cout<< it->first << ":" << it->second <<endl; } // 获取长度并判断是否非空 int len = employees.size(); bool is_empty = employees.empty(); cout<<len<<" "<<is_empty<<endl; // 查找键值 map<string, int>::iterator it = employees.find("Bob"); if(it != employees.end()){ if(it->second == 25){ cout<<"Bob: 25 is yes"<<endl; }else{ cout<<"Bob: 25 is no"<<endl; } }else{ cout<<"Bob: 25 is no"<<endl; } // 清空 employees.clear(); len = employees.size(); is_empty = employees.empty(); cout<<len<<" "<<is_empty<<endl; return 0; }find函数
h.find(x)在变量名为h的map中查找key为x的二元组。
insert和erase函数
与set类似，但其参数均是pair<key_type, value_type>。
size、empty、clear、begin、end函数
和set类似。
声明
map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
#include<iostream> #include<map> using namespace std; int main(){ map<long long, bool> vis; return 0; }二、位运算
1、位运算
| & | 与 |
| | | 或 |
| ~ | 非 |
| ^ | 异或 |
| >> | 右移 |
| << | 左移 |
2、常见操作
lowbit(x) = x & -x，返回x的最后一位1
#include<iostream> #include<string> using namespace std; int main(){ int num; cin>>num; int lowbit = num & -num; cout<< lowbit <<endl; return 0; }求x的第k位数字 x >> k & 1
#include<iostream> #include<string> using namespace std; int main(){ int num; cin>>num; int k ; cin>>k; cout<< ((num>>k) & 1) <<endl; return 0; }三、常用库函数
1、reverse函数
将元素进行翻转。例子：翻转数组和vector。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(){ int a[10] = {1,2,3,4,5,6,5,4,3,2}; for(int i = 0; i < 10; i++){ cout<<a[i]<<endl; } cout<<endl; // 翻转数组 reverse(a,a + 10); for(int i = 0; i < 10; i++){ cout<<a[i]<<endl; } cout<<endl; vector<int> q; // 添加元素 q.push_back(1); q.push_back(2); q.push_back(3); q.push_back(4); // 输出 for(vector<int>::iterator it = q.begin(); it < q.end(); it++){ cout<< *it <<endl; } cout<<endl; // 翻转vector q reverse(q.begin(),q.end()); // 输出 for(vector<int>::iterator it = q.begin(); it < q.end(); it++){ cout<< *it <<endl; } return 0; }2、unique函数
返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(){ vector<int> q; // 添加元素 q.push_back(1); q.push_back(2); q.push_back(2); q.push_back(2); q.push_back(3); q.push_back(3); q.push_back(4); // 输出 for(vector<int>::iterator it = q.begin(); it != q.end(); it++){ cout<< *it <<endl; } cout<<endl; // 去重vector q vector<int>::iterator new_end = unique(q.begin(),q.end()); q.erase(new_end, q.end()); // 输出不重复元素的数量 int m = q.size(); cout << "Number of unique elements: " << m << endl; // 去重后的元素 cout << "After removing duplicates: "; for(vector<int>::iterator it = q.begin(); it != q.end(); it++){ cout<< *it << " "; } cout<<endl; return 0; }3、random_shuffle函数
用法与reverse相同。随机打乱。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main(){ vector<int> a; // 添加元素 a.push_back(1); a.push_back(2); a.push_back(3); a.push_back(4); a.push_back(5); // 输出 for(vector<int>::iterator it = a.begin(); it != a.end(); it++){ cout<< *it <<endl; } cout<<endl; // 随机打乱 random_shuffle(a.begin(), a.end()); // 输出 for(vector<int>::iterator it = a.begin(); it != a.end(); it++){ cout<< *it <<endl; } return 0; }4、sort函数
对两个迭代器（或指针）指定的部分进行快速排序。默认是升序排列。
#include<iostream> #include<algorithm> using namespace std; int main(){ int a[10] = {1,2,3,2,1,4,3,2,1,10}; // 默认是升序排列 sort(a,a + 10); for(int i = 0; i < 10; i ++){ cout<<a[i]<<endl; } cout<<endl; // 这种是降序排列 sort(a,a + 10,greater<int>()); for(int i = 0; i < 10; i ++){ cout<<a[i]<<endl; } return 0; }5、lower_bound/upper_bound 函数
- lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int a[10] = {1,3,5,7,9,2,4,6,8,10}; // 排序 sort(a,a + 10); // 在已排序的数组中找到>=5的最小整数的下标 int i = lower_bound(a, a + 10, 5) - a; cout<<i<<endl; // 在已排序的数组中找到>5的最小整数的下标 int j = upper_bound(a, a + 10, 5) - a; cout<<j<<endl; return 0; }
