C++ 基础知识:输入输出以及std容器算法

淡淡的烟草味﹌ 2022-09-09 06:16 121阅读 0赞

### 文章目录 ###

*  1. C++的输入输出 \`\#include \`
 *   *  1.1 输入输出的定义
     *  1.2 输入输出重定向
     *   *  a 输出重定向
         *  b 输入重定向
         *  c 流操作算子
     *  1.3 getline()读取一行的问题
     *  1.4 输入字符串解析各种数据
     *   *  a 字符串分割方法
         *  b. 字符串转int类型
         *  c. 方法2,3的实现 字符串直接提取数组
         *  d. 方法1 字符串提取二维数组
 *  2. 基础容器 vector和list
 *   *  2.1 vector和list底层逻辑以及区别
     *  2.2 vector基础语法 \`\#include \`
     *   *  a. vector增删改查
         *  b. 二维vector的相关方法
     *  2.3 list的基础语法
 *  3. 基础容器set和map以及unordered\_set和unordered\_map
 *   *  3.1 \`map/set\`和\`unordered\_map/unordered\_set\`的底层逻辑以及区别
     *  map的重要方法
 *  4. 基础容器queue和stack
 *   *  4.1 stack
     *  4.2 \[使用栈实现队列(两个栈转移)\](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
     *  4.3 \[使用队列实现栈 (一个队列翻滚)\](https://leetcode-cn.com/problems/implement-stack-using-queues/)
 *  5. 基础容器 string
 *  本文涉及到的头文件

之所以会有这篇文章, 是因为C++开发在笔试的时候, 需要手动处理数据, 但是C++又没有像是java, python那样自带的`split函数`或者`re包`或者`eval函数`可以直接提取输入的数据变成想要的格式, 因此经过了一大轮的洗礼, 我总结了下面的输入处理方法以及常用的std容器使用方法, 作为C++入门的教程

# 1. C++的输入输出 `#include <iostream>` #

## 1.1 输入输出的定义 ##

<table> 
 <thead> 
  <tr> 
   <th><code>cin</code></th> 
   <th>标准输入流</th> 
   <th>键盘读取数据</th> 
   <th>可被重定向(文件读取)</th> 
   <th><code>freopen("input.dat", "r", stdin);</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>cout</code></td> 
   <td>标准输出流</td> 
   <td>屏幕输出(缓存)</td> 
   <td>可被重定向(文件写入)</td> 
   <td><code>freopen("test.txt", "w", stdout);</code></td> 
  </tr> 
  <tr> 
   <td><code>clog</code></td> 
   <td>标准错误流</td> 
   <td>缓存输出</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><code>cerr</code></td> 
   <td>标准错误流</td> 
   <td>不缓存输出</td> 
   <td>用于迅速输出出错信息</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

**cerr和clog的区别在于**：cerr不适用缓冲区，直接向显示器输出信息；而输出到clog中的信息会先被存放到缓冲区，缓冲区满或者刷新时才输出到屏幕。

ostream类的无参构造函数和复制构造函数都是私有的，因此在程序中一般无法定义ostream类的对象，唯一能用的ostream类的对象就是cout。

cout可以被重定向，而cerr不能。所谓重定向，就是将输入的源或输出的目的地改变。例如，cout本来是输出到屏幕的，但是经过重定向，本该输出到屏幕上的东西就可以被输出到文件中。

## 1.2 输入输出重定向 ##

### a 输出重定向 ###

`freopen(file, mode, stdout)`是个标准库函数，第二个参数`mode=w写/a追加/r读`，第三个参数代表标准输出。该语句的作用是将标准输出重定向为test.txt文件。重定向之后，所有对cout的输出都不再出现在屏幕上，而是在test.txt文件中。

#include <iostream>
    using namespace std;
    int main()
    { 
        int x,y;
        cin >> x >> y;
        freopen("test.txt", "w", stdout);  //将标准输出重定向到 test.txt文件
        if( y == 0 )  //除数为0则输出错误信息
            cerr << "error 分母不能为0" << endl;
        else
            cout << x /y ;
        return 0;
    }

### b 输入重定向 ###

在文件test.py中输入`23 24回车`  
运行下面代码直接就可以输入23 24

int main(int argc, char const *argv[]){ 
    	// 表示将文件内容读出到cin中, 所以下面的所有cin都是使用test.py文件中的数据, 不用在屏幕上重新打字了
        freopen("test.py", "r", stdin);
        int a, b;
        cin >> a >>b;
        cout << a << " "<< b <<endl;
        return 0;
    }

