ACM常用STL

转载于https://blog.csdn.net/riba2534/article/details/61929000

1. stack

stack<int>st;//栈st，用于存放int型数据

st.push();//将3入栈

st.push();//将2入栈

st.pop();//栈顶2出栈

int Top = st.top();//获取栈顶元素,即3

int Size = st.size();//求栈中的元素个数

bool isEmpty = st.empty(); //栈中元素是否为空，1表示空，0表示非空  

stack<T>st;  // T是存放数据的类型，可以是int, double等，也可以是自定义的结构体类型

如：

struct Node

{

    int x,y;

};

stack<Node> st;

2. queue

queue<int>que;//队列que,存放int型数据

que.push();//将3入队列

que.push();//将2入队列

que.pop();//队首3出队列

int Front = que.front();//获取队首元素

int Size = que.size();//队列中元素个数

bool isEmpty = que.empty(); //是否为空  

queue<T>que;  // T是存放数据的类型，可以是int, double等，也可以是自定义的结构体类型.

3. priority_queue

优先队列中的元素按照一定的优先级进行排列，对于int型的元素，默认是从大到小进行排列的，队首为最大元素.

const int len = ;

int a[len] = {, , , , };

priority_queue<int> q;

for(int i = ; i < len; ++ i)

{

    q.push(a[i]);

}

for(int i = ; i < len; ++ i)

{

    cout<< q.top() <<endl;

    q.pop();

}

输出的元素依次为 9 6 5 3 2

如果要按照从小到大排列，把priority_queue<int>q;这条语句换成

priority_queue<int,vector<int>,greater<int>>q;就可以实现。

另外我们可以根据需求，自己定义优先级，对’<’符号进行重载，使得队列中的元素按照一定的顺序排列，假设我们定义一个操作系统中作业的结构体，里面有两个元素，一个是作业名char name[5]; 一个是到达时间intarriveTime; 把作业对象放到优先队列里面，要求在优先队列按作业到达时间从小到大排列，即到达时间最小的作业在队首.

struct Job //定义作业结构体

{

    char name[];//作业名

    int arriveTime;//到达时间

    bool operator < (const Job another)const{//如果当前作业到达时间大于另一个，则当前作业优先级小

        if(arriveTime > another.arriveTime)

            return true;

        return false;

    }

}job[];  

int main()

{

    strcpy(job[].name, "no1");

    strcpy(job[].name, "no2");

    strcpy(job[].name, "no3");

    job[].arriveTime = ;

    job[].arriveTime = ;

    job[].arriveTime = ;  

    priority_queue<Job> que;

    que.push(job[]);

    que.push(job[]);

    que.push(job[]);

    for(int i = ; i < ; ++ i)

    {

        Job tempJob = que.top();

        que.pop();

        cout<< tempJob.name <<"  "<<tempJob.arriveTime<<endl;

}

return ;

}

输出为：

no2 1

no1 2

no3 3

实现了优先队列中的作业按照到达时间排序.

4. vector

vector是一种容器，可以看做是动态的数组.

vector<int>vec;

vec.push_back();//尾部插入数字2,即 vec[0]=2

vec.push_back();//尾部插入数字4,即 vec[1]=4

int Size = vec.size();//容器中存放数字的个数

cout<< vec[] <<endl;//访问第二个数字，即4  

for(int i = ; i < vec.size(); ++ i)//按照下标遍历元素,此时vec[0]=2  vec[1]=4

{

    cout<< vec[i] << " ";

}

cout<<endl;  

vector<int>::iterator it;//按照迭代器遍历元素

for(it = vec.begin(); it != vec.end(); ++ it)

{

    cout<< *it <<" ";

}

cout<<endl;  

vec.insert(vec.begin() + , );//在第二个位置上插入元素6，即vec[1]=6

vec.erase(vec.begin() + );//删除第二个位置上的元素

vec.clear();//把容器中的元素全部清除

另外也可以定义二维动态数组即vector<int>vec[2];也就是两个容器，用它可以很方便的保存有向图的邻接表,即vec[i]中存放的是与第i个顶点相邻的顶点（从顶点i出发），.其操作只要把上述代码中的vec改成vec[i] 就可以.

5. set

set这种容器里面存放元素是唯一的，即不可能两个相同的数都存在set里面，set的效率比较高，起内部采用了高效的平衡检索二叉树：红黑树。插入的元素按从小到大自动排好序，第一个元素为最小值。

