容器

vector

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    //容器1:vector
    //vector可以随开随用,下面的操作类似于二维数组
    //vector<int> vec1[100];
    vector<int> vec;
    int n, t;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        //从尾部插入t
        vec.push_back(t);
    }
  
    //正序排序
    sort(vec.begin(),vec.end());
    //倒序排序
    //reverse(vec.begin(),vec.end());
  
    //正序遍历
    //迭代器遍历
    vector<int>::iterator it;
    //begin返回第一个元素的迭代器
    //end返回最后一个元素的迭代器
    for(it = vec.begin(); it != vec.end(); it++)
    {
        cout<<*it<<" ";
    }
    cout<<endl;
  
    //for循环中的auto,可以遍历容器
    for(auto j:vec)
    {
        cout<<j<<" ";
    }
    cout<<endl;
  
    //vector遍历
    for(int i = 0; i < vec.size(); i++)
    {
        cout<<vec[i]<<" ";
    }
    cout<<endl;
  
    //倒序遍历
    vector<int>::reverse_iterator it1;
    //it1可以直接在for循环内使用auto类型
    for(it1 = vec.rbegin(); it1 != vec.rend(); it1++)
    {
        cout<<*it1<<" ";
    }
    cout<<endl;
    for(int i = vec.size() - 1; i >=0; i--)
    {
        cout<<vec[i]<<" ";
    }
    cout<<endl;
  
    //按值删除vec中的元素
    for(auto it = vec.begin(); it != vec.end();)
    {
        if(*it == 4)
        {
            it = vec.erase(it);
        }
        else
        {
            it++;
        }
    }
    for(auto j:vec)
    {
        cout<<j<<" ";
    }
    cout<<endl;
  
    //删除尾部的元素
    vec.pop_back();
  
    if(vec.size())
    {
        //返回第一个元素
        vec.front();
        //返回最后一个元素
        vec.back();
    }
  
    //清空vec
    vec.clear();
    return 0;
}

string

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    //容器2:string
    string a, b;
    cin>>a;
    //在容器尾部插入元素
    a.push_back('xxxxxx');
  
    //排序
    sort(a.begin(), a.end());
    cout<<a<<endl;
    //在容器尾部删除元素
    a.pop_back();
    cout<<a<<endl;
    //返回找到第一个b的索引
    cout<<a.find('b')<<endl;
    //从3开始往后截取5个字符,不会越界
    cout<<a.substr(3,5)<<endl;
  
    return 0;
}

pair

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int main()
{
    //容器3:pair 
    //关键字 关键值
    //基础用法
//  pair<char, string> a, b;
//  char t;
//  string s;
//  cin>>t>>s;
//  a = {t, s};
//  
//  cout<<a.first<<" "<<a.second;

    //别名用法
    p p1 = p(1, 3);
    p p2 = p(2, 2);
    p p3 = p(0, -2);
  
    vector<p> vec;
    vec.push_back(p1);
    vec.push_back(p2);
    vec.push_back(p3);
  
    //pair排序
    //pair默认是先对第一个关键字从小到大排序
    //如果第一关键字相同，在对第二关键字从小到大排序
    sort(vec.begin(), vec.end());
    for(auto i : vec)
    {
        cout<<i.first<<" "<<i.second<<endl;
    }
    return 0;
}

stack

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    //容器4:stack 栈(先进后出)
    stack<int> sta;
    int n, t;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        //入栈
        sta.push(t);
    }
    cout<<sta.top()<<endl;
    //出栈
    sta.pop();
    cout<<sta.top()<<endl;
  
    //用数组模拟栈，输出后可以保留栈的数据
//  int z[100];
//  int n,t;
//  int tt = 0;
//  cin>>n;
//  //模拟进栈
//  for(int i = 0; i < n; i++)
//  {
//      cin>>t;
//      z[tt++] = t;
//  }
//  //模拟出栈（不会真的出栈）
//  for(int i = tt - 1; i >= 0; i--)
//  {
//      cout<<z[i]<<endl;
//  }
  
    return 0;
}

queue

#include <iostream>
#include <queue>

