Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

STL操作总结

  • STL(Standard Template Library,标准模板库)是C++标准不可缺少的一部分,也是我们平时写程序非常实用的工具。
    本文简单总结了若干STL中常用数据结构的用法,包括向量(vector)、栈(stack)、队列(queue)、优先队列(priority queue)、映射(map)、集合(set)等,供使用时快速参考。详细的内容参考STL手册。

    1. 向量(vector)。头文件<vector>

    void f()
    {
    	vector<int> v;			//空
    	vector<int> v1(10);		//指定个数
    	vector<int> v2(10, -1);	//指定个数,初始值
    	int x[3] = {1, 2, 3};	vector<int> v3(x, x+3); //数组初始化,[st, ed)
    	vector<int> v4(v3);		//vector初始化
    
    	v.empty();	v.size();	//是否为空,元素个数
    	v.push_back(100); v.pop_back();		//插入 删除元素 
    	for (int i = 0; i < v.size(); i++)	cout << v[i] << endl;		//数组遍历
    	for(vector<int>::iterator p = v.begin(); p != v.end(); p++) cout << *p << endl;	//迭代器遍历
    }

    2. 栈(stack)。头文件<stack>。

    void f()
    {
    	stack<int> s;	//初始化
    	s.push(100); s.pop();	//入栈 出栈
    	s.top(); s.empty(); s.size();	//取栈顶,判栈空,栈大小
    	while(!s.empty())	s.pop();	//清空栈
    }

    3. 队列(queue)。头文件<queue>。

    void f()
    {
    	queue<int> q;	//初始化
    	q.push(100); q.pop();		//入队 出队
    	q.front(); q.back(); q.empty(); q.size();		//取队首 队尾 判队空 队大小
    	while(!q.empty())	q.pop();	//清空队列	
    }

    4. 仿函数(functor)。头文件<functional>。部分操作用到了仿函数,做个简单介绍。仿函数是实现了operator()的类,可以模拟函数的行为,这里只涉及关系运算的仿函数。

    struct cmp{	bool operator()(const int& a, const int& b)	{return a > b;} };
    void f()
    {
    	int a[5] = {1, 3, 2, 5, 4};
    	sort(a, a+5);					//从小到大
    	//STL自带关系仿函数 equal_to<T> not_equal_to<T> greater<T> greater_equal<T> less<T> less_equal<T>
    	sort(a, a+5, greater<int>());	//从大到小
    	//自定义关系仿函数
    	sort(a, a+5, cmp());			//从大到小
    }

    5. 优先队列(prority queue)。头文件<queue>。

    struct Node{ int x, y;	Node(int a = 0, int b = 0):x(a), y(b){}	};	//Node结构
    bool operator<(Node a, Node b){return a.x > b.x;}		//重载Node <
    struct cmp{ bool operator()(const Node&a, const Node&b){return a.x > b.y;}};	//仿函数
    void f()
    {
    	priority_queue<int> q;	//默认小于,大根堆,队首元素最大
    	priority_queue<int, vector<int>, greater<int> > q1; //大于,小根堆
    	priority_queue<Node> q2; //使用重载的<,大根堆
    	priority_queue<Node, vector<Node>, cmp> q3; //使用仿函数,大于,小根堆
    
    	q.push(100); q.pop();			//入队 出队
    	q.top(); q.empty(); q.size();	//取队首 判队空 队大小
    	while(!q.empty())	q.pop();	//清空队列	
    }

    6. 映射(map)。头文件<map>。

    struct cmp{	bool operator()(const int& a, const int& b)	{return a > b;}};//仿函数
    void f()
    {
    	map<int, int> m;		//默认按key升序排
    	map<int, int, cmp> m1;	//根据cmp按降序排
    	m[1] = 2; m.insert(pair<int,int>(1, 2)); m.insert(map<int,int>::value_type(1, 2));//3种插入方法
    	m.find(1);	//查找,ans==m.end()时查找失败,使用ans->first,ans->second访问
    	m[1];		//访问元素(确定1存在)
    	m.empty(); m.clear(); m.erase(p);	//判空 清空 删除迭代器p所指元素(确定存在)
    }

    7. 集合(set)。头文件<set>。

    struct Node{ int x, y;	Node(int a = 0, int b = 0):x(a), y(b){}	};	//Node结构
    struct cmp{ bool operator()(const Node&a, const Node&b){return a.x > b.y;}};	//仿函数
    void f()
    {
    	set<int> s;					//默认从小到大排序
    	set<int, greater<int> > s1;	//从大到小排序
    	set<int> s2(s);		set<int> s3(st, ed); //指定内容set初始化
    	set<Node, cmp> s4;	//自定义结构体,排序函数
    
    	s.insert(100);	s.insert(p, 100); //插入(在迭代器p或之后插入),返回pair<iterator, bool>,表示位置,成功与否
    	s.find(100); //查找,没找到时 p==s.end()
    	s.erase(100);	s.erase(p);		s.erase(p1, p2);	//删除
    	s.empty();		s.clear();		s.size();	s.count(100);	//判空 清空 大小 统计
    	for(p = s.begin(); p != s.end(); p++) cout << *p << endl; //遍历
    
    	//集合运算
    	set<int> a1; a1.insert(1); a1.insert(2);		
    	set<int> a2; a2.insert(2); a2.insert(3);
    	vector<int> rs;		vector<int>::iterator pEnd;
    	//交
    	rs.resize(a1.size() + a2.size());
    	pEnd = set_intersection(a1.begin(), a1.end(), a2.begin(), a2.end(), rs.begin());
    	rs.resize(pEnd - rs.begin());
    	//并
    	rs.resize(a1.size() + a2.size());
    	pEnd = set_union(a1.begin(), a1.end(), a2.begin(), a2.end(), rs.begin());
    	rs.resize(pEnd - rs.begin());
    	//差 A-B:属于A且不属于B
    	rs.resize(a1.size() + a2.size());
    	pEnd = set_difference(a1.begin(), a1.end(), a2.begin(), a2.end(), rs.begin());
    	rs.resize(pEnd - rs.begin());
    	//对称差 (A-B)U(B-A):属于A或B但不同时属于A与B
    	rs.resize(a1.size() + a2.size());
    	pEnd = set_symmetric_difference(a1.begin(), a1.end(), a2.begin(), a2.end(), rs.begin());
    	rs.resize(pEnd - rs.begin());
    }

    9. 堆(heap)。头文件<algorithm>。

    struct cmp{ bool operator()(const int& a, const int& b){ return a > b; } };
    void print(vector<int> v){ for (int i= 0; i < v.size(); i++) cout << v[i] << " ";cout<<endl; }
    void f()
    {
    	vector<int> v;
    	v.push_back(4); v.push_back(1); v.push_back(7);			print(v);	
    	make_heap(v.begin(), v.end(), cmp());					print(v);//默认<,大根堆;使用仿函数,小根堆
    	v.push_back(2);	push_heap(v.begin(), v.end(), cmp());	print(v);//先加数据,再push
    	pop_heap(v.begin(), v.end(), cmp());	v.pop_back();	print(v);//先pop,再删数据
    	sort_heap(v.begin(), v.end(), cmp());					print(v);//堆排,不再是堆
    }

     

  • 上一篇: 下一篇:

    我的博客

    NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

    站内搜索

    最新评论