### c 流操作算子 ###

比如将十进制的整形转成8进制数等操作

void test(){ 
    	int a = 125;
    	cout<< hex << a <<endl; // 16进制输出 
    	cout<< oct << a <<endl; // 8进制输出
    	
    	double b = 3.1415926;
    	cout<< fixed << b <<endl; // 普通小数
    	cout<< scientific << b <<endl; // 科学计数法输出
    }
    /* 7d 175 3.141593 3.141593e+00 */

## 1.3 getline()读取一行的问题 ##

`cin>>str`读字符串由于**遇到空格会终止**，有时候为了读取一行不得不使用`getline(cin, s)`  
但`getline(cin, s)`只能读取一行，但在`getline(cin, s)`前调用了`cin>>str`的情况下，读取会跳过一行。  
为了解决上述问题, 可以在`getline(cin, s)`上面加入一行 `cin.ignore(numeric_limits <streamsize> ::max(), '\n');`

/* test.py 的文件内容 23 24 def handle(a = 256, b = 64): if a==0 : */
    int main(int argc, char const *argv[]){ 
        freopen("test.py", "r", stdin);
        int a, b;
        cin >> a >>b;
        cout << a << " "<< b <<endl;
        string s;
    /* 如果不加下面这行 输出的就是: 23 24 def handle(a = 256, b = 64): 加了输出的是: 23 24 def handle(a = 256, b = 64): if a==0 : */
        cin.ignore(numeric_limits <streamsize> ::max(), '\n'); // 重点中的重点
        getline(cin, s); 
        cout<< s <<endl;
        getline(cin, s);
        cout<< s <<endl;
        return 0;
    }

## 1.4 输入字符串解析各种数据 ##

由于输入的数据基本都是按照字符串来进行解析的,  
比如输入一个数组: `[12,32,43,5,6]`  
其实输入的应该是`vector<int> a = {12,32,43,5,6}`  
**有两种方式解决上面的`input->vector`**

1.  方法1: 如果输入规范, 则将上面字符串`str = str[1:-1]` 去掉左右两个括号, 在通过`,` 分割, 在利用`atoi(s.c_str())` 将`s` 转成int
2.  方法2: 如果上述输出不规范, 将上面非\[0-9, +, -, .\]转化为空格, `"[12,32,43,5,6]"` → `"12 32 43 5 6"`; 然后在利用空格分割, 在转int型
3.  方法3: 得到`"12 32 43 5 6"`可以利用`sstream`流直接转换

下面是三种方式的具体实现方法:

### a 字符串分割方法 ###

// s="fasjlg,hgjlsd,hdsjlhj,sardehjs,,sdhr" --> {"fasjlg", "hgjlsd"}
    vector<string> split(string s,char ch){ 
        int start=0;
        int len=0;
        vector<string> ret;
        for(int i=0;i<s.size();i++){ 
            if(s[i]==ch){ 
                ret.push_back(s.substr(start,len));
                start=i+1;
                len=0;
            }
            else len++;
        }
        if(start<s.size()) ret.push_back(s.substr(start,len));
        return ret;
    }

### b. 字符串转int类型 ###

int main(int argc, char const *argv[]){ 
        string s="123";
        int v=atoi(s.c_str()); // const char *c_str();表示返回正规字符串指针, 内容与string一致
        printf("result v=%d\n",v);
        return 0;
    }

### c. 方法2,3的实现 字符串直接提取数组 ###

// s="[[2,3], [23,43.5], [2,3,432]]" --> {2,3,23,43,2,3,432}
    vector<int> getV(string str1){ 
        for(int i=0; i<str1.size(); i++){ 
            if(str1[i]-'0' > 9 || str1[i]-'0' < 0){ 
                if(str1[i] != '-' && str1[i] != '.')
                    str1[i] = ' ';
            }
        }
        istringstream s1(str1);
        int num;
        vector<int> nums;
        while(s1 >> num){ 
            nums.push_back(num);
        } 
        print_v(nums);
        return nums;
    }

### d. 方法1 字符串提取二维数组 ###

