C++的STL学习笔记-阿里云开发者社区

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;
}

程序输出结果：

第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常用函数

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);

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++的STL学习笔记