using namespace std;
int main()
{
    //容器5:queue(先进先出)
//  queue<int> q;
//  int n,t;
//  cin>>n;
//  for(int i = 0; i < n; i++)
//  {
//      cin>>t;
//      q.push(t);
//  }
//  while(q.size())
//  {
//      //返回队头元素和队尾元素
//      cout<<q.front()<<" "<<q.back()<<endl;
//      q.pop();
//  }
    //数组模拟queue
    int z[100];
    int n, t;
    int hh = 0, tt = 0;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        z[tt++] = t;
    }
    while(hh < tt)
    {
        cout<<z[hh++]<<endl;
    }
  
    return 0;
}

deque

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    //容器6:deque 双端队列
    deque <int> q;
    int t = 0;
    q.push_back(t);
    q.push_front(t);
    q.pop_back();
    q.pop_front();
    return 0;
}

priorty_queue

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    //容器7:priorty_queue 优先队列(堆)
    //自动排序,从大到小,类似于大根堆,vector为默认的存放容器
    priority_queue<int, vector<int>, less<>> q; 
    //类似小根堆
    priority_queue<int, vector<int>, greater<>> q1; 
    int n, t;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        q.push(t);
    }
    while(q.size())
    {
        cout<<q.top()<<endl;
        q.pop();
    }
    return 0;
}

set

#include <iostream>
#include <set>
using namespace std;
int main()
{
    //容器8:set 红黑树实现
    //不存在重复的数据
    //正序排序
    set<int> se;
    int n,t;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        //插入
        se.insert(t);
    }
    //迭代器遍历
    set<int>::iterator it;
    for(it = se.begin(); it != se.end(); it++)
    {
        cout<<*it<<" ";
    }
  
    cout<<endl;
  
    //for循环中的auto遍历
    for(auto j : se)
    {
        cout<<j<<" ";
    }
  
    cout<<endl;
  
    //倒序遍历
    set<int>::reverse_iterator it1;
    for(it1 = se.rbegin(); it1 != se.rend(); it1++)
    {
        cout<<*it1<<" ";
    }
  
    cout<<endl;
  
    //查找3 如果查找不到会返回se.end()
    //用法：可以通过j++ j--获取比j大一位或者小一位的数
    auto j = se.find(3);
    if(j == se.end())
    {
        cout<<"did not find"<<endl;
    }
    else
    {
        cout<<*j<<endl;
    }
  
    //返回>=3的第一个数(二分查找)
    //要求是有序数组,不存在这个数则返回end()
    j = se.lower_bound(3);
    //返回>3的第一个数
    j = se.upper_bound(3);
  
    //删除指定元素
    //set可以直接删除值
    //vector只能通过指针删除
    se.erase(3);
    for(auto it = se.begin(); it != se.end();)
    {
        if(*it == 4)
        {
            it = se.erase(it);
        }
        else
        {
            it++;
        }
    }
    for(auto j : se)
    {
        cout<<j<<" ";
    }
    //返回1出现的次数
    se.count(1);
  
    //清空set
    se.clear();
  
    return 0;
}

map

#include <iostream>
#include <map>
using namespace std;
int main()
{
    //容器9:map 红黑树实现
    //和set类似但是维护的是pair类型
    //不存在重复的数据
    //根据第一关键字正序排序
    map<int,int> mp;
    int n, t, s;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t>>s;
        mp[t] = s;
    }
    //用法:记录同一个值出现的次数
//  for(int i = 0; i < n; i++)
//  {
//      cin>>t;
//      mp[t]++;
//  }
  
    //插入 两种方法等价
    //mp.insert({1,2});
    //mp[1] = 2;
  
    //正序遍历
    map<int,int>::iterator it;
    for(it = mp.begin(); it != mp.end(); it++)
    {
        cout<<(*it).first<<" "<<(*it).second<<endl;
    }
  
    for(auto j : mp)
    {
        cout<<j.first<<" "<<j.second<<endl;
    }
  
    //删除指定元素
    //map可以直接根据对应关键字删除
    mp.erase(3);
  
    //返回1作为关键字出现的次数
    mp.count(1);
  
    return 0;
}

multiset

