STL知识点总结

港控/mmm° 2022-03-15 13:12 165阅读 0赞

导言：STL是标准模板库，使用方法：先定义集合类型变量（元素类型在“<>"内具体说明）；调用具体功能格式为”变量名.成员名”。  
**一、栈（stack）**  
1.特点：先进后出，只有一个出口，只能操作顶端元素。  
2：头文件：`#include<stack>`  
3.定义：`stac<date_type>stack_name;//stack是整体类型，date_type是元素类型`  
eg:`stack<int>s;//定义一组整形数`  
4.常用操作：  
s.empty():返回bool类型，表示栈内是否为空  
s.size():返回栈元素个数  
s.top():返回栈顶元素  
s.pop():移除栈顶元素  
s.push(a):向栈内压入一个元素a  
**二、队列（queue)**  
1.特点：两个出口，先进先出，底端加入元素，从顶端取出元素。  
2.头文件：`#include<queue>`  
3.定义：`queue<date_type>queue_name`  
eg:`queue<int>q;`  
4.常用操作：  
q.empty():返回bool类型，表示queue内是否为空  
q.size():返回queue内元素个数  
q.front():返回queue内下一个元素（返回第一个元素，即队头）  
q.back():返回queue内最后一个元素（队尾）  
q.pop():移除queue中的一个元素（只能从顶端移除，即从最小下标移除）  
q.push(a):将一个元素a置入queue中（只能从底端加入元素）  
**三、vector（动态数组；向量）**  
1.头文件：`#include<vector>`  
2.定义：`vector<date_type>vector_name`  
eg:`vector<int>v;`  
3.常用操作：  
q.empty():返回bool类型，表示vector内是否为空  
q.size():返回vector内元素个数  
push\_back(date\_type a)将元素a插入最尾端  
pop\_back()将最尾端元素删除（也可以从队友或队尾删除元素）  
v\[i\]类似数组取第i个位置的元素  
**四、sort(排序函数）**  
1.头文件：`<algorithm>`（为算法头文件）  
2.格式：sort(begin,end);//默认从小到大排序（begin为首地址，end为最后一个元素的下一个位置，即不合法元素的第一个位置，为前开后闭区间）  
sort(begin,end,cmp);//cmp为自定义函数，规定比较准则  
自定义函数为：`bool cmp(int a,int b) { return a>b;//若a>b,返回true，不交换次序；若a<=b,返回false,交换次序。 } sort(num,num+5,cmp);`

使用:sort(a,a+5);
            sort(b,begin(),b.end());

**五、生成排列（可用于全排列）**  
1.头文件：`#include<algorithm>`  
2.使用：`bool next_permutation(begin,end);//改变区间内元素顺序，产生下一个排列 bool prev_per//产生前一个排列`  
end：最后一个元素下一个位置  
**六、upper\_bound和lower\_bound（查找）**  
1.前提：一组数据已经排列完成  
2.用法：`upper_bound(begin,end,value);//返回>value的元素的第一个位置，即不满足条件的第一个位置 lower_bound(begin,end,value);//返回>=value的元素的第一个位置，即满足条件的第一个位置`  
ps:`upper_bound和lower_bound使用的均为二分查找`  
eg:`num[]=={1,2,2,3,4,5}; lower_bound(num,num+6,2)为num+1(即为num[1]=2) upper_bound(num,num+6,2)为num=3（即为num[3]=3)`  
**七、set容器 (集合)**  
1.特点：自动将元素排序，默认由小到大排序，可以重载运算符(<)进行改变，无重复元素（multiset也可自动排序，但是有重复元素）  
2.头文件：`#include<set>`  
3.定义：`set<date_type>set_name;`  
eg :`set<int>s;`  
重载运算符：

struct new_type{
     int x, y;
     bool operator < (const new_type &a)const{
      if(x != a.x) return x < a.x;
      return y < a.y;
     }
    }
    set <new_type> s;

4.简单应用：  
s.intsert(elem):安插一个elem副本，返回新元素的位置  
s.erase(elem):移除与elem元素相等的所有元素，返回被移除元素的个数  
s.erase(pos):移出迭代器pos所指位置上的元素，无返回值。 s.clear():移除全部元素，将容器清空  
s.find(“元素”):查找元素所在位置（二分查找）  
s.size() – 返回容器大小。  
s.empty() – 返回容器是否为空。  
s.count(elem) – 返回元素值为elem的元素的个数（只针对multiset）  
s.lower\_bound(elem) – 返回 元素值>= elem的第一个元素位置。  
s.upper\_bound(elem) – 返回元素值 > elem的第一个元素的位置。  
以上位置均为一个迭代器。  
s.begin() – 返回一个双向迭代器，指向第一个元素。  
s.end() – 返回一个双向迭代器，指向最后一个元素的下一 个位置

5.迭代器：用来检查元素并遍历的数据类型 \`\`\`

multiset<int>::iterator pos;                
     for(pos=s.begin();pos!=s.end();pos++)                     
      {
           cout << (*iter1) << endl;
       }

ps:结构体初始化方法：  
eg:`struct T1{ int key; int value1, value2; bool operator<(const T1 &b)const{ return (key < b.key); } };`

T1 t={2,33,44};//方法一
     T1 tt;
     tt.key=5;
     tt.value1=22;
     tt.value2=88;//方法二

**八、map和multimap(映射）**  
1，定义：map的所有元素都是pair（pair为关连内容说明），pair的第一个元素被视为键值，第二个元素为实值。map不允许两个元素有相同的键值（实值可以重复），但multimap可以。  
2.头文件:`#include <map>`  
3.定义：`map <data_type1, data_type2> map_name;`  
如：`map <string, int> m;//默认按string由小到大排序`  
4.操作：  
m.size() 返回容器大小  
m.empty() 返回容器是否为空  
m.count(key) 返回键值等于key的元素的个数  
m.lower\_bound(key) 返回键值等于key的元素的第一个可安插 的位置  
m.upper\_bound(key) 返回键值等于key的元素的最后一个可安 插的位置  
m.begin() 返回一个双向迭代器，指向第一个元素  
m.end() 返回一个双向迭代器，指向最后一个元素的下一个 位置。  
m.clear() 将整个容器清空  
m.erase(elem) 移除键值为elem的所有元素，返回个数，对 于map来说非0即1（map中键值不能重复）  
m.erase(pos) 移除迭代器pos所指位置上的元素  
直接元素存取：  
m\[key\] = value；  
查找的时候如果没有键值为key的元素，则安插一个键值为key的新元素，实值为默认(一般0)  
m.insert(elem) 插入一个元素elem  
1)运用value\_type插入

map<string, float> m;
    m.insert(map<string, float>:: value_type ("Robin", 22.3));

1.  运用pair<>

m.insert(pair<string, float>("Robin", 22.3));

1.  运用make\_pair()

m.insert(make_pair("Robin", 22.3));

**九、优先队列（priority\_queue）**  
1.定义：一个拥有权值观念的queue，根据自定义的权值排列，权值最高排在前面。  
（排列规则：树状结构，只能跟上级比较，不能平级比较）  
2.头文件:`#include <queue>`  
3.定义：`priority_queue <data_type> priority_queue_name;`  
如：`priority_queue <int> q;//默认是大顶堆`  
4.基本操作：  
q.push(elem) 将元素elem置入优先队列  
q.top() 返回优先队列的下一个元素  
q.pop() 移除一个元素（最大的一个元素）  
q.size() 返回队列中元素的个数  
q.empty() 返回优先队列是否为空  
5. ps:优先队列不一定按单增或单减，通过交换将最大值放在最前面

struct coord{
        int x, y;
        const bool operator<(const coord &b)const{
            return (dist2(x, y) < dist2(b.x, b.y));
        }//按平方和大小比较