STL

string

字符串

构造函数

string s = ""
s1 = s2

增加元素

s += s2  //直接用 + 即可
s += "new string"

删除元素

string& erase ( size_t pos = 0, size_t n)         //删除从pos开始的n个字符
iterator erase ( iterator)                        //删除一个
iterator erase ( iterator first, iterator last )  //删除范围

iterator erase(remove(str.begin(), str.end(), 'a'), str.end()) //删除特定字符

迭代器

iterator begin();  //头迭代器
iterator end();   //尾迭代器

其他

sort(string, iterator l, iterator r) //排序 [l, r) 
string substr(int pos, int n)        //获取连续子串，从 pos 开始的 n 个字符，-1表示到最后
bool empty()                         //判断是否为空
int size()                           //字符个数
bool isalnum(char)                   //如果c是字母或数字，返回 true
bool isalpha(char )                  //如果c是字母，返回true
bool iscntrl(char)                   //如果c是控制符，返回true
bool isdigit(char)                   //如果c是数字，返回true
bool isgraph(char)                   //如果c不是空格，返回为true
bool islower(char)                   //如果c是小写字母，返回为true
bool isupper(char)                   //如果c是大写字符，返回为true
bool isprint(char)                   //如果c是可打印的字符，返回为true
bool ispunct(char)                   //如果c是标点符号，返回为true
bool isspace(char)                   //如果c是空白字符，返回为true
bool isxdigit(char)                  //如果c是十六进制数，返回为true

vector

\(include<vector>\)

构造函数

vector()                    //创建一个空vector
vector(int nSize)           //创建一个vector,元素个数为nSize
vector(int nSize,const T& t)//创建一个vector，元素个数为nSize,且值均为t
vector(const vector&)       //复制构造函数
vector(begin,end)           //复制[begin,end)区间内另一个数组的元素到vector中

增加元素

void push_back(const T& x)                               //向量尾部增加一个元素X
iterator insert(iterator it,const T& x)                  //迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x)            //迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,iterator first,iterator last)//迭代器指向元素前插入另一个向量的[first,last)的数据

删除元素

iterator erase(iterator it)                 //删除迭代器指向元素
iterator erase(iterator first,iterator last)//删除[first,last)中元素
void pop_back()                             //删除向量中最后一个元素
void clear()                                //清空向量中所有元素

迭代器

reference at(int pos)       //返回pos位置元素的引用
reference front()           //返回首元素的引用
reference back()            //返回尾元素的引用
iterator begin()            //返回向量头指针，指向第一个元素
iterator end()              //返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin()   //反向迭代器，指向最后一个元素
reverse_iterator rend()     //反向迭代器，指向第一个元素之前的位置

其他

int size() const              //返回向量中元素的个数
int capacity() const          //返回当前向量所能容纳的最大元素值
int max_size() const          //返回最大可允许的vector元素数量值
bool empty() const            //判断向量是否为空，若为空，则向量中无元素
void swap(vector&)            //交换两个同类型向量的数据
void assign(int n,const T& x) //设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last)//向量中[first,last)中元素设置成当前向量元素

stack

\(include<stack>\)

构造函数

list<int> c0                       //空链表
list<int> c1(3)                    //建一个含3个默认值是0的元素的链表
list<int> c2(5,2)                  //建一个含5个元素的链表，值都是2
list<int> c4(c2)                   //复制
list<int> c5(iterator beg, iterator end)              //区间[beg, end)做为元素初值

push(const T& x)                   //入栈
T pop()                            //出栈
T top()                            //获取栈顶
bool empty()                       //判断空栈
int size()                         //返回栈元素个数

list

\(include <list>\)

构造函数

c1 = c2             //复制
assign(n, elem)      //赋值n个elem
assign(beg, end)   //区间[beg,end）内的元素赋值给c
swap(c1, c2)        //交换 

增加元素

