挑战程序设计(算法和数据结构)—数据结构（STL总结）

STL（Standard Template Library)简介

栈

头文件#include <stack>
使用 stack<int> S;
成员函数

队列

普通队列

头文件#include <queue>
使用queue<int> Q
成员函数

优先队列

• 头文件：#include <queue>
• 先出队列的是优先级最高的元素。
• 使用priority_queue<int> pq;(默认:值越大，优先级越高)。
• 注意：取元素的方法由queue的front()变为top()。
• priority_queue<int，vector<int>, greater<int> > pq;值越小，优先级越大，注意最后两个">"中间要有空格。
• 自定义类型需要自己定义优先级比较函数。
• 优先队列使用堆结构来实现，堆的操作复杂度为O（logn）。

具体情况见代码：

struct cmp1{ 
    bool operator ()(int &a,int &b){ 
        return a>b;//最小值优先 
    } 
}; 

struct node {     
　　int x, y;     
　　bool operator < (const node&a) const 
　　{         
　　　　return x > a.x;    //结构体中，x小的优先级高     
　　}
};

priority_queue<int，vector<int>, cmp1 > pq;// 其中，第二个参数为容器类型。第三个参数为比较函数。
priority_queue<node>q;   //定义方法
//在该结构中，y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时，最好不要重载”>”，可能会发生编译错误

双端队列

头文件：#include <deque>
使用：deque<int>s1;
成员函数

• 注意：支持与vector类似的随机访问（O(1)）：int x=Q[3];

vector(动态数组)

头文件#include <vector>
使用vector <int> V
成员函数

vector技巧
1.初始化(5种)
vector<int>vec; //初始化为空

vector<int>vec(v1);//用另一个vector来初始化，即构造一个副本

vector<int>vec(n, i);//大小为n，并全部初始化为元素i （常用）

vector<int>(n);//构造大小为n的容器，没有初始化里面的元素

vector<int>{1,2,3,4}; //构造大小为4，并初始化里面的各个元素

2.遍历容器

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++){
	vec[it]=0;
}

3.调整空间

vec.capacity();//获取容器分配的存储空间，区别于vec.size()
vec.resize(n+m);//调整vec的大小变为n+m，同时还可以通过该函数调整大小删除末尾一些数据

4.vector经常用到的一些函数功能。
需加头文件#include<algorithm>

sort(vec.begin(),vec.end());//对元素排序
reverse(vec.begin(), vec.end());//反转容器
swap(vec[i],vec[j]);//交换元素

参考自C++容器vector的常用成员函数

list(双向链表)

头文件#include <list>
使用list<int> L
成员函数

set(集合)

头文件#include <set>
使用set<int> S

• set是元素值进行排序的集合，所插入的元素在集合中唯一，不存在重复元素。如果是结构体需要重载"<",来排序元素。
• set由二叉搜索树实现，而且对树进行了平衡处理，使得元素在树中分布较为均匀，因此能保持搜素、插入、删除操作的复杂度在O(logn)。

成员函数：

map(键值对集合)

头文件#include <map>
使用map<string, int> T(以string为键的int型元素)

• map集合以键与值组合为元素，集合以值作为排序标准，集合中各元素的键唯一，不存在重复。
• 可以使用"[ ]"来访问指定键对应的值或迭代器来访问每一对键和值。
• map和set一样通过平衡二叉搜索树来实现，因此元素的插入、删除、搜索以及"[ ]"运算的复杂度均为O(logn)
• map中的key默认是以less<>升序对元素排序（排序准则也可以修改），也就是说key必须具备operator<对元素排序，而平常我们的用的基本上都是基本类型元素作为key，所以就不存在这个问题了。如果是结构体需要重载"<",来排序key值。
  例子：

struct Puzzle
{
    int f[N2];
    int space;
    string path;
    bool operator < (const Puzzle &p) const {
        for(int i=0; i<N2; i++)
        {
            if(f[i]==p.f[i]) continue;
            return f[i] < p.f[i];//代表升序排列
            }
        return false;
    }
};

成员函数：
key为键，val为值

其它

拓展：STL的结构体pair

• 无头文件
• 使用pair<string, int> T来初始化或直接用make_pair(x,y)来建立一个结构体元素
• 第一个元素可以使用first访问，第二个元素可以使用second访问。eg:T.first和T.second

其他知识点：

• 能进行算术运算的迭代器只有随机访问迭代器，要求容器元素存储在连续内存空间里，vector，string，deque的迭代器是有加减法的，但是map，set，multimap,multiset的迭代器是没有加减法的，list也不可以 。

algorithm

sort(排序)

1. 全局函数形式的自定义排序

//定义一个节点
struct node {
	int a;
	string name;
};

//以全局函数的形式自定义排序函数
bool cmp(node x, node y) {
	return x.a < y.a;  // 从小到大排序
}

vector<node> v;
sort(v.begin(), v.end(), cmp);

2. 结果体内部的自定义排序

struct node {
	int a;
	string name;
	bool operator < (const node&a) const 
　　{         
　　　　return x < a.x;    // 从小到大排序  
　　}
};

vector<node> v;
sort(v.begin(), v.end());

• min、max
• swap(a,b)（交换a、b的值) 支持所有的内置类型以及用户自己定义的结构体。

最后

以上就是傻傻龙猫为你收集整理的挑战程序设计(算法和数据结构)—数据结构（STL总结）的全部内容，希望文章能够帮你解决挑战程序设计(算法和数据结构)—数据结构（STL总结）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。