#include <iostream>
#include <set>
using namespace std;
int main()
{
    //容器10:multiset  红黑树实现
    //可以存放重复的数据 
    //自动进行正序排序
    multiset<int> se;
    int n, t;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t;
        se.insert(t);
    }
    //删除指定元素
    se.erase(2);
    for(auto it = se.begin(); it != se.end();)
    {
        if(*it == 3)
        {
            it = se.erase(it);
        }
        else
        {
            it++;
        }
    }
  
    //正序遍历
    for(auto j : se)
    {
        cout<<j<<endl;
    }
    return 0;
}

multimap

#include <iostream>
#include <map>
using namespace std;
int main()
{
    //容器11:multimap  红黑树实现
    //和set类似但是维护的是pair类型
    //可以存放重复的数据 
    //因为数据可能重复 所以不能使用mp[t] = s这种插入方法
    //根据第一关键字正序排序
    multimap<int,int> mp;
    int n, t, s;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>t>>s;
        mp.insert({t, s});
    }
  
    //这样会删除所有的以3位关键字的元素
    mp.erase(3);
  
    //删除指定的关键值和关键字组成的元素
    for(auto it = mp.begin(); it != mp.end();)
    {
        if((*it).first == 3 && (*it).second == 2)
        {
            it = mp.erase(it);
        }
        else
        {
            it++;   
        }
    }
  
    for(auto j : mp)
    {
        cout<<j.first<<" "<<j.second<<endl;
    }
    return 0;
}

hashmap、hashset

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main()
{
    //哈希表
    //容器12:hashset
    //容器13:hashmap
    //无自动排序，有去重，支持 O(1) 时间查找元素是否存在
    //map、set使用红黑树为 O(logn)
  
    unordered_map<int, int> ump;
    unordered_set<int> ums;

    ump.insert({ 1, 2 });
    ump[1] = 2;
    ump[2] = 3;
  
    ums.insert(3);
    ums.insert(4);

    for (auto j : ump)
    {
        cout<<j.first<<" "<<j.second<<endl;
    }
  
    cout<<endl;
  
    for (auto j : ums)
    {
        cout << j << endl;
    }
    cout<<endl;
  
    //查找元素是否存在，存在就返回true，否则返回false
    bool t = ump.count(3);
    bool g = ums.count(1);
    cout<<t<<g;
    return 0;
}

函数

unique

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> vec = {3,3,4,4,5,5,6,7,7,4};
    sort(vec.begin(), vec.end());
    for(auto j : vec)
    {
        cout<<j<<" ";
    }
    cout<<endl;
    //将重复的数字堆在数组有序数组后面
    //返回重复的第一个元素
    //通过erase删除后面重复的元素
    vec.erase(unique(vec.begin(), vec.end()),vec.end());
    for(auto j : vec)
    {
        cout<<j<<" ";
    }
  
    cout<<endl;
    //对数组进行去重
    int a[200] = {0,1,2,2,2,3,0,5,7,1};
    sort(a, a+10);
    int n = unique(a, a+10) - a;
    for(int i = 0; i < n; i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

next_permutation

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    //时间复杂度比较高 最好只处理比较小的数组
  
    //next_permutation 从小到大全排列
    //如果要求排列所有情况 需要一组升序的元素
    int a[] = {1,2,3,4};
    do
    {
        for(int i = 0; i < 4; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }while(next_permutation(a, a+4));
    cout<<"-----------------------"<<endl;
    for(int i = 0; i < 4; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    reverse(a,a+4);
    for(int i = 0; i < 4; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl<<"-----------------------"<<endl;
  
    //prev_permutation 从大到小全排列
    do
    {
        for(int i = 0; i < 4; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }while(prev_permutation(a, a+4));
    return 0;
}

lower_bound

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    //用的是二分查找的方法
    //区间是前闭后开
    //返回>=key的值 需要是一个有序数组
    //找不到的话会返回vec.end() 或者比数组范围更大1的位置
    int a[] = {1,2,3,4,5,6};
    int t = lower_bound(a, a+6, 200) - a;
    cout<<t<<endl;
    vector<int> vec = {1,2,3,4,5,6};
    int s = lower_bound(vec.begin(),vec.end(),10) - vec.begin();
    cout<<s<<endl;
  
    return 0;
}