数据结构之STL篇

校赛中关于stl的一点点收获：

1.数字全排列问题：（输出全排列

stl的用法：

#include <bits/stdc++.h>
using namespace std;
const int maxn =1e6+5;
int a[maxn];
int main ()
{
    int n,i,j,k;
    cin>>n;
    for (i=1;i<=n;i++)
        a[i-1]=i;
     do
     {
         for (i=0;i<n;i++)
            cout<<a[i];
         cout<<endl;

     }while(next_permutation(a,a+n));
    return 0;
}

算法的详细解释(推荐)：全排列

---

堆排序：建堆，与堆排序

1、创建堆make_heap

2、元素入堆push_heap（默认插入最后一个元素）

3、元素出堆pop_heap（与push_heap一样，pop_heap必须对堆操作才有意义）
4堆排序sort_heap

make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());

推荐习题: L2-012

/***
 这道题没有得到全部的得分点,由于但是利用stl的make_heap建堆的使用也是可以的了.
 PS: 感觉自己可能是建堆过程有错误,没有考虑特殊情况.
***/
#include <bits/stdc++.h>
using namespace std;
int a[200000];
int n,m;
inline int get_pos(int x)
{
    return distance(a,find(a,a+n,x));
}
int main ()
{
    string str;
    string temp ;

    int i,j,k;
    cin>>n>>m;

    for (i=0;i<n;i++)
    {

        cin>>a[i];
        make_heap(a,a+i+1,greater<int>() );

    }
//    for (i=0;i<n;i++)
//        cout<<a[i]<<" ";
//    cout<<endl;
    getchar();
    while (m--)
    {
        temp="";
        stringstream ss;
        getline(cin,str);
        int len =str.length();
        if (str[len-1]=='t')
        {

            for (i=0;i<len;i++)
            {
                if(str[i]==' ')
                    break;
                temp+=str[i];
            }
            int ret;
            ss<<temp;
            ss>>ret;
            if (ret==a[0])
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
        else if (str[len-1]=='s')
        {
            int x,y;
            for (i=0;i<len;i++)
            {
                if (str[i]==' ')
                    break;
                temp+=str[i];
            }
            ss<<temp;
            ss>>x;
            ss.clear();
            temp="";
            i++;
            for (;i<len;i++)
            {
            if (str[i]>='0'&&str[i]<='9')
                temp+=str[i];
            }
            ss<<temp;
            ss>>y;
            ss.clear();
            int pos_x=get_pos(x);
            int pos_y=get_pos(y);
            if ((pos_x+1)/2==(pos_y+1)/2)
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
        else
        {
            bool yes=0;
            for (i=0;i<len;i++)
                if (str[i]=='p')
            {
                yes=1;
                break;
            }

            int x, y;
                for (i=0;i<len;i++)
                if (str[i]==' ')
                    break;
                else
                    temp+=str[i];
                ss<<temp;
                ss>>x;
                ss.clear();
                temp="";
                i++;
                for (;i<len;i++)
                if (str[i]>='0'&&str[i]<='9')
                    temp+=str[i];
                ss<<temp;
                ss>>y;
                ss.clear();
                int pos_x=get_pos(x);
                int pos_y=get_pos(y);
            if (yes)
            {
                if (a[pos_x*2+1]==a[pos_y]||a[pos_x*2+2]==a[pos_y])
                    cout<<"T"<<endl;
                else
                    cout<<"F"<<endl;
            }
            else
            {
                if (a[pos_y*2+1]==a[pos_x]||a[pos_y*2+2]==a[pos_x])
                    cout<<"T"<<endl;
                else
                    cout<<"F"<<endl;
            }

        }
    }
    return 0;

}

stl Map 键值对:

map[key]=values
map.find[key] 查找函数
Lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器）
Upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器)
map.erase(key) 删除指定元素
map.clear() 清空map

其他常见的stl函数,模板(读者自行百度):

1.sort(),排序
2.set  集合 (实现方式是红黑树,一种平衡二叉树的变形,详情可去爱课程上搜寻查找上海交大的相关课程学习(为是么不说出来,---我忘记了))
3. lower_bound 二分查找,返回值是地址信息

最后一句:

如果你打算从事C++开发或者ACM学习竞赛,STL是你必须要过的一个知识点,希望你可以好好努力,加油!

注意:

以上内容，作者一字一句码出来的，纯属不易，欢迎大家转载，转载是还请您表明出处。另外如果我有侵权行为，请在下方留言，确认后我会及时撤销相应内容，谢谢大家！