c++算法训练—（一）STL库

本文主要是介绍c++算法训练—（一）STL库，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、STL算法库（c++特性）

pair(二元组、元素对）

位于头文件< iostream>中用来表示一个二元组或元素对
1.1 使用pair
定义一个pair对象表示一个平面面坐标点:

pair<double, double> p;
cin >> p.first >> p.second;

2.1排序

int cmp(pair<int,int > a,pair<int ,int > b){
	return a.second<b.second;
}

vector( 类数组 )

vector包含着一系列连续存储的元素，性质和数组十分相似。
访问元素或者在末尾插入元素常数级别，插入元素是线性级别。

要注意的是，vector的尾部元素是

vector<int> ve;
vector<int>::iterator::iter;
iter=ve.end()-1;    //这里一定要减
cout<*ite<<endl;

2.vector的操作

cvec.begin();    //返回第一个元素的迭代器 
vec.end();
vect.empty();
vec.front();    //返回第一个元素
vec.push_back();    //在最后添加一个元素
vec.pop_back();     //移除最后一个元素 

#include<bits/stdc++.h>
using namespace std;

vector<int> vec
int main(){
    vec.push_back(1);       //尾部插入元素
    vec.push_back(2);
    vec.push_back(5);
    
    //迭代器
vector<int>::iterator ite;
for(ite=vec.begin();ite!=vec.end();++ite){
    cout<<*ite<<endl;
} 

//插入元素,在第i+1个元素前面插入a 
vec.insert(vec.begin()+i,a); 
//删除元素
vec.erase(vec.begin()+2);  //删除第三个元素 

vec.size();
vec.clear();

return 0;
}

//vector的元素还可以是结构体，但是结构体一定要定义为全局 
#include<bits/stdc++.h>
using namespace std;
typedef struct rect{
    int id,length,width;
    //对于向量元素是结构体的，可以在结构体内部定义比较函数
    bool operator< (const rect &a)  const
    {
        if(id!=a.id)
            return id<a.id;
        else
        {
            if(length!=a.length)
                return length<a.length;
            else
                return width<a.width;
        }
    }
}Rect;
int main(){
    vector<Rect> vec;
    Rect rect;
    rect.id=1;
    rect.length=2;
    rect.width=3;
    vec.push_back(rect);
    vector<Rect>::iterator it=vec.begin();
    cout<<(*it).id<<(*it).length<<(*it).width<<endl;
return 0;
}

(1) 使用reverse将元素翻转：

reverse(vec.begin(),vec.end());

(2)使用sort排序：需要头文件#include<algorithm>

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).

可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(const int &a,const int &b)
{
    return a>b;
}

调用时sort(vec.begin(),vec.end(),Comp)这样就降序排序。

set

数据存入其中后会自动去重，自带排序。
虽然set自动去重，但是仍然可以用count()求出某一点重复数据的个数 set容器中不允许重复元素,multiset允许重复元素
set在访问元素的时候不能按照下标来访问，只能做到遍历访问。我们想要按照下标来访问set内部的元素，可以把set内部的元素存放在vector里面。

set常用操作：

set<int> s;
set<double> ss;
multiset<int> ms;     //允许重复

set的基本操作:
s.begin()                               //返回指向第一个元素的迭代器
s.clear()                               //清除所有元素
s.count()                               //返回某个值元素的个数
s.empty()                               //如果集合为空,返回true(真)
s.end()                                 //返回指向最后一个元素之后的迭代器,不是最后一个元素
s.erase()                               //删除集合中的元素
s.find()                                //返回一个指向被查找到元素的迭代器
s.insert()                              //在集合中插入元素
s.lower_bound()                         //返回指向大于(或等于)某值的第一个元素的迭代器
s.size()                                //集合中元素的数目
s.swap()                                //交换两个集合变量
s.upper_bound()                         //返回大于某个值元素的迭代器

set<int> s;

s.erase(2);        //删除键值为2的元素
s.clear();

//元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。

set<int>::iterator it;
it=s.find(5);    //查找键值为5的元素
if(it!=s.end())    //找到
   cout<<*it<<endl;
else            //未找到
   cout<<"未找到";


//自定义比较函数
    (1)元素不是结构体：
        例：
        //自定义比较函数myComp,重载“（）”操作符
        struct myComp
        {
            bool operator()(const your_type &a,const your_type &b)
            [
                return a.data-b.data>0;
            }
        }
        set<int,myComp>s;
        ......
        set<int,myComp>::iterator it;
    (2)如果元素是结构体，可以直接将比较函数写在结构体内。
        例：
        struct Info
        {
            string name;
            float score;
            //重载“<”操作符，自定义排序规则
            bool operator < (const Info &a) const
            {
                //按score从大到小排列
                return a.score<score;
            }
        }
3.举例