// s="[[2,3], [23,43.5], [2,3,432]]" -->{ {2,3}, {23,43}, {2,3,432}}
    vector<vector<int>> getVV(string s="[[2,3], [23,43.5], [2,3,432]]"){ 
        vector<string> vS = split(s.substr(0, s.size()-1), ']');
        vector<vector<int>> ans;
        for(int i=0; i<vS.size(); i++){ 
            ans.push_back(getV(vS[i]));
        }
        print_vv(ans);
        return ans;
    }

# 2. 基础容器 vector和list #

## 2.1 vector和list底层逻辑以及区别 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">Vector</th> 
   <th align="center">List</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">连续存储的容器，动态数组，在堆上分配空间, 两倍容量增长, 顺序内存</td> 
   <td align="center">动态双向链表, 堆上空间, 每删除一个元素会释放一个空间</td> 
  </tr> 
  <tr> 
   <td align="center">访问：O(1)(随机访问);插入:后插快, 中间需要内存拷贝, 内存申请和释放; 删除: 后删快, 中间需要内存拷贝</td> 
   <td align="center">访问: 随机访问差, 只能开头和结尾; 插入和删除快, 常数开销</td> 
  </tr> 
  <tr> 
   <td align="center">适用场景：经常随机访问，且不经常对非尾节点进行插入删除</td> 
   <td align="center">适用于经常插入和删除</td> 
  </tr> 
  <tr> 
   <td align="center">下面是区别</td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">数组</td> 
   <td align="center">双向链表</td> 
  </tr> 
  <tr> 
   <td align="center">支持随机访问</td> 
   <td align="center">不支持随机访问</td> 
  </tr> 
  <tr> 
   <td align="center">顺序内存</td> 
   <td align="center">离散内存</td> 
  </tr> 
  <tr> 
   <td align="center">中间节点插入删除会导致拷贝</td> 
   <td align="center">不会</td> 
  </tr> 
  <tr> 
   <td align="center">一次性分配好内存, 二倍扩容</td> 
   <td align="center">list每次在新节点插入会进行内存申请</td> 
  </tr> 
  <tr> 
   <td align="center">随机访问性能好,插入性能差</td> 
   <td align="center">相反</td> 
  </tr> 
 </tbody> 
</table>

注意: vector在保存对象时, 建议使用指针保存, 这是因为无论指针还是对象在内存中开辟的空间都一样, 但是使用指针时, 就不会内存中开辟连续的巨大空间, 并且随着对象的插入, vector内存如果不够, 需要新开辟空间, 拷贝对象到新的空间, 并且调用对象的析构函数回收上一个空间, 因此会有创建, 拷贝, 和析构的时间浪费;

## 2.2 vector基础语法 `#include <vector>` ##

### a. vector增删改查 ###