push_front()        //首加
push_back()         //尾加
insert(pos,num)     //在pos位置插入元素num，返回新元素位置
insert(pos,n,elem)  //在pos位置上插入n个elem副本，无返回值
insert(pos,beg,end) //在pos位置上插入区间[beg,end)内的所有元素的副本，没有返回值

删除元素

pop_front()         //首删
pop_back()          //尾删
erase(pos)　　　　   //删除pos位置的元素，返回下一个元素的位置
erase(beg,end)      //移除[beg, end)区间内的所有元素，返回下一个元素的位置
remove(num)         //删除链表中匹配num的元素
remove_if(cmp)      //删除条件满足的元素,参数为自定义的回调函数
clear()             //清空

迭代器

list<T>::iterator it
c.begin()  
c.end()   
c.rbegin()          //逆向链表的第一个元素,即c链表的最后一个数据。
c.rend()            //返回逆向链表的最后一个元素的下一个位置,即c链表的第一个数据再往前的位置。it++

其他

T front()             //首元素
T back()              //尾元
bool empty()          //判断是否为空
int size()            //有效元素个数
int max_size()        //返回容器最大的可以存储的元素
bool c1 == c2         //比较
sort()                //单链表排序
unique()              //去重，要先排序
c1.merge(c2)          //合并2个有序的链表并使之有序,从新放到c1里,释放c2
c1.merge(c2,cmp)      //合并2个有序的链表并使之按照自定义规则排序之后从新放到c1中,释放c2
reverse()             //反转
resize(int)           //重置有效元素个数

set

\(include<set>\)

平衡二叉搜索树，不会存储重复的元素

构造函数

swap(set, set )        //  交换两个集合变量
s1 = s2

增加元素

insert(T)     //  在集合中插入元素

删除元素

clear()       //  清除所有元素
erase(T)      //  删除集合中的元素

迭代器

set<T>::iterator it
begin()       //  返回指向首元素的迭代器
end()         //  返回指向尾元素的后一位的迭代器
rbegin()      //  反向迭代器
rend()        // 

其他

int count(T)              //  返回某个元素的个数,0或1，只能判断是否存在
bool empty()              //  判断集合为空
int size()                //  集合中元素的数目
max_size()                //  返回集合能容纳的元素的最大限值
iterator find(T)          //  返回一个指向被查找到元素的迭代器,无则返回end()
iterator lower_bound(T)   //  返回指向大于或等于某值的第一个元素的迭代器
iterator upper_bound(T)   //  返回大于某个值元素的迭代器

pair

\(include<utility>\)

两任意类型元素的结构体

pair<int, double> p1;    //默认构造函数
pair<int, double> p1(1, 1.1);   //含参构造函数
pair<int, double> p1(p2);   //拷贝构造函数  p1 = p2

p1.first                 //获取 第一个元素
p1.second                //获取 第二个元素
p1 < p2                  //可以直接比较,先比较first，再比较second

map

\(include<map>\)

建立Key－value的对应，key 和 value 可以是任意类型。

构造函数

map<int, string> m1;   //索引为 int型
map<string, int> m2;   //索引为 string

增加元素

insert(pair<int, string>(1, "string1"))   //这里的元素可以是元素类型与声明匹配的2元素结构体或者pair，insert不能覆盖原值


map<int,string> m1    //数组可以覆盖原值
m1[1] = "string1"     //如果没有对应 key 值会自动添加
m1[2] = "string2"
map<string, int> m2
m2["string1"] = 1
m2["string2"] = 2

删除元素

