c++STL简单记录

C++的STL

源自好友：therainisme的博客

动态数组vector

// 声明模板，<>中可以定义动态u数组的类型
// 支持索引取数
vector<int> v;
// 下面两个操作可以当成栈用
v.push_back(x);   // 在尾部插入一个元素
v.pop_back(x);   // 在尾部删除一个元素
int n = v.size(); // 返回数组的个数
v.clear();	// 清空数组
v.empty();//是否为空
v.back(); // 返回最后一个数据
v.front(); // 返回第一个


//排序简单的：
sort(v.begin(),v.end());

// 迭代器遍历,这里的auto对应的是vector<int>::iterator类型
for(auto i = v.begin();i!=v.end();i++)
    cout<<*i;

// find函数使用，algorithm包里的,应该不止vector能用string也能用
auto it  = find(v.begin(),v.end(),num);
// 找到了会返回原来值的指针，找不到会返回到vector的终点
if(it != v.end())
	cout<<*it;
// 如果想用findd找到对应数据的索引,可以使用
int a = distance(v.begin(),it);
cout<<a;

栈stack

// 我觉得完全可以用vector代替
stack<int> s;   // 声明
s.push(x);      // x入栈
int t = s.top();  // 获取栈顶元素
bool b = s.empty(); // 栈是否为空
int n = s.size(); // 返回栈中元素的个数

单向队列queue

queue<int> q;    		// 声明
q.push(x);				// x入队
q.pop();				// 队头元素出队
int f = q.front();		// 返回队头元素
int e = q.back();		// 返回队尾元素
bool b = q.empty();		// 判断队列是否为空
int n = q.size();		// 返回队列元素个数

集合set

集合中不会存在重复元素，它支持高效地插入，删除和查询操作，复杂度均是$O(logn)$。它是关联容器的一种，是排序好的集合。

不能直接修改set容器中元素的值，因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏。

改set容器中某个元素的值，正确的做法是先删除该元素，再插入新元素

通过set插入的值经过begin和end的方式读取，会得出无重复的有序序列；

set<int> s; // 声明
int b = s.begin(); 	// 返回set的第一个元素，成为迭代器（指针）
int e = s.end();    // 同上，需要使用->访问
s.clear();			// 清空
bool e = s.empty(); // 判断set是否为空
s.insert(x);		// 插入元素x
s.erase(x);			// 删除一个元素x
it=s.find(x);		// 查找元素x，返回迭代器。未找到返回s.end()

映射map

从一个元素映射到另一个元素的数据结构。<key,value>。内部是红黑树，在插入时会自动排序

可以使用begin和end遍历方式，不过他会有两个值，用->firste和->second访问键和值

map<string,int> a;		// 声明
map["hello world"] = 1; // 可以像数组一样访问
if(map.count("key"))    // 可以判断是否存在这样的映射
map.clear();			// 清空

优先队列priority_queue

实际上是二叉堆，使用该模板可以快速实现小根堆，大根堆。插入，删除，查询的时间复杂度是$O(logn)$

默认声明的是小根堆

priority_queue<int> q; 		// 默认声明的是小根堆
// 声明大根堆，cmp是自定义比较函数
struct cmp{
    bool operator()(const int&a,const int &b){
        return a>b;
    }
};

priority_queue<int,vector<int>,cmp> q;
// 大根堆还能这么写
priority_queue<int,vector<int>,greater<int>> heap;

迭代器iterator

// 用法1
map<string,int> m;
map<string,int>::iterator it;
// 顺序遍历，rbegin()就是逆序遍历
for(it = m.begin();it!=m.end();it++){
    // it类指针用法
}
// 用法2
for(auto a : m){
    cout<<a.first()<<endl;
    cout<<a.second()<<endl;
}

排序sort()

普通用法

vector:		sort(v.begin(),v.end());
int a[]:	sort(a,a+n);

配合操作符重载

struct Edge{
    int a,b,c;
    bool operator < (const Edge &E) const{
        return w < E.w;
    }
}edges[N];
sort(edges,edges+m);

传入回调函数

struct Edge{
    int a,b,c;
}edges[N];
bool cmp (struct Edge a,struct Edge b){
    return a.w<b.w;
}
sort(edges,edges+m,cmp);

字符串string

s.push_back('A');				// 向尾部追加一个字符串
char c = s.back();				// 获取尾部的字符
char c = s.front();				// 获取头部的字符
s.pop_back();					// 弹出尾部的字符
// 翻转字符串
s.reverse(s.begin(),s.end());
// 排序
sort(s.begin(),s.end());
s.insert(p,"a string")			// 向下标p之后插入一个字符串
s.erase(p,n);					// 从p开始删除n个字符
s.erase(p);						// 删除p位置上的字符
s.erase(first,last);			// 删除first到last之间的字符串，参数是迭代器
s.substr(a,b);					// 从a开始获取b个字符串
string::size_type p = s.find("string"); // 找出"string"字串开始的位置
if(p == s.npos) 				// 是没有找到的情况