#include <algorithm>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    // 打印向量
    void print_vector1(vector<int> b){ 
        for(vector<int>::iterator it=b.begin();it!=b.end();it++)
            cout<<*it<<" ";
        cout<<endl;
    }
    
    void print_vector2(vector<int> &b){ 
        for(const auto&a : b){  // const保证不更改b, &a表示引用b里面的值
            cout<< a <<" ";
        }cout<<endl;
    }
    
    
    // 增加
    void add_item(){ 
        //方法一
        vector<int> a;
        for(int i=0;i<10;i++)
            a.push_back(i);
    
        // 方法二
        int a2[6]={ 1,2,3,4,5,6};
        vector<int> a3;
        vector<int> a4(a2,a2+4);
        for(vector<int>::iterator it=a4.begin(); it<a4.end(); it++)
        a3.push_back(*it);
    
        // 方法三
        // ifstream in("data.txt");
        // vector<int> a;
        // for(int i; in>>i)
        // a.push_back(i);
    }
    
    
    
    int main(int argc, char const *argv[])
    { 
        // vector定义
        vector<int> a0; //a0=[] 定义空的整形元素向量
        vector<int> a1(10); // a1=[0,0,0,0,0,0,0,0] 定义了10个整型元素的向量, 默认=0
        vector<int> a2(10, 1) ; //a2=[1,1,1,1,1,1,1,1,1] 大小为10初值为1的向量a
        vector<int> a3(a2); //a3=[1,1,1,1,1,1,1,1,1] 用b向量来创建a向量，整体复制性赋值
        vector<int> a4 = { 1,2,3,4,5,6,7,8,9}; // a4=[1,2,3,4,5,6,7,8,9]
        vector<int> a5(a4.begin(), a4.begin()+3); // a5=[1,2,3]
        int i1[7]={ 1,2,3,4,5,9,8};
        vector<int> a6(i1,i1+7); // a6=[1,2,3,4,5,9,8] 从数组中获得初值
        vector<int> a7;
        a7.assign(a6.begin(), a6.begin()+3); // a7=[1,2,3]
        vector<int> a8; 
        a8.assign(4,2); // a8=[2,2,2,2]
    
    
        // 增加元素
        a0.push_back(1); // a0=[1,]在后面插入一个值1
        a0.insert(a0.begin(), 2); //a0=[2,1], 在a0的头部插入2
        a0.insert(a0.begin()+1,5); //a0=[2,5,1] 在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
        a0.insert(a0.begin()+1,3,7); // a0=[2,7,7,7,5,1]在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
        a0.insert(a0.begin()+1,a1.begin()+3,a1.begin()+6); 
        //a0=[2,0,0,0,7,7,7,5,1]b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8 ，插入元素后为1,4,5,9,2,3,4,5,9,8
        
    
        // 排序 #include <algorithm>
        sort(a6.begin(), a6.end()); // a6=[1,2,3,4,5,8,9]默认从小到大 
        // 元素倒置
        reverse(a6.begin(),a6.end());  // [9,8,5,4,3,2,1]
        // 深拷贝 
        copy(a6.begin(),a6.end(), a1.begin()+2);  
        // a1=[0,0,9,8,5,4,3,2,1,0]
    
        // 查找, 返回位置
        a6.push_back(4); // a6=[9,8,5,4,3,2,1,4]
        if(find(a6.begin(), a6.end(), 4) != a6.end()){ 
            for(vector<int>::iterator it = find(a6.begin(),a6.end(),4); it!=a6.end(); it++){ 
                cout<< "a6中4存在" << *it <<endl;
            }
        }
        if(count(a6.begin(), a6.end(), 2) != 0){ 
            cout<< "a6 存在2" <<endl;
        }
        // 读取数据
        a4.back();//返回a的最后一个元素
        a4.front(); //返回a的第一个元素
        a4.at(1); // 读取index=1的值, 如果没有会抛出异常
        a4.clear(); // a4=[]清空a中的元素
        if(a4.empty()){ 
            cout<< "a4空了" <<endl;
        }
        a4.push_back(4); // a4=[4] 插入一个元素
        a4.pop_back(); // a4=[] 删除a向量的最后一个元素
        a6.erase(a6.begin()+1,a6.begin()+3); // a6=[9,4,3,2,1,4]删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+ 3（不包括它）
        a7.size(); //返回a中元素的个数；
        a7.capacity(); //返回a在内存中总共可以容纳的元素个数
        a7.resize(6); // a7=[[1,2,3,0,0,0]将a的现有元素个数调至10个，多则删，少则补，其值随机
        a7.resize(8,2); // a7 = [1,2,3,0,0,0,2,2]将a的现有元素个数调至10个，多则删，少则补，其值为2
        a7.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才 显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
        // a7=[1,2,3,0,0,0,2,2]
        // a0=[2,0,0,0,7,7,7,5,1]
        a7.swap(a0); // 
        // a7=[2,0,0,0,7,7,7,5,1]
        // a0=[1,2,3,0,0,0,2,2]
        a7==a0; //b为向量，向量的比较操作还有!=,>=,<=,>,<
    
        print_vector1(a1);
        print_vector2(a2);
    
        return 0;
    }

### b. 二维vector的相关方法 ###

