万能头

#include<bits/stdc++.h>

c++常用

1.大根堆和小根堆

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

int main()
{
    priority_queue<int, vector<int>, greater<int>> q;//小根堆 堆顶元素最小
    //定义成大根堆的方式：priority_queue<int, vector<int>, less<int>> q;  //堆顶元素最大
    q.push(1);
    q.push(10);
    q.push(89);
    //遍历 top()取出堆顶元素 pop()删除堆顶元素
    while(!q.empty())
    {
        cout << q.top() << endl;
        q.pop();
    }

    return 0;
}

2.vector快速查找 底层是数组 不提供sort函数

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

int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(9);
    v.push_back(6);
    v.push_back(4);
    sort(v.begin(),v.end());//algorithm的sort函数  从小到大
    sort(v.begin(),v.end(),greater<int>());//从大到小
    v.pop_back();
    cout << v.size() << endl;
    cout << v.at(1) << endl; //返回某个位置的元素
    cout << "----------------" << endl;
    for(auto it = v.begin(); it!=v.end();++it)
    cout << *it <<endl;
    cout << "----------------" << endl;
    //反向遍历
    for(auto it = v.rbegin(); it!=v.rend();++it)
    cout << *it <<endl;
    cout << "----------------" << endl;
    //for遍历
    for(auto i:v)
    {
        cout << i << endl;
    }
    return 0;
}

3.List List函数类似 底层是链表 快速插入和删除 提供了sort函数

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

int main()
{
    list<int> l;
    l.push_back(4);
    l.push_back(2);
    l.push_back(8);
    l.sort();
    l.sort(greater<int>());//降序
    for(auto it = l.begin(); it != l.end(); ++it)
    cout << *it << endl;
}

4.queue先进先出 所以pop是删除队首元素

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int main()
{
    queue<int> q;
    q.push(1);
    q.push(9);
    q.push(10);
    //1 9 10
    cout << q.back() << endl;//返回最后一个元素
    cout << q.size() << endl;
    while(!q.empty())
    {
        cout << q.front() << endl;
        q.pop();//删除第一个元素
    }
    return 0;
}

5.栈的函数与queue类似 但是是先进后出

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int main()
{
    stack<int> sk;
    sk.push(1);
    sk.push(2);
    sk.push(3);
    sk.push(6);//在栈顶增加元素 6 3 2 1
    cout << sk.size() << endl;
    while(!sk.empty())
    {
        cout << sk.top() << endl; //输出6 3 2 1
        sk.pop();
    }

    return 0;
}

6.set map unordered_set unordered_map

set
map
unordered_set
unordered_map

1. set unordered_set

set：

• set 是一个有序的集合容器，其中的元素是唯一的。
• 元素按照严格弱序（Strict Weak Ordering）排序，默认情况下按照升序排列。
• 插入、删除和查找操作的时间复杂度为 O(log n)。
• set支持存pair set<PII>

unordered_set：

• unordered_set 是一个无序的集合容器，其中的元素是唯一的。
• 元素存储在哈希表中，插入、删除和查找操作的平均时间复杂度为 O(1)。
• 不保证元素的顺序。
• unordered_set 不支持存pair

 insert()  插入一个数
 find()  查找一个数  返回值是一个迭代器，成功返回迭代器指向要查找的元素，失败返回的迭代器指向end
 count()  返回某一个数的个数 ,只能是0或1
 erase()
 (1) 输入是一个数x，删除所有x   O(k + logn)
 (2) 输入一个迭代器，删除这个迭代器
  lower_bound()/upper_bound()
  lower_bound(x)  返回大于等于x的最小的数的迭代器
  upper_bound(x)  返回大于x的最小的数的迭代器

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<set>
using namespace std;

int main()
{
    //unordered_set 无序集合
    unordered_set<int> us;
    us.insert(12);
    us.insert(98);
    us.insert(1);
    us.insert(3);
    us.insert(1);
    cout << "count(12): " << us.count(12) << endl; //count返回出现次数
    cout << "*find()98: " << *us.find(98) << endl; //find返回的是迭代器
    cout << "us.erase(us.begin()): " << *us.erase(us.begin()) << endl; //删除成功返回迭代器
    //遍历 无序的
    for(auto i : us)
    {
        cout << i << ' ';
    }
    cout << endl << "-------------" << endl;
    cout << "us.erase(3); " << us.erase(3) << endl; //删除成功返回1
    cout << "us.erase(2); " << us.erase(2) << endl; //删除失败返回0

    set<int> st;
    st.insert(12);
    st.insert(98);
    st.insert(1);
    st.insert(199);

    //从小到大排序的
    for(auto i : st)
    {
        cout << i << ' ';
    }
    cout << endl << "-------------";
    return 0;
}

1. map unordered_map

map：

• map 是一种关联容器，存储键-值对，并根据键的顺序进行排序。
• 键是唯一的，值可以重复。
• 元素按照严格弱序（Strict Weak Ordering）排序，默认情况下按照键的升序排列。
• 插入、删除和查找操作的时间复杂度为 O(log n)。
• 支持:map<PII,int> m;

unordered_map：

• unordered_map 是一种关联容器，存储键-值对，并根据键的哈希值进行存储。
• 键是唯一的，值可以重复。
• 元素存储在哈希表中，插入、删除和查找操作的平均时间复杂度为 O(1)。
• 不保证元素的顺序。
• 不支持:unordered_map<PII,int> um;

insert()  插入的数是一个pair
erase()  输入的参数是pair或者迭代器
count()  返回出现次数 0/1
find()   返回值是一个迭代器，成功返回迭代器指向要查找的元素key，失败返回的迭代器指向end

[]  注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

插入元素
map<int,int> m;
m[1]=3;
m.insert({1,3});

unordered_map<int,int> ump;
for(int i=0;i<n;++i) 
{
    if(!ump.count(a[i]))
     ump[a[i]]=1;
    else ++ump[a[i]];
}

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
using namespace std;

int main()
{
    unordered_map<int,int> ump;
    ump.insert({1,3});
    ump.insert({9,99});
    ump[8] = 88;
    cout << ump[1] << endl;
    cout << ump.count(1) << endl;
    auto it = ump.find(9);
    if(it != ump.end())
    cout << it->first << " : " << it->second << endl;
    return 0;
}