erase(iter)
erase(iterator first, iterator second)  //删除范围 
clear(）                                //删除所有元素

迭代器

iterator begin()
iterator end()
iterator rbegin()        //返回一个指向map尾部的逆向迭代器
iterator rend()          //返回一个指向map头部的逆向迭代器
map<int, string>::iterator iter;  
for(iter = m1.begin(); iter != m1.end(); iter++)    //遍历
    cout<<iter->first<<' '<<iter->second<<endl;

其他

int size()                    // 获取大小 
iterator find(T)              //  T 是 value 类型，没找到返回 end()
swap(m1[key1], m1[key2])      //交换 value
bool empty()                  //如果map为空则返回true
int  count()                  //返回指定元素出现的次数

queue

\(include<queue>\)

先进先出（FIFO），只能尾加和首删，只能访问队首和队尾元素，

bool empty()  //队列为空返回真
T front()  //返回第一个元素
T back()   //返回最后一个元素 
int size()   //返回元素个数

push()   //队尾加入元素
pop()    //删除队首元素
swap()   //交换内容

清空队列的三种方法（没有clear操作）

//用空队列赋值
q1=queue<T>();
//不断首删
while(!q.empty())q.pop();
//自己定义clear
void clear(queue<T>& q){
    queue<T>empty;
    swap(empty,q);
}

priority_queue

\(include<queue>\)

默认大根堆

priority_queue

数据类型 容器 比较方式 其中 Container需要用数组实现的容器

声明

priority_queue<T> p;
priority_queue<int,vector<int>, greater<int> > p;  //小根堆    在sort里greater是从大到小
priority_queue<int,vector<int>,less<int> >p;    //大根堆
/*自定义优先级的2种方式*/
//
struct node{     
　　int x;     
　　bool operator < (const node& a) const     {         
　　　　return a.x < x;    //小根堆     
　　}
};
priority_queue<node> p;
//
struct cmp {     
　　bool operator ()(int x, int y) {        
　　　　 return　x > y; //小根堆
　　}
};
priority_queue<int, vector<int>, cmp>q; 

成员函数

top()      //访问队头元素
empty()    //队列是否为空
size()     //返回队列内元素个数

push()     //队尾加入元素（并排序）
pop()      //弹出队顶元素    
swap()     //交换内容

deque

\(include<queue>\)

构造函数

deque<T> deq;               //空deque
deque(n)                    //元素个数为n
deque(n,elem)               //元素个数为n,且值均为elem
deque(beg,end)              //[beg, end)
deque(const deque &deq)     //复制构造函数

增加函数

void push_front(elem)    //头插
void push_back(elem)     //尾插
? insert(pos,elem)       //某一元素前增加一个元素x
void insert(pos,n,elem)  //某一元素前增加n个相同的元素x
void insert(pos,beg,endt)//某一元素前插入另一个相同类型向量的[forst,last)间的数据

删除函数

? erase(pos)     //删除某一个元素,返回下一个元素位置
? erase(beg,end)   //删除[first,last）中的元素,返回下一个元素位置
void pop_front()          //头删
void pop_back()           //尾删
void clear()                              

遍历函数

reference at(pos)         //返回pos位置元素的引用
reference front()         //返回首元素的引用
reference back()          //返回尾元素的引用
iterator begin()          //返回头迭代器
iterator end()            //返回尾迭代器（最后一个元素的下一个
reverse_iterator rbegin() //反向迭代器，指向最后一个元素
reverse_iterator rend()   //反向迭代器，指向第一个元素的前一个元素

其他函数

bool empty()        //向量是否为空
int size()          //返回元素的个数
int max_size()      //返回最大可允许的元素数量
void swap(deque&)   //交换两个同类型deque的数据
void assign(beg, end)    //将[beg, end)区间中的数据拷贝赋值给本身。
void assign(n, elem)     //将n个elem拷贝赋值给本身。

algorithm

lower_bound()

二分查找

对于升序数组：

lower_bound( begin, end, num)：查找第一个大于等于 num 的数并返回其地址，不存在返回end。返回值减去begine即索引下标

upper_bound( begin, end, num)： 大于

对于降序数组：需要重载

//升序 a数组中 k 的个数
upper_bound(a, a+n, k)-lower_bound(a, a+n, k);

next_permutation

//求按照字典序的全排列
int a[4]={1,2,3,4};
while(next_permutation(a,a+4))
{
    for(int i=0;i<4;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

min_element/max_element

int maxx = *max_element(a, a+n);