#include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    // https://blog.csdn.net/sinat_41852207/article/details/86668954?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control
    int main(int argc, char const *argv[])
    { 
    	// 二维向量初始化
    	vector<vector<int>> v1(5,vector<int>(10,6)); // 5行. 每行10个, 10个6
    	vector<vector<int>> v2 = { { 1,2,3,4}, { 2,3,4,5}}; //两行, 直接赋值
    	
    	int a1[5]={ 1,2,3,5,6};
    	vector<int> i(a1, a1+4); //初始化一维数组, 用a1赋值
    	printf("打印向量:\n");
    	for(auto c : i) cout<< c <<" ";
    	// 二维向量的插入
    	vector<vector<int>> v3;
    	v3.push_back(i); // v3 = { {1,2,3,5}, }
    	i[0]=5;
    	i[1]=4;
    	i[2]=4;
    	i[3]=4;
    	i[4]=4;
    	v3.push_back(i); // v3 = { {1,2,3,5}, {5,4,4,4,4}}
    	
    	// 二维向量的打印
    	cout<<"\n打印二维数组"<<endl;
    	for (int i = 0; i < v1.size(); i++)
    	{ 
    		for (int j = 0; j < v1[0].size(); j++)
    		{ 
    			cout<<v1[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    	cout<<endl;
    	cout<<"hello world"<<endl;
    	return 0;
    }

## 2.3 list的基础语法 ##

跟vector一样

#include <list>
    void test(){ 
        list<int> list1 = { 1,2,3,3 ,3, 3, 3, 4,5,5,5,6,7,8, 2, 2, 2};
        for(list<int>::iterator it=list1.begin(); it!=list1.end(); it++){  // 迭代器打印全部数据
            cout<< *it << " ";
        } cout << endl;
    
        list1.remove(2); // 删除全部的指定元素
        for(auto &a : list1){  cout<< a <<" " ;}cout<< "\n";
    
        list1.remove_if([](int &a){ return a%2==0;});// 删除list中2的倍数
        for(auto &a : list1){  cout<< a <<" " ;}cout<< "\n";
    
        list1.unique(); // 移除连续重复的数据, 只保留一个
        for(auto &a : list1){  cout<< a <<" " ;}cout<< "\n";
    
    
        list1.erase(++list1.begin(), list1.end()); // 删除第二个到最后一个
        for(auto &a : list1){  cout<< a <<" " ;}cout<< "\n";
    }

# 3. 基础容器set和map以及unordered\_set和unordered\_map #

#include<unordered_map>
    #include<map>
    #include<unordered_set>
    #include<set>

## 3.1 `map/set`和`unordered_map/unordered_set`的底层逻辑以及区别 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>map/set</th> 
   <th>unordered_map/unordered_set</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层</td> 
   <td>红黑树</td> 
   <td>哈希表</td> 
  </tr> 
  <tr> 
   <td>有序性</td> 
   <td>自动排序</td> 
   <td>无序, key映射</td> 
  </tr> 
  <tr> 
   <td>查找时间</td> 
   <td>O(logn)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>空间占用率高(保存父子节点关系)</td> 
   <td>空间占用率低</td> 
  </tr> 
 </tbody> 
</table>

**为何不能修改key?**  
由于`map`是`key-value`键值对和`set`是`key`, 因此都无法修改`key`, 因为红黑树底层按照`key`排列,必须保证有序, 如果可以修改`key`, 则需要删除`key`, 调节树平衡, 在插入修改后的`key`, 调节平衡, 将会破坏`map`和`set`的结构;

## map的重要方法 ##

#include<iostream>
    #include<map> // 注意map的key会自动排序, 所以在遇到排序问题时参考
    #include<algorithm>
    #include<vector>
    #include <unordered_map>
    using namespace std;
    // map中 所有元素都是pair
    // pair中 第一个元素为key(键值) 用于索引 第二个元素value(实值)
    // 所有元素都会根据键值自动排序
    // 本质：
    // map /mulmap底层都是二叉树
    // 优点：
    // 可根据key值快速找到value值
    
    // map不允许容器中出现相同的值 
    // mulmap中允许出现重复的值2
    // map大小和交换：
    // .size() //返回容器中元素的数目
    // .empty() //判断容器是否为空
    // .swap(st) //交换两个容器
    // 插入和删除：
    // insert(elem) //容器中插入元素 inseert(pair<int,int> ( , ));
    // clear() //清除所有元素
    // erase(pos) //删除pos迭代器所指的元素 返回下一个迭 代器位置
    // erase(key) 删除键值为key的元素
    
    void map_test(){ 
        // https://blog.csdn.net/tcx1992/article/details/80928790
        // https://blog.csdn.net/sevenjoin/article/details/81937695
        typedef map<int, string> myMap; // 这其实就是将map里面的数据格式给固定下来而已, map<int, string> = myMap
        myMap test;
        //插入
        test.insert(pair<int, string>(3, "a"));
        test.insert(pair<int, string>(4, "b"));
        test.insert(pair<int, string>(5, "c"));
        test.insert(pair<int, string>(8, "d"));
        test.insert(pair<int, string>(50, "e"));
    
        //遍历（二叉搜索树的中序遍历，按照key值递增顺序）
        cout << "遍历" << endl;
    
        // for(auto i : test){ // 将temp里面的每个值, 放到i中, 这个i是新建的
    	// for(auto &i : test){ // 将temp里面的每个值, 软连接到i, 修改i就是在修改temp中的值
    	for(const auto &i : test){  // 将temp里面的每个值, 软连接到i, 禁用修改, 防止在遍历过程中出现改值
            cout << i.second << endl;
        cout << endl;
        auto iter = test.rbegin();//最大的N个数
        for (int i = 0; i < 3; i++)
            cout << iter++->second << endl;
        //查找
        cout << "查找" << endl;
        // 使用find，返回的是被查找元素的位置，没有则返回map.end()。
        auto it = test.find(50); //查找key=50的数据是, find(key)返回的是pair格式, 也就是(50, e), 所以it->second=
        if (it != test.end())
            cout << it->second << endl;
        // 使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0
        cout << test.count(3) << endl;
        //删除
        cout << "删除" << endl;
        if (test.erase(3))
            cout << "delete success" << endl;
        for (auto &i : test)
            cout << i.second << endl;    
    }
    
    void map_test2(){ 
        map<int, string> myMap;  // 创建
        myMap.insert(pair<int, string>(3, "a")); // 插入
        myMap.insert(pair<int, string>(5, "b"));
        myMap.insert(pair<int, string>(50, "d"));
        for (auto &i : myMap) cout <<i.first <<"value="<< i.second<<"; "; cout<<endl;  // 遍历
            
        //返回map最后一个值
        map<int, string>::reverse_iterator iter = myMap.rbegin(); 
        if (iter != myMap.rend()) cout<<"最后一个值是"<<iter->first << "-" << iter->second <<endl;
        // cout<<"最后一个值是"<<myMap.end()->first << "-" << myMap.end()->second <<endl; //这样是错误的, 因为rend()和end()这两个函数只是标记找没找到 不是返回最后一个元素
    
        // 最大的2个数
        auto iter1 = myMap.rbegin();
        for (int i = 0; i < 2; i++)
            cout << iter1++->second << endl;
    
        // 查找find
        auto it = myMap.find(50); //查找key=50的数据是, find(key)返回的是pair格式, 也就是(50, e), 所以it->second=
        if (it != myMap.end()) 
            cout <<it->first << "-"<<it->second << endl;
    
        // 判断存在, 
        cout << "3有" << myMap.count(3) << endl;
    }
    
    int main()
    { 
        // map_test2();
        unordered_map<int, string> map1{ { 1, "hel"}, { 2, "ahskg"}, { 3, "world"}};
        cout<<map1.at(1)<<endl; // 最简单的查找
        // cout<<map1.at(5)<<endl; // 最简单的查找
        return 0;
    }

# 4. 基础容器queue和stack #

## 4.1 stack ##

1.  stack是一种容器适配器，专门用在具有后进先出(LIFO)操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2.  stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3.  stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作： empty：判空操作 back：获取尾部元素操作 push\_back：尾部插入元素操作 pop\_back：尾部删除元素操作
4.  标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。
5.  stack的所有元素进出都必须符合“先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供随机访问功能，也不提供迭代器。

<table> 
 <thead> 
  <tr> 
   <th>函数接口</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>stack()</strong></td> 
   <td>构造空栈</td> 
  </tr> 
  <tr> 
   <td><strong>empty()</strong></td> 
   <td>检测栈是否为空</td> 
  </tr> 
  <tr> 
   <td><strong>top()</strong></td> 
   <td>返回栈顶元素的引用</td> 
  </tr> 
  <tr> 
   <td><strong>size()</strong></td> 
   <td>返回栈中元素个数</td> 
  </tr> 
  <tr> 
   <td><strong>push()</strong></td> 
   <td>将元素val压入stack中</td> 
  </tr> 
  <tr> 
   <td><strong>pop()</strong></td> 
   <td>将stack中尾部的元素弹出</td> 
  </tr> 
 </tbody> 
</table>

## 4.2 [使用栈实现队列(两个栈转移)][Link 1] ##

/* 1. 两个栈实现 2. 入队列: 入第一个栈 3. 出队列: 出第二个栈, 如果第二个栈空了, 将第一个栈数据都入第二个栈, 在出 */
    class MyQueue{ 
    private:
        stack<int> in, out;
        int q_size = 0;
    public:
        void push(int x){ 
            in.push(x);
            q_size++;
        }
        int pop(){ 
            in2out();
            int r = out.top();
            out.pop();
            q_size--;
            return r;
        }
        int peek(){ 
            in2out();
            int r = out.top();
            return r;
        }
        bool empty(){ 
            return q_size==0;
        }
        void in2out(){ 
            if(out.empty()){  // 为空则把in->out
                while(!in.empty()){ 
                    out.push(in.top());
                    in.pop();
                }
            }
        }
    };

## 4.3 [使用队列实现栈 (一个队列翻滚)][Link 2] ##

// 利用队列实现栈
    /* 0. 栈是先入后出 1. 入队: 使用一个队列, 每次新节点都进入到最底层(循环出队到入队n-1次) 2. 出队: 队列的头部直接出 */
    class MyStack{ 
    private:
        queue<int> temp;
    public:
        MyStack() { }
        void push(int x){ 
            temp.push(x);
            for(int i=0; i<temp.size()-1; i++){ 
                temp.push(temp.front());
                temp.pop();
            }
        }
        int pop(){ 
            int r=temp.front();
            temp.pop();
            return r;
        }
        int top(){ 
            return temp.front();
        }
        bool empty(){ 
            return temp.empty();
        }
    };

# 5. 基础容器 string #

#include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <vector>
    #include <sstream> // 为了使用stringsteam
    using namespace std;
    
    string String_test(){ 
    	string str="hello world";
    
    	//直接打印字符串
    	cout<<"str="<<str<<endl; 
    	// printf("%s\n", str); //这里会报错, 需要将string转化为const char*类型
    	const char *p = str.c_str();
    	printf("str=%s\n", p);
    
    	// 求字符串长度:
    	cout<<"字符串长度等于: "<<str.length()<<endl;
    
        // 打印字符串最后一位
        cout<<"字符串最后一位"<<str[str.length()-1]<<endl;
        cout<<"字符串最后一位"<<str.back()<<endl;
    
        // string切片 substr(起始位置, 长度)
        cout<<"切片"<<str.substr(0, 5)<<endl;  
    
    	//比较字符串
    	if (0 == str.compare("hello world")){ 
    		printf("字符串等于hello world\n");
    	}
    
    	// 字符串判断空
    	if(!str.empty()){ 
    		printf("字符串不为空\n");
    	}
    
        // 字符串翻转
        // reverse(str.begin(), str.end()); // algorithm定义
    	// char*、char[]转换为string 
        const char* pszName = "liitdar";
        char pszCamp[] = "alliance";
        string strName = pszName;
        string strCamp = pszCamp;
        cout << "strName is: " << strName << endl;	//strName is: liitdar
        cout << "strCamp is: " << strCamp << endl;	//strCamp is: alliance
    
        // find检测是否存在
    	// size_t find (const string& str, size_t pos = 0) const;
    	// size_t find (const char* s, size_t pos = 0) const;
    	// size_t find (const char* s, size_t pos, size_t n) const;
    	// size_t find (char c, size_t pos = 0) const;
        string str2 = "world";
        size_t son_location = str.find(str2);
        if (son_location != string::npos){  
        	cout<<"找到子串str2, 在str位置是: "<<son_location<<endl; //找到子串str2, 在str位置是: 6
        }
    
        // 插入方法 insert
        str.insert(6, "zjq's "); //hello zjq's world
        str.insert(5, 4, 'a'); //在5的位置, 插入4个a
        cout<<str<<endl;
    
        // int2string stringstream
        int n1 = 1234;
        // n1.str(); // 这肯定不对
        stringstream str3; //注意这里导入头文件<sstream>
        str3 << n1;
        string str4 = str3.str();
        cout<<"将int类型转化为string类型: "<<str4<<endl;
    
        string str5;
        str3 >> str5;
        cout<<str5<<endl; //总之都要将int转化为string类型
    
    
        // 方法2 to_string
        int numb2 = 456;
        string str6;
        str6 = to_string(numb2);    // C++11 标准
        cout << "str6 is: " << str6 << endl; //str6 is: 456
        return str6;
    }
    
    
    int main(int argc, char const *argv[])
    { 
    	string str = String_test();
        cout<<str<<endl;
    	return 0;
    }

# 本文涉及到的头文件 #

#include <algorithm>
    #include <vector>
    #include <list>
    #include <iostream>
    #include <map>
    #include <set>
    #include <unordered_set>
    #include <unordered_map>
    #include <numeric>
    #include <string.h>
    #include <queue>
    #include <stack>

[Link 1]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[Link 2]: https://leetcode-cn.com/problems/implement-stack-using-queues/