#include<iostream>
#include<set>
#include<cstdio>
using namespace std;
int main(){
    set<int> s;

    //插入元素
    s.insert(1);
    s.insert(3);
    s.insert(5);
    
    //查找元素
    set<int>::iterator ite;
    
    ite=s.find(1);  //查找键值为1的元素
    if(ite==s.end()) puts("not find");
    else puts("find");
    
    ite=s.find(2);
    if(ite==s.end()) puts("not find");
    else puts("find");
    
    //删除元素
    s.erase(3);
    
    //其他的查找元素的方法
    if(s.count(3)!=0) puts("find");
    else puts("no find");
    
    //遍历所有的元素
    for(ite=s.begin();ite!=s.end();++ite)
        cout<<*ite<<endl;
    
    return 0;



#include<bits/stdc++.h>
using namespace std;
set<int> s;
int main(){
    s.insert(1);
    s.insert(3);
    s.insert(4);
    cout<<*lower_bound(2)<<endl;  //输出3，返回第一个大于等于
    cout<<*lower_bound(3)<<endl;  //输出3
    cout<<*upper_bound(3)<<endl;  //输出4，返回第一个大于
return 0;
}

map(key - value）

map 是一种有序无重复的关联容器。
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。

map的功能
自动建立Key - value的对应。key 和 value可以是任意你需要的类型。

举例

map<string,int> mp;
string ss;
for(int i=0;i<n;i++){
    cin>>ss;
    mp[ss]=i;    
}

//插入数据
mp["a"]=1;
mp.insert(map<string,int>::value_type("b",2));

//查找数据
int tmp=mp["a"];
map::iterator ite;
ite.find("a");
ite->second=j;  //注意键的值不能修改，除非删除

#include<bits/stdc++.h>
using namespace std;
int main(){
    map<int,string> mpstudent;
    mpstudent[1]="student1";
    mpstudent[2]="student2";
    mpstudent[3]="student3";
    //迭代器
    map<int,string>::iterator ite;
    for(ite=mpstudent.begin();ite!=mpstudent.end();++ite)
        cout<<ite->first<<" "<<ite->second<<endl; 
    return 0;
} 

注意：
STL中默认是采用小于号来排序的，当关键字是一个结构体时，涉及到排序就会出现问题。
因为它没有小于号操作，insert等函数在编译的时候过不去

#include <map>
#include <cstring>
using namespace std;

typedef struct tagStudentInfo
{
    int nID;
    string strName;

    bool operator < (tagStudentInfo const & _A)const
    {
        // 这个函数指定排序策略，按nID排序，如果nID相等的话，按strName排序。
        if (nID < _A.nID)
            return true;
        if (nID == _A.nID)
            return strName.compare(_A.strName) < 0;
    
        return false;
    }

} StudentInfo, *PStudentInfo;  // 学生信息

void main()
{
    // 用学生信息映射分数
    map<StudentInfo, int> mapStudent;
    StudentInfo studentInfo;
    studentInfo.nID = 1;
    studentInfo.strName = "student_one";
    mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
    studentInfo.nID = 2;
    studentInfo.strName = "student_two";
    mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
}

队列

队列的特点：
先进先出

队列的操作

q.size();
q.empty();
q.push(k);   //在队尾插入k
q.pop();     //删掉队列的第一个元素
q.front();      //返回队列的第一个元素 
q.back();   //返回队列的末尾元素 

priority_queue 优先队列

特点：
自动排序(默认从大到小)
优先队列的操作

//node是结构体，这里必须要重载"<" 
priority_queue <node> q;
//两个>>不要写在一起，>>是右移运算符 
priority_queue <int,vector<int>,greater<int> > q;  //从小到大 
priority_queue <int,vector<int>,less<int> > q;      //从大到小

含有结构体，重载 <

#include<bits/stdc++.h>
using namespace std;
//重载小于号 
struct node{
    int x,y;
    bool operator <(const node &a) const{
        return x>a.x;
    }
}k;
priority_queue <node> q;
//priority_queue <int,vector<int>,greater > q;
int main(){
    k.x=1;k.y=2;  q.push(k);
    k.x=2;k.y=1;  q.push(k);
    k.x=3;k.y=4;  q.push(k);
    while(!q.empty()){
        node t;
        t=q.top();
        q.pop();
        cout<<"("<<t.x<<","<<t.y<<")"<<endl;
    }
    return 0;
}

stack

先进后出

#include<bits/stdc++.h>
using namespace std;
int main()
{
    stack<int> S;
    S.push(3);
    S.push(7);
    S.push(1);
    cout << S.size() << " ";

    cout << S.top() << " ";    //返回栈顶元素
    S.pop();                   //从栈取出并删除元素
    
    cout << S.top() << " ";
    S.push(5);                 //向栈内添加元素
    
    return 0;

}

这篇关于c++算法训练—（一）STL库的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！