vetor(数组)
迭代器
迭代器就相当于STL中的指针，按照定义方式，可以分为下面四类：
- 正向迭代器：容器类名
::iterator迭代器名; begin(); end(); - 常正向迭代器：容器类名
::const_iterator迭代器名； cbegin(); cend(); - 反向迭代器：容器类名
::reverse_iterator迭代器名； rbegin(); rend(); - 常反向迭代器：容器类名
::const_reverse_iterator迭代器名； crbegin(); crend();
迭代器用法示例：
通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。
- 对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；
- 反向迭代器进行++操作时，迭代器会指向容器中的前一个元素；
#include<vector> #include<iostream> using namespace std; int main(){ vector<int> v; //v是存放int类型变量的可变长数组，开始时没有元素 for(int n = 0; n < 5; n++) v.push_back(n); //push_back函数在vector容器尾部添加一个元素 //定义正向迭代器 vector<int>::itertor i; for(i = v.begin(); i != v.end(); ++i){ //用迭代器遍历容器 cout << *i << " "; //*i 就是迭代器i指向的元素 *i *= 2; //每个元素变为原来的2倍 } cout << endl; //定义常正向迭代器 for(vector<int>::const_itartor i = v.cbegin(); i != v.cend(); ++i) cout << *i << " "; //定义反向迭代器 for(vector<int>::reverse_itartor i = v.rbegin(); i != v.rend(); ++i) cout << *i << " "; //定义反向迭代器 for(vector<int>::const_reverse_itartor i = v.crbegin(); i != v.crend(); ++i) cout << *i << " "; return 0; }
程序输出结果：
0 1 2 3 4 0 2 4 6 8 8 6 4 2 0 8 6 4 8 0
第12行和第23行相当如下：
CDemo CDemo::operator++ () { //前置++ ++n; return *this; } CDemo CDemo::operator ++(int k) { //后置++ CDemo tmp(*this); //记录修改前的对象 n++; return tmp; //返回修改前的对象 }
按照功能分类：
| 容器 | 迭代器功能 |
| vector | 随机访问 |
| deque | 随机访问 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| priority_queue | 不支持迭代器 |
例如，vector的迭代器是随机迭代器，因此遍历vector容器有以下几种做法。【实例】遍历vector容器。
#include<iostream> #include<vector> using namespace std; int main() { vector<int> v(100); //v被初始化成有100个元素 for(int i = 0; i < v.size(); i++) //size返回元素个数 cout << v[i]; //像普通数组一样使用vector容器 vector<int>::iterator i; //用于双向迭代器，双向迭代器不支持 “<”进行比较 for(i = v.begin(); i != end(); i++) //用！=比较两个迭代器 cout << *i ; //用于单向迭代器 for(i = v.begin(); i < v.end(); i++) //用 < 比较两个迭代器 cout << *i; i = v.begin(); while(i < v.end()){//间隔一个输出 cout << *i; i += 2; //随机访问迭代器支持 “+= 整数” 的操作 } }
迭代器的辅助函数
STL中有用于操作迭代器的三个函数模板，它们是：
advance(p, n); //使迭代器p向前或向后移动元素 distance(p, q); //计算两个迭代器之间的距离，即迭代器p经过多少次++操作后和迭代器q相等。如果调用p时已经指向q的后面，则这个函数会陷入死循环。 iter_swap(p, q); //用于交换两个迭代器p、q指向的值
实际函数操作如下：
#include<list> #include<iostream> #include<algorithm> using namespace std; int main() { int a[5] = {1, 2, 3, 4, 5}; list<int> lst(a, a + 5); list<int>::iterator p = list.begin(); advance(p, 2); //p向后移动两个元素，指向3 cout << "1)" << *p << endl; //输出1）3 advance(p, -1); //p向前移动一个元素，指向2 cout << "2)" << *p << endl; //输出2）2 list<int>::iterator q = list.end(); q--; //q指向 5 cout << "3)" << distance(p, q) << endl; //输出 3）3 iter_swap(p, q); //交换 2 和 5 cout << "4)"; for(p = lst.begin(); p != lst.end(); p++) cout << *p << ednl; return 0; }
程序输出结果：
1)3 2)2 3)3 4)1 5 3 4 2
vetor的定义和特性
在c++中，vector是一个动态数组容器，可以存储一系列相同类型的元素。它是标准库==== 中定义的模板类。
vetor的定义和结构非常简单，它由以下几个重要的部分组成：
模板类声明： vetor是一个模板类，因此在使用之前需要包含头文件.声明一个vetor对象的通用语法如下：
vetor<T> vec; //这里的T是要存储在vector中的元素类型 //T可以为int、char、double......
容器大小： vector是一个动态数组，可以根据需要自动调整大小。它会根据元素的数量动态分配内存空间。
元素访问： 可以通过索引来访问vector中的元素。索引从0开始，最后一个元素的索引是size() - 1。可以使用[ ]运算符或at()函数来访问元素
元素添加和删除： 可以使用push_back()函数在vector中元素的数量，使用empty()函数检查vector是否为空。还可以使用resize()函数调整vector的大小
迭代器： vector提供了迭代器，可以用于遍历容器中的元素，可以使用begin()函数获取一个元素的迭代器，使用end() 函数获取指向最后一个元素之后位置的迭代器。
vector的常用函数
push_back(): 将元素添加到vector的末尾
void push_back(const T& value);
pop_back(): 删除vector末尾的元素
void pop_back();//一定要保证vector非空
begin() 和 end(): 返回指向vector第一个元素和最后一个元素之后位置的迭代器
例子：
vector<int> vec = {10, 20, 30}; for(auto it = vec.begin(); it != vec.end(); ++it){ cout << *it << " "; }
vector排序去重
排序： 要对vector进行排序，可以使用标准库中的sort函数，该函数位于头文件中。
#include<algorithm> vector<T> vec = {. . .}; //这里T是vector 中元素的类型 sort(vec.begin(),vec.end()); //sort函数接受两个迭代器参数，表示要排序的范围 //vec.begin()返回指向vector第一个元素的迭代器 //vec.end()返回指向最后一个元素之后位置的迭代器
示例
#include<iostream> #include<vector> #include<algorlthm> int main(){ vector<int> vec = {5, 2, 8, 1, 9}; sort(vec.begin(),vec.end()); for(const auto& num : vec){ cout << num << " "; } return 0; }
输出
| 1 2 5 8 9 |
去重： 要去除vector中的重复元素，可以使用unique函数。该函数位于头文件中。
#include<algorithm> vector<T> vec = { . . .}; sort(vec.begin(),vec.end()); auto last = =unique(vec.begin(),vec.end()); vec.erase(last,vec.end());
首先，需要对vector进行排序，以便相同的元素相邻。然后，，unique函数将重复的元素移动到vector的末尾，并返回一个指向重复的迭代器。最后，可以使用vec.erase函数将重复元素从vector中删除
示例：
#include<iostream> #include<vector> #include<algorlthm> int main(){ vector<int> vec = {2, 1, 3, 2, 4, 1, 5, 4}; sort(vec.begin(),vec.end()); auto last = =unique(vec.begin(),vec.end()); vec.erase(last,vec.end()); for(const auto& num : vec){ cout << num << " "; } return 0; } //注意vector中的重复元素被去除，只保留了不重复的元素。
输出：
| 1 2 3 4 5 |
queue（队列）
queue队列
queue是一种先进后出（FIFO）的数据结构
queue提供了一组函数来操作和访问元素，但它的功能相对简单
queue的定义和结构如下：
template<class T, class Container = deque<T>> class queue; //T:表示存储在queue中的元素的类型 //Container：表示底层容器的类型，默认为deque。也可以使用其他容器类型，如list
queue的内部实现使用了底层容器来存储元素，并且只能通过特定的函数来访问和操作元素，以下是一些queue的常用函数：
#include<queue> //queue容器的头文件 queue<int> q; //声明 struct node {int x, y, z;}; queue<node> qq; //声明一个结构体类型的队列容器 q.push(111); //将111插入队尾 O(1) q.pop(); //将队头元素删除 O(1) int x = q.front(); //返回队头元素 O(1) int y = q.back(); //返回队尾元素 O(1)
priority_queue按照元素从大到小排序
tempplate<class T, class Container = vector<T>, class Compare = less<typename //比较函数 Container::value_type>> class priority_queue; //T:表示存储在queue中的元素的类型 //Container：表示底层容器的类型，默认为deque。也可以使用其他容器类型，如deque //Compare:表示元素之间的比较函数对象的类型，默认为less，即按照元素的值进行比较
priority_queue的内部实现使用了底层容器来存储元素，并且只能通过特定的函数来访问和操作元素。以下是一些priority_queue的常用函数：
| 函数 | 描述 | 时间复杂度 |
| push(x) | 将元素x插入到优先队列中 | O(logN) |
| pop() | 弹出有限队列中的顶部元素 | O(logN) |
| top() | 返回优先队列中的顶部元素 | O(1) |
| empty() | 检查优先队列是否为空 | O(1) |
| size() | 返回优先队列中元素的个数 | O(1) |
几种优先队列修改比较函数的方法
struct Compare{ bool operator()(int a, int b){ //自定义的比较函数，按照逆序排列 return a > b; } } int main(){ priority_queue<int, vector<int>,Compare> pq; auto compare = [](int a, int b){ //自定义的比较函数，按照逆序排序 return a > b; } priority_queue<int, vector<int>,Compare> pq(compare); }
如果优先队列中的元素类型比较简单，可以直接使用
greater来修改比较方法.
priority_queue<int, vector, greater> pq;
greater函数对象定义在头文件中
deque双端队列
deque(双端队列)是一个容器，它允许在两端进行高效的插入和删除操作。
template<class T, class Allocator = allocator<T> class deque; //T表示存储在deque中的元素的类型 //Allocator:表示用于分配内存的分配器类型，默认为allocator
| 函数 | 描述 | 时间复杂度 |
| push_back(x) | 在尾部插入元素x | 平摊O(1) |
| push_front(x) | 在头部插入元素x | 平摊O(1) |
| pop_back() | 弹出尾部元素 | 平摊O(1) |
| pop_front() | 弹出头部元素 | 平摊O(1) |
| front() | 返回头部元素 | O(1) |
| back() | 返回尾部元素 | O(1) |
| empty() | 检查deque是否为空 | O(1) |
| size() | 返回deque中元素的个数 | O(1) |
| clear() | 清空deque中所有的元素 | O(N) |
| insert(pos,x) | 在指定位置pos插入元素 | 平摊O(N) |
| erase(pos) | 移除指定位置pos处的元素 | 平摊O(N) |
| erase(first,last) | 移除(first,last)范围内的元素 | 平摊O(N) |
set
set集合
set 是一种容器，用于存储一组唯一的元素，并按照一定的排序规则进行排序。set中的元素是按照升序排序的，默认情况下，它使用元素的比较运算符（<)来进行排序。
set的定义结构如下：
template<class key, class Compare = less<key>, class Allocator = allocator<key>> class set;
- key: 表示存储在set中的元素的类型。
- Compare: 表示元素之间的比较函数对象的类型，默认为less，即按照元素的值进行比较。
- Allcoator: 表示用于分配内存的分配器类型，默认为allocator.
set的内部实现使用了红黑树（一种自平衡的二叉搜索树)来存储元素，并爆出元素的有序性，这使得在set中插入、删除和查找元素的时间复杂度都是对数时间，即O(log n).
set中的元素是唯一的，即不允许重复的元素存在，当插入一个重复的元素时，set会自动忽略该元素。
set函数
s.insert(key); //向set中插入一个元素key。 s.erase(key); //从set中移除指定的元素key。 s.find(key); //查找set中是否存在指定的元素key，如果存在则返回指向该元素的迭代器，否则返回set::end()。 s.lower_bound(key); //返回指向第一个不小于给定键值key的元素的迭代器。 s.upper_bound(key); //返回指向第一个大于给定键值key的元素的迭代器。 s.equal_range(); //返回一个返回，其中包含所有给定的元素 s.size(); //返回集合中元素的数量 s.empty(); //检查集合是否为空 s.clear(); //清空set中的所有元素。 s.begin(); //指向集合中最小元素的迭代器 s.end(); //指向集合中最大元素的下一个位置的迭代器 s.rebegin(); //返回指向集合末尾位置的逆向迭代器 s.rend(); //返回指向集合起始位置的逆向迭代器 s.swap(); //交换两个集合 s.count(key); //返回set中与指定元素key相等的元素的个数，由于set中不允许有重复的元素，因此返回值只能是0或1。
修改set比较方法的常见手段，后面的multiset类似
#include<iostream> #include<set> using namespace std; int main(){ set<int,greater<int>> mySet; mySet.insert(25); mySet.insert(17); mySet.insert(39); mySet.insert(42); for(const auto& elem : mySet){ cout << elem << " "; } cout << endl; return 0; }
#include<iostream> #include<set> using namespace std; struct MyCompare{ bool operator()(const int& a, const int& b) const{ //自定义比较逻辑 return a > b;//改为逆序 } }; int main(){ set<int, MyCompare> mySet; //mYCompare是仿函数 mySet.inster(25); mySet.inster(17); mySet.inster(39); mySet.inster(42); for(const auto& elem : mySet){ cout << elem << " "; } cout << endl; return 0; }
multiset多重集合
multiset 是一种容器，它与set类似，用于存储一组元素，并按照一定的排序规则进行排序。
不同之处在于，multiset容器允许存储重复的元素
multiset的定义和结构与set类似，如下所示：
template <class Key, class Compare = less<key>, class Allocator = allocator<key>> class multiset;
- key: 表示存储在set中的元素的类型。
- Compare: 表示元素之间的比较函数对象的类型，默认为less，即按照元素的值进行比较。
- Allcoator: 表示用于分配内存的分配器类型，默认为allocator.
multiset的内部实现也使用红黑树来存储元素，并保持元素的有序性。与set不同的是，multiset中的元素可以重复出现
multiset函数
s.insert(key); //向set中插入一个元素key。 s.erase(key); //从set中移除指定的元素key。 s.find(key); //查找set中是否存在指定的元素key，如果存在则返回指向该元素的迭代器，否则返回set::end()。 s.lower_bound(key); //返回指向第一个不小于给定键值key的元素的迭代器。 s.upper_bound(key); //返回指向第一个大于给定键值key的元素的迭代器。 s.size(); //返回集合中元素的数量 s.empty(); //检查集合是否为空 s.clear(); //清空set中的所有元素。 s.begin(); //指向集合中最小元素的迭代器 s.end(); //指向集合中最大元素的下一个位置的迭代器 s.rebegin(); //返回指向集合末尾位置的逆向迭代器 s.rend(); //返回指向集合起始位置的逆向迭代器 s.swap(); //交换两个集合 s.count(key); //返回set中与指定元素key相等的元素的个数，由于set中不允许有重复的元素，因此返回值只能是0或1。
unordered_set无序集合
unordered_set 是一种容器，用于存储一组唯一的元素，并且没有特定的顺序。unorderde_set容器使用哈希表来实现元素的存储和访问，因此元素的插入、删除和查找的时间复杂度都是常数时间，即O(1)。
unordered_set的定义和结构如下：
template <class key, class Hash = Hash<key>, class keyEqual = equal_to<key>, class Allocator = allocator<key>> class unordered_set;
- key: 表示存储在set中的元素的类型。
- Hash: 表示用于计算元素哈希值的哈希函数对象的类型，默认为hash，使用key类型默认哈希函数
- keyEqual: 表示用于比较元素是否相等的函数对象的类型，默认为equal_to,使用key类型的默认相等比较函数
- Allcoator: 表示用于分配内存的分配器类型，默认为allocator.
- unordered_set 中的元素是唯一的，即不允许重复的元素的存在。当插入一个重复的元素时，unoredered_set会自动忽略该元素。
unordered_set函数
s.insert(key); //向set中插入一个元素key。 s.erase(key); //从set中移除指定的元素key。 s.find(key); //查找set中是否存在指定的元素key，如果存在则返回指向该元素的迭代器，否则返回set::end()。 s.count(key); //返回set中与指定元素key相等的元素的个数，由于set中不允许有重复的元素，因此返回值只能是0或1。 s.size(); //返回集合中元素的数量
代码示例：
#include <iostream> #include <set> using namespace std; int main() { set<int> mySet; // 插入元素 mySet.insert(5); mySet.insert(2); mySet.insert(8); mySet.insert(2); // 重复元素，不会被插入，因为set自动去重 // 遍历集合 cout << "Set elements: "; for (const auto& elem : mySet) { cout << elem << " "; } cout << endl; // 应该输出：2 5 8（注意顺序可能因实现而异，但一定是升序） // 查找元素 int searchValue = 5; auto it = mySet.find(searchValue); if (it != mySet.end()) { cout << searchValue << " found in the set." << endl; } else { cout << searchValue << " not found in the set." << endl; } // 移除元素 int removeValue = 2; mySet.erase(removeValue); // 再次遍历集合 cout << "Set elements after removal: "; for (const auto& elem : mySet) { cout << elem << " "; } cout << endl; // 应该输出剩余的元素，例如：5 8（顺序可能因实现而异） // 清空集合 mySet.clear(); // 检查集合是否为空 if (mySet.empty()) { cout << "Set is empty." << endl; } else { cout << "Set is not empty." << endl; } return 0; }
set板子
#define fi first #definese second constint INF Xfffffff: constint mod = 1e9 + 7; int N = 2e5 + 10; void Solved(){ set<int> st; for(int i=10;i>0;i--) st.insert(i); //for(const auto&i:st) cout << i<< endl; for(set<int>::iterator it = st.begin();it != st.end();it ++ ){ cout << *it << endl; } signed main(void){ IOS int ALL =1: cin >>ALL; while(ALL --) Solved(); // cout<< fixed;/制以小数形式显示 //cout<< setprecision(n)://保留n位小数 return 0; }
stack(栈)
stack的定义和结构
stack是一种后进先出（LIFO）的数据结构，使用前需要包含头文件。
stack提供了一组函数来操作和访问元素，但它的功能相对较简单。
stack的定义和结构如下：
template <class T, class CONtainer = deque<T>> class stack;
stack的常用函数
stack<int> stk; stk.push(x);//将x加入栈中，即入栈操作 stk.pop();//出栈操作(删除栈顶)，只是出栈，没有返回值 stk.top();//返回第一个元素(栈顶元素) stk.size();//返回栈中的元素个数 stk.empty();//当栈为空时，返回 true
stack不能遍历
如果将数组的元素依次放入栈，再依次取出，则可以将数组翻转
代码示例：
#include <iostream> #include <stack> using namespace std; int main() { stack<int> myStack; // 向栈中插入元素 myStack.push(10); myStack.push(20); myStack.push(30); myStack.push(40); //获取栈顶元素 cout << "栈顶元素：" << myStack.top() << endl; //弹出栈顶元素 myStack.pop(); //再次获取栈顶元素 cout << "弹出一个元素后的栈顶元素：" << myStack.top() << endl; // 检查栈是否为空 if (myStack.empty()) { cout << "栈为空" << endl; } else { cout << "栈不为空" << endl; } //获取栈的大小 cout << "栈的大小：" << myStack.size() << endl; return 0; }
map（映射）
map容器是一个键值对 key - value 的映射。其内部实现是一棵以key为关键码的红黑树。map的key和value可以是任意类型，其中key必须定义“小于号”运算符
map的定义和结构如下：
template<class key, class T, class Compare = less<key>, class Allocator = allocator<pair<const key, T>>> class map;
map<long long, bool> vis; map<string, int> hash; map<pair<int, int>, vector<int> > test;
在很多时候，map容器被当作Hash表使用，建立从复杂信息key（如字符串）到简单信息value（如一定范围内的整数）的映射。
因为map基于平衡树实现，所以它的大部分操作的时间复杂度都在O(log n)级别，比Hash函数实现的传统Hash表慢。
map函数（常用）
map<string, int> h; undered_map<string, int> operator; h.insert() //插入键值对到map中。有多种形式的insert()函数重载，可以接受单个键值对、迭代器范围或者初始化列表作为参数。 h.erase() //从map中删除指定键的键值对。有多种形式的erase()函数重载，可以接受单个键、迭代器范围或者删除满足特定条件的键值对。 h.find() //查找指定键的位置，并返回指向该位置的迭代器。如果键不存在，则返回map的end()迭代器。 h.count() //返回指定键在map中的个数。由于map中的键是唯一的，因此返回值只能是0或1。 //判断key是否存在 h.size() //返回元素个数 h.begin() //返回元素个数 h.end() //返回元素个数 h.empty() //检查map是否为空。如果map为空，则返回true，否则返回false。 h.clear() //清空map，删除所有的键值对。 h.lower_bound() //返回指向第一个不小于指定键的元素位置 h.upper_bound() //返回指向第一个大于指定键的元素位置
multimap
multimap是一种关联容器，类似于map，但允许存储多个具有相同键值对
multimap容器根据键来自动进行排序，并且可以通过键快速查找对应的值
multimap定义结构：
template<class key, class T, class Compare = less<key>, class Allocator = allocator<pair<const key, T>>> class multimap;
函数：
map<string, int> h; undered_map<string, int> operator; h.insert() //插入键值对到map中。有多种形式的insert()函数重载，可以接受单个键值对、迭代器范围或者初始化列表作为参数。 h.erase() //从map中删除指定键的键值对。有多种形式的erase()函数重载，可以接受单个键、迭代器范围或者删除满足特定条件的键值对。 h.find() //查找指定键的位置，并返回指向该位置的迭代器。如果键不存在，则返回map的end()迭代器。 h.count() //返回指定键在map中的个数。由于map中的键是唯一的，因此返回值只能是0或1。 h.size() //返回map中键值对的个数。 h.empty() //检查map是否为空。如果map为空，则返回true，否则返回false。 h.clear() //清空map，删除所有的键值对。 operator[] //访问指定键的值。如果键存在，则返回对应的值；如果键不存在，则会插入一个新的键值对，关联的值被默认构造。
如果多次查找的key不存在，当时间一长，容器里会多很多无用的0值，占用内存。
在使用 [ ] 操作符之前，最好先用find函数检查key的存在性
使用map容器的示例代码
#include<iostream> #include<map> using namespace std; int main(){ //创建并初始化map map<int, string> myMap = {{1,"Apple"},{2,"Banana"},{3,"Orange"}}; //插入元素 myMap.insert(make_pair(4,"Grapes")); //查找和访问元素 cout << "Value at key 2: " << myMap[2] << endl; //遍历并打印map中的元素 for(const auto& pair : myMap){ cout << "key: " << pair.first << ",Value: " << pair.cond << endl; } //删除元素 myMap.erase(3); //判断元素是否存在 if(myMap.count(3) == 0){ cout << "key 3 not found." << endl; } //删除元素 myMap.erase(3); //判断元素是否存在 if(myMap.count(3) == 0){ cout << "key 3 not found." << endl; } //清空map myMap.clear(); //判断map是否为空 if(myMap.empty()){ cout << "Map is empty." << endl; } return 0; }
使用multimap容器的示例代码
#include<iostream> #include<map> using namespace std; int main(){ //创建并初始化multimap map<int, string> myMultimap = {{1,"Apple"},{2,"Banana"},{3,"Orange"}}; //插入元素 myMultimap.insert(make_pair(4,"Grapes")); //查找和访问元素 auto range = myMultimap.equal_range(2); for(auto it = rang.first; it != range.second; +it){ cout << "key:" << it->first << ",Value:" << it->second <<endl; } //遍历并打印Multimap中的元素 for(const auto& pair : myMultimap){ cout << "key: " << pair.first << ",Value: " << pair.cond << endl; } //删除元素 myMultimap.erase(3); //判断元素是否存在 if(myMultimap.count(3) == 0){ cout << "key 3 not found." << endl; } //清空map myMultimap.clear(); //判断map是否为空 if(myMultimap.empty()){ cout << "Map is empty." << endl; } return 0; }
使用unordered_map容器的示例代码
#include <iostream> #include <unordered_map> #include <string> int main() { // 创建一个unordered_map容器 std::unordered_map<int, std::string> myMap; // 插入键值对 myMap.insert({1, "one"}); myMap.insert({2, "two"}); myMap[3] = "three"; // 访问值 std::cout << myMap[1] << std::endl; // 输出: one // 检查键是否存在 if (myMap.count(2) > 0) { std::cout << "Key 2 exists." << std::endl; } // 遍历键值对 for (const auto& pair : myMap) { std::cout << pair.first << ": " << pair.second << std::endl; } // 删除键值对 myMap.erase(3); return 0; }
bitset
bitset可看作一个多位二进制，每8位占用一个字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。在估算程序运行的时间时，我们一般以32位整数的运算次数位基准，因此n位bitset执行一次位运算的复杂度可视为n/32，效率较高
bitset声明时可初始化，可用unsigned或string型来赋值。当用unsing long值作为bitset对象的初始值时，该值将转化为二进制的位模式。 而bitset对象中的位集作为这种位模式的副本。如果bitset类型长度大于unsigned long值的二进制位数，则其余的高阶位置为0；如果bitet类型长度小于unsigned long值的二进制位数，则只使用unsigned值中的低阶位，超过bitet类型长度的高阶位将被丢弃。
操作符
~s : 返回对bitset s按位取反的结果
&，|，^ : 返回丢两个位数相同的bitset执行按位与、或、异或运算的结果
“>>”,“<<”: 返回把一个bitset右移、左移若干位的结果
==,!= : 比较两个bitset代表的二进制数是否相等
bitset支持[ ]操作符，bitset[i]表示二进制的第i位，可以赋值或取值。
//头文件 #include<bitset> //声明/初始化 bitset<n> s; //表示一个n位的二进制数，每位都是0 bitset<n> s(m) //表示一个n位的二进制数，位m的二进制表示 string s; bitset<n> s(str) //将string行转化位bitset型，前提时str为01字符串 bitset<n> s(s, a, b) //将字符串s的下标a开始，长度为b的子字符串与bitset进行转换
bitset和string是反向转化的，但仅限与string型小于bitset位数的部分，超出bitset位数的部分将被抛弃，在bitset位数内，string反向转换位bitset型。
bitset与整型数转换时,bitset从第0位开始存储整型数二进制下的最低位,当整型数的二进制位数超过bitset位数时,超出部分将不会被读进。
遇到整型数或者string型转bitset型时,当整型数二进制或string长度小于bitset时,bitset的高阶补0。
举个例子：
整型数15,二进制为0100,0001,正常转换为8位bitset型为1000,0010, string型转换同理
但是如果0100,0001转换为4位bitset型则为: 1000,因为bitset是从15的二进制的第0位开始储存
string型的"01000001"转换位4位bitset型则为: 0010,因为bitset是将string的前四位反向读取,而string的后四位抛弃了
常用内置函数
b.any() //b中是否存在为1的二进制位 b.none() //b中不存在置为1的二进制位 b.count() //b中置为1的二进制位的个数 b.size() //b中二进制位的个数 b.test(x) //b中在x处的二进制是否位1？ b.set() //把b中所有二进制位都置为1 b.set(x) //把b中在x处的二进制位置为1 b.reset() //把b中所有二进制位都置为0 b.reset(x) //把b中在x处的二进制位置为0 b.flip() //把b中所有二进制位逐位取反 b.flip(x) //把b中在x处的二进制位取反 b.to_uiong() //用b中同样的二进制位返回一个unsigned long值 cout << b << endl; //直接输出b
srring(字符串)
string字符串，是c++中的一个类，也可以看作是一个字符串容器，可以说是非常好用。它可以直接将两个字符串进行比较。另外其内置函数功能也是十分齐全。
#include<cstring> string str; str.push_back('s');//在末尾添加字符's' str.pop_back();//删除最后一个元素 str.front();//返回第一个元素 str.back();//返回最后一个元素 str.clear();//清空容器 str.empty();//容器为空时返回true,否则返回flase str.erase(3);//删除str[3]~str[n - 1],返回str str.erase(2, 3);//删除str[2]~str[2+3-1] str.erase(str.begin());//删除指向的元素, 返回迭代器, 指向下一元素 str.erase(str.begin(), str.end());//删除区间内的元素, 返回迭代器, 指向下一元素 str.find('s');//返回字符 ‘s’ 在 str 中首次出现的位置 str.find('s', 2);//返回字符 ‘s’ 在 str[2]~str[n-1] 中首次出现的位置 str.find(ch);//返回字符串 ch 在 str 中首次出现的位置 str.find(ch, 4);//返回 ch 在 str[4]~str[n-1] 中首次出现的位置 str.find(ch, 4, 3);//返回 ch[0]~ch[3-1] 在 str[4]~str[n-1] 中首次出现的位置 str.find(str1);//返回 str1 在 str 中首次出现的位置 str.find(str1, 2);//返回 str1 在 str[2]~str[n-1] 中首次出现的位置 str.substr(2);//返回 str[2]~str[n-1], 不对 str 进行操作 str.substr(2,3);//返回 str[2]~str[2+3-1]
stringstream
srd::stringstream 是C++标准库中的一个类，它提供了字符串流的功能，可以将数据以字符串的形式进行输入和输出。std::stringstream 可以将各种类型的数据转换为字符串，并且可以从字符串中提取数据。
#include<iostream> #include<algorithm> #include<sstream> using namespace std; int main(){ //1、创建一个对象，向对象输入字符串，输入字符串后直接进行字符串拼接 stringstream ss; ss << str; ss1 << "fre"; ss3 << "gre"; cout << ss1.str() << edml; //2、创建时使用字符串初始化，进行字符串拼接时，首先把原本的字符串覆盖掉，之后再进行拼接。 stringstream ss(str); //3、输出时需调用str()函数 cout << ss.str() << endl; //4、利用stringstream去除字符串空格，streamstring 默认是以空格来分割字符串 stringstream ss("2 dfjho 43"); cout << ss.str() << endl； string str; while (ss >> str){ cout << str << endl; } //5、利用 streamstring 指定字符分割字符串 string source = "abc,123,<!>"; stringstream ss(source); cout << ss.str() << endl; cout<< endl； string str; while (getline(ss, str, ',')){ cout << str << endl; } } }
std::stringstream还提供了其他一些功能，如clear()函数用于重置字符串流的状态，str()函数用于获取字符串流的内容，以及seekg()和seekp()函数用于设置读写位置。
std::stringstream对于将数据转换为字符串或从字符串中提取数据非常有用，尤其在需要处理字符串形式的数据时。
pair（二元组）
pair的定义和结构
在C++中，pair是一个模板类，用于表示一对值的组合。它位于<utility> 头文件中。
pair类的定义如下：
template<class T1, class T2> struct pair{ T1 first; //第一个值 T2 second; //第二个值 //构造函数 pair(); pair(const T1& x, const T2& y); //比较运算符重载 bool operator == (const pair& rhs) const; bool operator != (const pair& rsh) const; //其他成员函数的特征 ...... }
C++内置二元组，其中包含两个元素，分别是first、second。在比较大小中，以第一元first尾第一关键字，第二元second尾第二关键字。
pair<int> a; //a为int型的二元组 a.first = 1; a.second = 2; pair<int, pair<int, int>> b; b.first = 1; b.second.first = 2; b.second.second = 3;
list
list的定义和结构
list是一种双向链表容器，它是标准模板库STL提供的一种序列容器，list容器以节点（node) 的形式存储元素，并使用指针将这些节点链接在一起，形成一个链表结构。
list容器的特点包括：
- 双向性：每个节点都包含指向前一个节点和后一个节点的指针，因此可以在常数时间内在链表中的任意位置进行插入、删除和访问操作。
- 动态大小：链表的大小可以根据需要动态扩展或收缩，不需要预先 指定容器的大小。
- 不连续存储：链表中的节点可以在内存中的任意位置分布，不要求连续存储，因此插入和删除操作不会导致元素的移动
list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素，包括插入、删除、访问、反转等操作。可以使用迭代器来遍历链表中的元素。
展示list容器
#include<iostream> #include<list> using namespace std; int main(){ list<int> myList; //在链表尾部插入元素 myList.push_back(1); myList.push_back(2); myList.push_back(3); //在链表头部插入元素 myList.push_front(0); //遍历链表并输出元素 for(int num : myList){ cout << num << " "; } cout << endl; return 0; }
list<int> myList; myList.push_back(); //将元素插入到链表的末尾 myList.push_front(); //将元素插入到链表的开头 myList.pop_back(); //移除链表末尾的元素 myList.pop_front(); //移除链表开头的元素 myList.size(); //返回链表中元素的个数 myList.empty(); //检查链表是否为空 myList.clear(); //清空链表的所有元素 myList.front(); //返回链表中第一个元素的引用 myList.back(); //返回链表中最后一个元素的引用 myList.begin(); //返回指向链表第一个元素的迭代器 myList.end(); //返回指向链表末尾的下一个位置的迭代器 myList.insert(); //在指定位置之前插入一个或多个元素 myList.erase(); //从链表中移除指定位置的一个或多个元素
- 代码示例：
#include<bits/stdc++.h> using namespace std; int main() { //创建一个List<int> 对象myList list<int> myList; //向myList尾部添加元素 for(int i = 1; i <= 5; i++) { myList.push_back(i); } //从头到尾输出myList中的元素 for(const auto &i : myList) cout << i << " "; cout << endl; //将myList中的元素反转 reverse(myList.begin(), myList.end()); for(const auto &i : myList) cout << i << " "; cour << endl; //在第一个元素的后一个位置加上元素0 myList.insert(++myList.begin(), 0); for(const auto &i : myList) cout << i << " "; cout << endl; myList.erase(++ ++ myList.begin(), --myList.end()); //输出myList的大小 cout << myList.size() << "\n"; //从头到位输出myList中的元素 for(const auto &i : myList) cout << i << " "; cout << "\n"; return 0; }
- 结果
1 2 3 4 5 5 4 3 2 1 5 0 4 3 2 1 链表大小为：3 5 0
二分查找函数
lower_bound()
lower_bound() 函数定义在头文件中，其语法格式有 2 种，分别为：
//在 [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);
其中，first 和 last 都为正向迭代器，[first, last) 用于指定函数的作用范围；val 用于指定目标元素；comp 用于自定义比较规则，此参数可以接收一个包含 2 个形参（第二个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。
实际上，第一种语法格式也设定有比较规则，只不过此规则无法改变，即使用 < 小于号比较 [first, last) 区域内某些元素和 val 的大小，直至找到一个不小于 val 的元素。这也意味着，如果使用第一种语法格式，则 [first,last) 范围的元素类型必须支持 < 运算符。
此外，该函数还会返回一个正向迭代器，当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。
upper_bound()
pper_bound() 函数定义在头文件中，用于在指定范围内查找大于目标值的第一个元素。该函数的语法格式有 2 种，分别是：
//查找[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);