set<int>st;//容器中存放int型数据

st.insert();//插入元素2

st.insert();

st.insert();

st.insert();  

int Size = st.size();//容器中元素个数

bool isEmpty = st.empty();//元素是否为空

int has1 = st.count();//1这个元素是否在set中 st.count()不是1就是0

int has2 = st.count();//6这个元素是否在set中，has1值为1  has2值为0

st.erase();//在容器中删除1这个元素

bool inSet = (st.find(-)!= st.end());//-2这个元素是否在set中

cout<<*st.lower_bound()<<endl;//返回set中第一个大于等于1的数

cout<<*st.upper_bound()<<endl;//返回set中第一个大于1的数  

set<int>:: iterator it;//遍历set容器，输出 1 2 3

for(it = st.begin(); it != st.end(); ++ it)

{

    cout<< *it <<"  ";

}

cout<<endl;  

st.clear();//清空set中的元素

6. map

map是一种映射关系，一对一，第一个为关键字（first），第二个为键值(second)，关键字唯一，map中的元素按关键字有序. 实际应用中要考虑好关键字和键值代表的意义，灵活运用。

比如:

map<string, int> mp; //关键字为string类型，键值为int 类型，我们可以用来表示某一个符

//串str出现的次数,int型键值默认为0

cout<< mp[“hello”] <<endl; //输出”hello”这个字符串出现的次数，这里原来map是空的，但

//但是我们输出了一下以后，mp的元素个数自动变成了1，但是”hello”对应的键值仍然为0  

mp.clear();//清空元素

mp.insert(make_pair("hello",));//插入键值对，代表初始的时候"hello"出现的次数为1

mp.insert(make_pair("world",));//插入键值对，初始的时候"world"出现的次数为3

mp.insert(make_pair("apple",));//插入键值对，初始的时候"apple”出现的次数为1

cout<<mp.size()<<endl;//map中的元素个数，这里输出3  

map<string, int>:: iterator it;//遍历map

for(it = mp.begin(); it!= mp.end(); ++ it)

{

    cout<<it->first<<"  "<<it->second<<endl;

}

输出如下：

apple 1

hello 1

world 3

可以发现元素是按关键字从小到大排好序的

cout<< mp[“hello”]<<end;//查看”hello”出现的次数

mp[“hello”] ++ ;//”hello”出现的次数+1  

bool inMap = mp.count(“hello”); //”hello”是否在map中，返回0或1

inMap = (mp.find("hello") != mp.end()); //”hello”是否在map中，返回0或1  

for(it = mp.begin(); it != mp.end(); ++ it)//查找到”hello”,然后删除该元素

{

    if(it->first == "hello")

    {

        mp.erase(it);

        break;

    }

}

7. sort

头文件#include<algorithm>

使用sort可以很方便的对数组进行进行排序,它可以传两个或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一个地址，也就是排序的区间为[a,b),比如有一个数组 int a[5], 使得a[0] 到a[4]从小到大有序，只要写 sort(a, a + 5)就可以了，通用sort(a, a+ n);// n为元素个数。sort内部采用的是快速排序，一般情况下效率很高.

const int n = ;

int arr[n] = {, , };

sort(arr,arr+n);

for(int i = ; i < n; ++ i)

cout<< arr[i] <<endl;

另外，我们也可以按照自己的需求进行元素排序，元素可以是结构体，这里就用到了第三个参数，比较函数，告诉计算机按照什么顺序进行排序。

比如：按照从大到小排序

bool cmp(int a, int b)//定义比较函数，从大到小

{

    if(a >= b)

        return true;

    return false;

}

主函数中： sort(arr, arr+n,cmp);

再比如下面结构体，要按照学生的年龄从小到大排序.

struct Student

{

    int age; //年龄

    string name;//姓名

}student[];  

bool cmp(Student a, Student b)

{

    if(a.age <= b.age)

        return true;

    return false;

}  

student[].name = "aa";student[].age = ;

student[].name = "bb";student[].age = ;

student[].name = "cc";student[].age = ;

sort(student, student+, cmp);

for(int i = ; i < ; ++ i)

cout<< student[i].name <<"  "<<student[i].age<<endl;

输出：

cc 8

bb 10

aa 15

8. cmath

cout<< log2() <<endl;  //输出3 , 因为2的3次方为8

cout<< log10() <<endl;  //输出2，因为10的2次方为100

cout<< log() <<endl;  //计算 ln(20)的值

补充：

//vector-----------------

   vector<int>v;

   v.erase(v.begin() + );//删除第2个元素，从0开始计数

   v.erase(v.begin() + , v.begin() + );//删除第1到第5个元素

   sort(v.begin(), v.end());//元素排序

   //sort(v.begin(), v.end(), cmp);//自定义排序规则，cmp函数自定义

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

   //string-----------------

   string s;

   s = "";

   string::iterator it;

   it = s.begin();

   s.insert(it + , 'p');// s 变为 1p23456

   s.erase(it + );//删除第3个字符，从0开始计数

   s = "abc123456";

   s.replace(, , "good");//从第3个开始，将连续的3个字符替换为"good",即将123替换为good

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

   //set--------------------

   set<int>st;

   //反向遍历，从大到小

   set<int>::reverse_iterator rit;//定义反向迭代器

   for(rit = st.rbegin(); rit != st.rend(); rit ++)

   {

       cout << *rit << endl;

   }  

   //multiset--------------里面值可以重复

   multiset<int> ms;

   int n = ms.erase(); //删除里面所有的3，返回删除元素总个数

   multiset<int>::iterator it;

   it = ms.find();

   if(it != ms.end())//找到了3这个元素

   {

       cout << *it <<endl;

   }

   else

   {

       cout<< "not find it"<<endl;

   }  

   //map-----------键值-->映照数据

   map<int> mp;

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

   map<int>::iterator it;

   it = mp.find();//查找键值

   if(it != mp.end())//找到了

   {

       cout << (*it).first << (*it).second <<endl;

   }  

   struct Info

   {

       string name;

       float score;

       //重载'<'操作符，自定义排序规则，在map中

       bool operator < (const Info &a) const

       {

           //按score从小到大排序

           return a.score < score;

       }

   };  

   map<Info, int> mmp;  

   //multimap------------允许键值相同的存在

   multimap<string, double>m;

   m.insert(pair<string, double> ("jack", 20.4));

   m.insert(pair<string, double> ("jack", 34.1));

   m.erase("jack");//删除键值等于"jack"的元素

   //find()函数只返回重复键值中的第一个元素的迭代器位置  

   //deque-------------双端队列

   push_back()方法在尾部插入元素，不断扩张队列

   push_front()和insert()在首部和中间位置插入元素，只是将原位置上的元素值覆盖，不会增加新元素

   deque<int> d;

   d.push_back();

   d.push_back();

   d.push_back();

   d.insert(d.begin() + , );

   cout << d[] << d[] << d[] <<endl; //输出 1 88 3

   d.pop_front();//头部删除元素

   d.pop_back();//尾部删除元素

   d.erase(d.begin() + );  

   //list--------------链表

   list<int> l;

   l.push_back();

   l.push_back();

   l.push_back();//链表尾部插入元素，链表自动扩张

   l.push_front();//链表头部插入元素，链表自动扩张

   list<int>::iterator it;

   it = l.begin();

   it ++;//注意链表的迭代器只能进行 ++ 或者 -- ，不能 + n

   l.insert(it, );

   for(it = l.begin(); it != l.end(); it ++)

   {

       cout << *it <<endl;  //输出 8 20 2 1 5

   }

   l.remove();//值为2的节点都删除

   l.pop_front();//删除首部元素

   l.pop_back();//删除尾部元素

   l.sort();//排序

   l.unique();//剔除重复元素， 3 8 1 1 1 3 1 ---->  3 8 1 3 1  

   //bitset 位集合容器

   bitset<>b; //能容纳10个元素，也就是10位，默认都为0

   //赋值

   b[] = ;

   b[] = ;

   b[] = ;

   //第0位是最低位，第9位是最高位

   for(int i = b.size() - ; i >= ; i --)

   {

       cout << b[i] << " ";   //输出 1001000010

   }

   b.set();//全部重置为1

   b.set(, );//将第1位置为1

   b.set(, );

   b.set(, );

   b.reset();//将第9位置为0

   cout << b <<endl;// 和上面效果相同，也是输出1001000010

巴特西

ACM常用STL

最新文章

热门文章