开发技巧

玩转STL模板

C++ STL

Posted by lvyonghao on December 20, 2018

STL模板浅谈

STL简介

STL就是标准模板库，出自惠普实验室开发的一系列软件，目前主要出现在C++当中，就是C++泛型库，数组，字符串，队列，栈堆，链表，二叉树等等都在其中，对我们的学习工作都是大大的有利，为我们节省了很多时间。

STL的代码从广义上来说主要是三大类：algorithm（算法），container（容器），iterator（迭代器）。

STL被组织为以下十三个头文件

algorithm、deque、functional、iterator、vector、list、map、 memory、numeric、queue、set、stack和utility。

算法

STL对数据类型的选择对其可重用性取得了大家的共识，C++的模板机制可以允许真正是用模板或者对模板进行特化的时候进行数据类型的选择，STL就提供了相当多的算法，避免重复写大量的代码。 包含四类算法：排序算法，不可变序算法，变序性算法和数值算法。

算法部分主要在头文件algorithm，numeric，和functional当中。

容器

在实际的开发，或者一些算法的竞赛当中，选择一个合理的数据结构会帮你省下很多时间，但我们总是要重复写一些链表，二叉树，图之类的，还要加上各种遍历，删减或者是运算的函数。STL容器就为我们提供了这样的方便。

容器部分主要由一下几个头文件组成

向量（vector）连续存储数据类似数组

链表（list）由节点组成的双向链表

队列（deque）连续存储的志向不同元素指针所组成的数组，其实就是用双向链表实现的的队列

集合（set）由节点组成的红黑树，这个一般用不上日后会了在更新 多重集合和（multiset）同上

栈（stack）最基本的数据结构之一，符合后进先出的规则存数数据

队列（queue）最基本的数据结构之一，符合先进先出的规则

优先队列（priority_queue）emmm就是对队列的元素进行排列，可以理解为一个有序队列

映射（map）由键值对组成的集合，就是图

多重映射（multimap）允许键值对有相等的的次序映射（了解不深咱且不谈）

迭代器

迭代起的作用是就在STL当中吧算法和容器联系起来，所有的算法都需要通过迭代器才能对元素进行存取，可以理解为一个过度的工具，这部分还是很难理解的。 迭代器的作用就是遍历容器 迭代器部分主要是由头文件utillty，iterator，和memory组成

untility，它包括了使用STL中的几个模板的声明

lterator中提供的是迭代器使用的多种方法

memory 主要为容器中的元素分配存储空间，其中主要部分是allocator，他负责所有容器中的默认分配器

vector向量容器

vector不仅能像数组一样能对元素进行随机访问，还能在尾部插入元素，这样就免去了不知道数组开多大的烦恼，完全可以替代数组。

创建vector对象

  1. 不指定容器的元素个数，如定义一个储存整形的容器：vector<int> v
  2. 创建制定容器大小，如定义一个大小为10的double类型元素容器vector<double> v(10)每个元素被初始为0.0
  3. 创建一个具有n个元素的向量容器对象，每个元素具有指定的初始值vector<double> v(10,8.6)上述语句定义了v向量容器，10个元素，每个元素都是8.6.

尾部扩张

使用push_back()对vector容器在尾部追加新元素。下面将2，7，9三个元素从尾部添加到v容器中，其依次是2，7，9。

#include<vector>
using namespace std;

int main(){
	vector<int> v;
	v.push_back(2);
	v.push_back(7);
	v.push_back(9);
	return 0;
}

下标访问vector元素

方式类似数组。

#include<vector>
#include<iostream>
using namespace std;

int main(){
	vector<int> v(3);
	v[0] = 2;
	v[1] = 7;
	v[2] = 9;
	cout << v[0] << " " << v[1] << " " << v[2] << endl;
	return 0;
}

用迭代器来访问元素

常用迭代器配合循环语句对vecotr对象进行遍历访问，迭代器类型要与vetcor的元素类型一致 线面采用迭代器对vector进行了遍历输出2，7，9。

#include<vector>
#include<iostream>
using namespace std;

int main(){
	vector<int> v(3);
	v[0] = 2;
	v[1] = 7;
	v[2] = 9;
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it!=v.end();it++){
		//输出迭代器的元素值
		cout << *it << " ";	
	} 
	cout << endl;
	return 0;
}

元素的插入

insert（）方法可以在vector对象的任意位置前插入一个新的元素，同时，vector自动扩充一个空间，之后所有的元素都往后移一个位置。 insert（）方法要求插入的位置是元素迭代器位置，而不是元素下标。 下面代码输出的结果是821793。

#include<vector>
#include<iostream>
using namespace std;

int main(){
	vector<int> v(3);
	v[0] = 2;
	v[1] = 7;
	v[2] = 9;
	//在最前面加入新元素为8
	v.insert(v.begin().8);
	//在第二个元素插入1
	v.insert(v.begin()+2,1);
	//在向量末尾追加元素3；
	v.insert(v.end(),3);
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	cout << endl;
	return 0;
}

元素的删除

erase（）方法可以删除迭代器中所指的一个元素或者一段区间的元素。 clear（）方法则一次性删除所有的元素。

#include<vector>
#include<iostream>
using namespace std;

int main(){
	vector<int> v(10);
	for(int i = 0;i < 10; i++){
		v[i] = i;
	}
	//删除2个元素，从0开始计数
	v.erase(v.begin()+2); 
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	cout << endl;
	//删除迭代器第一道第五区间的所有元素
	v.erase(v.begin()+1,v.begin()+5);
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	//清空向量
	v.clear();
	//输出向量大小
	cout << v.size() << endl;
	return 0;
}

使用reverse反向排列算法

reverse反向排列算法，需定义头文件“#include”。 reverse算法可以将向量中某段迭代器区间元素反向排列。

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	vector<int> v(10);
	for(int i = 0;i < 10; i++){
		v[i] = i;
	}
	//反向排列向量首到尾的元素 
	reverse(v.begin(),v.end()); 
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	cout << endl;
	return 0;
}

输出结果9 8 7 6 5 4 3 2 1 0

使用sort算法对向量元素排列

使用sort排列算法，需定义头文件“#include” 默认情况下对向量元素景象升序排列，见下面程序。

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	vector<int> v; 
	int i;
	//赋值 
	for(int i = 0;i < 10; i++){
		v.push_back(9 - i);
	}
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	sort(v.begin(),v.end());
	//再次输出 
	cout << endl;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	return 0;
}

输出结果 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 还可以自己设计排序比较函数，然后把这个函数指定给sort算法。

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

//自己设计的排序比较函数；对元素进行降序排列
bool Comp(const int &a,const int &b)
{
	if(a != b) return a > b;
	else return a > b; 
 } 
int main(){
	vector<int> v; 
	int i;
	//赋值 
	for(int i = 0;i < 10; i++){
		v.push_back(i);
	}
	//定义迭代器变量
	vector<int>::iterator it;
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	cout << endl;
	sort(v.begin(),v.end(),Comp);
	//再次输出 
	for(it = v.begin();it != v.end();it++){
		cout << *it << " ";
	} 
	cout << endl;
	return 0;
}

向量的大小

使用size（)方法返回向量的大小，即元素的个数。 使用empty（）方法返回向量是否为空，返回0或1。 在这里就不进行代码的演示了。

队列容器

queue队列容器是一个先进先出的线性存储表，元素的插入只能在队尾，元素的删除只能在队首。 使用queue需要声明头文件#include<queue> queue队列主要有入队，出队，读取队首元素，读取队尾元素，判断队列是否为空，队列当前元素的数目几种方法,因为方法通用就不单独介绍了，区别在于queu没有clear（）函数也没法使用迭代器，因为它必须满足先进先出的规则。

插入元素push（） 删除元素pop（） 队列长度size（） 队首元素front（） 队尾元素back（） 判断队列是否为空empty返回为bool类型

#include<queue>
#include<iostream>
using namespace std;
 
int main(){
	//定义队列，元素类型是整形
	queue<int> q; 
	//入队，即插入元素
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5); 
	//返回队列长度
	cout << q.size() << endl;
	//队列是否为空，是空，
	cout << q.empty() << endl;
	//读取队首元素
	cout << q.front() << endl; 
	//读取队尾元素
	cout << q.back() << endl;
	//让所有的元素出列（删除所有元素）
	while(q.empty()!=true){
		cout << q.front() << " ";
		//队首元素出列
		q.pop(); 
	} 
	//输出队列元素 
	i = q.size();
	while(i--){
		u = q.front();
		q.pop();
		cout << u << endl;
	}
	return 0;
}

优先队列

priority_queue优先队列容器，和队列一样，它的特性在于，队列中最大的元素总是位于对手，元素的比较鬼子默认认为按照元素的值又到大小排序，可以选择重载‘<’操作符。使用优先队列可以免去自己写排序算法的麻烦。 使用priority_queue需要声明头文件#include<queue>和队列相同。

优先队列的使用方法

优先队列包括出队，入队，读取队首元素以及判断队列是否为空，但是没有读取队尾。

插入元素 push（） 删除队首元素top（） 判断队列是否为空empty（）

#include<queue>
#include<iostream>
using namespace std;
 
int main(){
	//定义优先队列，元素类型为整形
	priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(9);
	//返回队列中元素数目
	cout << pq.size() << endl;
	//返回队列中的首元素
	cout << pq.top() << endl;
	//所有元素出队，删除所有元素
	while(pq.empty() != true) {
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

重载‘<’ ‘（）’操作符来定义优先级

如果优先队列的元素类型是结构体可以通过重载‘<’操作符来修改优先队列的优先性。如果是优先队列的元素不是结构体类型，则可以通过重载‘（）’操作符的方式来定义优先级。这里只介绍队列元素不是结构体类型的因为会经常用到，例如把队列变为从小到大排列的。

#include<queue>
#include<iostream>
using namespace std;
 
int main(){
	//定义优先队列，元素类型为整形
	priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(9);
	//返回队列中元素数目
	cout << pq.size() << endl;
	//返回队列中的首元素
	cout << pq.top() << endl;
	//所有元素出队，删除所有元素
	while(pq.empty() != true) {
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

stack堆栈容器

stack是一个后进后出的线性表，插入和删除的元素都只能在表的一端进行。插入元素的一端称为栈顶，删除元素的一端称为栈底。使用stack必须在头函数声明#include<>stack

stack基本用法

堆栈只提供入栈，出栈，栈顶元素访问和判断是否为空几种方法。同队列，因为结构原因不能使用迭代器进行迭代。

入栈push() 出栈pop() 访问栈顶元素top（） 判断栈是否为空empty()

#include<iostream>
#include<stack>
using namespace std;
int main(){
	//定义堆栈s，其元素类型为整形
	stack<int> s;
	//元素入栈
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(9);
	//读取栈顶元素
	cout << s.top() << " ";
	//返回栈顶元素数量
	cout << s.size() << " ";
	//让所有元素出战
	while(s.empty() != true){
		cout << s.top() << " ";
		s.pop();
	} 
	return 0;
}

list双线链表容器

STL为我们提供了双向链表的数据结构，数据元素是通过链表指针串连成逻辑意义上的线性表，优点是可以对链表任意位置元素进行插入删除查找。list的每个节点有三个域，前去指针域，数据域，后继指针域。由于list在物理地址上并不连续，所以对于迭代器来说只能通过++或————的操作将迭代器移动到后继/前驱的节点元素除。并不能对迭代器进行+n或-n的操作。 使用list需要声明头文件#include<list>

创建链表

  • 创建空链表list<int> l;
  • 创建具有n个元素的链表list<int> l(10)

元素的插入和遍历

插入元素有三种方法

  • 采用push_back()方法向尾部插入元素
  • 采用push_front()方法向首部插入元素
  • 采用insert()方法在迭代器位置处插入新元素。
  •  #include<iostream>
#include<list>
using namespace std;
int main(){
//定义链表list元素类型为整形的空链表
list<int> l;
//在链表尾部插入元素
l.push_back(2);
l.push_back(1);
l.push_back(5);
//在链表头部插入元素
l.push_front(7);
l.push_front(8);
l.push_front(8);
//创建链表迭代器
list<int>::iterator it;
it = l.begin();
it++;//链表迭代器只能进行自增或自减操作
//在链表头节点的下一节点插入元素 
l.insert(it,20);
//使用迭代器遍历链表
for(it = l.begin();it != l.end();it++){
    cout << *it << " ";
} 
return 0;
}

反向遍历

采用反向迭代器reverse_iterator进行反向遍历。

#include<iostream>
#include<list>
using namespace std;
int main(){
	//定义链表list元素类型为整形的空链表
	list<int> l;
	//在链表尾部插入元素
	l.push_back(2);
	l.push_back(1);
	l.push_back(5);
	//在链表头部插入元素
	l.push_front(7);
	l.push_front(8);
	l.push_front(8);
	//创建链表迭代器
	list<int>::reverse_iterator it;
	//使用反向迭代器遍历链表
	for(it = l.rbegin();it != l.rend();it++){
		cout << *it << " ";
	} 
	return 0;
}

元素删除

元素的删除有四种方法，使用remove()删除链表中的一个元素，值相同的元素都会被删除。使用pop_front()方法删除链表首元素，使用pop_back()方法删除链表尾元素。使用erase删除迭代器位置上的元素，可以实现删除指定位置的元素，使用clear()方法请空链表。

  • remove() 
     #include<iostream>
#include<list>
using namespace std;
int main(){
 //定义链表list元素类型为整形的空链表
 list<int> l;
 //在链表尾部插入元素
 l.push_back(2);
 l.push_back(1);
 l.push_back(5);
 //在链表头部插入元素
 l.push_front(7);
 l.push_front(8);
 l.push_front(8);
 //创建链表迭代器
 list<int>::iterator it;
 it = l.begin();
 it++;//链表迭代器只能进行自增或自减操作
 //在链表头节点的下一节点插入元素 
 l.insert(it,20);
 //使用迭代器遍历链表
 for(it = l.begin();it != l.end();it++){
     cout << *it << " ";
 } 
 cout << endl; 
 l.remove(8);
 //删除值为8的元素 
  for(it = l.begin();it != l.end();it++){
     cout << *it << " ";
 }
 return 0;
}
  • pop_front()和pop_back() 
     #include<iostream>
#include<list>
using namespace std;
int main(){
 //定义链表list元素类型为整形的空链表
 list<int> l;
 //在链表尾部插入元素
 l.push_back(2);
 l.push_back(1);
 l.push_back(5);
 //在链表头部插入元素
 l.push_front(7);
 l.push_front(8);
 l.push_front(8);
 //创建链表迭代器
 list<int>::iterator it;
 it = l.begin();
 it++;//链表迭代器只能进行自增或自减操作
 //在链表头节点的下一节点插入元素 
 l.insert(it,20);
 //使用迭代器遍历链表
 for(it = l.begin();it != l.end();it++){
     cout << *it << " ";
 } 
 cout << endl; 
 l.remove(8);
 //删除值为8的元素 
  for(it = l.begin();it != l.end();it++){
     cout << *it << " ";
 }
 return 0;
}
  • erase()
#include<iostream>
#include<list>
using namespace std;
int main(){
	//定义链表list元素类型为整形的空链表
	list<int> l;
	//在链表尾部插入元素
	l.push_back(2);
	l.push_back(1);
	l.push_back(5);
	//在链表头部插入元素
	l.push_front(7);
	l.push_front(8);
	l.push_front(8);
	//创建链表迭代器
	list<int>::iterator it;
	it = l.begin();
	it++;//链表迭代器只能进行自增或自减操作
	//在链表头节点的下一节点插入元素 
	l.insert(it,20);
	//使用迭代器遍历链表
	for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	cout << endl; 
	l.remove(8);
	//删除值为8的元素 
	 for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	}
	return 0;
}
  • clear() 
    #include<iostream>
#include<list>
using namespace std;
int main(){
 //定义链表list元素类型为整形的空链表
 list<int> l;
 //在链表尾部插入元素
 l.push_back(2);
 l.push_back(1);
 l.push_back(5);
 //在链表头部插入元素
 l.push_front(7);
 l.push_front(8);
 l.push_front(8);
 //创建链表迭代器
 list<int>::iterator it;
 it = l.begin();
 it++;//链表迭代器只能进行自增或自减操作
 //在链表头节点的下一节点插入元素 
 l.insert(it,20);
 //使用迭代器遍历链表
 for(it = l.begin();it != l.end();it++){
     cout << *it << " ";
 } 
 cout << endl; 
 //请空链表 
 l.clear();
 cout << l.size() << endl;
 return 0;
}

元素的查找

使用find（）方法可以在链表中查找元素，如果找到该元素，返回该元素在迭代器的位置，如果没找到返回end（）迭代器的位置，就是链表末尾，同样使用find（）方法需要声明头文件#include<algorithm>。find()参数表（起始位置，结束位置，查找的元素）

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main(){
	//定义链表list元素类型为整形的空链表
	list<int> l;
	//在链表尾部插入元素
	l.push_back(2);
	l.push_back(1);
	l.push_back(5);
	//在链表头部插入元素
	l.push_front(7);
	l.push_front(8);
	l.push_front(8);
	//创建链表迭代器
	list<int>::iterator it;
	it = l.begin();
	it++;//链表迭代器只能进行自增或自减操作
	//在链表头节点的下一节点插入元素 
	l.insert(it,20);
	//使用迭代器遍历链表
	for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	cout << endl; 
	//采用find（）查找算法在链表中查找
	it = find(l.begin(),l.end(),10);
	if(it != l.end()){
		cout << "find it" << endl;
	} 
	else
	{
		cout << "not find it" << endl; 
	}
	it = find(l.begin(),l.end(),2);
	if(it != l.end()){
		cout << "find it" << endl;
	} 
	else
	{
		cout << "not find it" << endl; 
	}
	return 0;
}

元素排序

采用sort()方法可以对链表元素进行升序排列

#include<iostream>
#include<list>
using namespace std;
int main(){
	//定义链表list元素类型为整形的空链表
	list<int> l;
	//在链表尾部插入元素
	l.push_back(2);
	l.push_back(1);
	l.push_back(5);
	//在链表头部插入元素
	l.push_front(7);
	l.push_front(8);
	l.push_front(8);
	//创建链表迭代器
	list<int>::iterator it;
	it = l.begin();
	it++;//链表迭代器只能进行自增或自减操作
	//在链表头节点的下一节点插入元素 
	l.insert(it,20);
	//使用迭代器遍历链表
	for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	cout << endl; 
	//排序
	l.sort();
	 for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	return 0;
}

剔除重复元素

采用方法unique()方法可提出连续重复元素，只保留一个，一般情况用不到。

#include<iostream>
#include<list>
using namespace std;
int main(){
	//定义链表list元素类型为整形的空链表
	list<int> l;
	//在链表尾部插入元素
	l.push_back(2);
	l.push_back(1);
	l.push_back(8);
	//在链表头部插入元素
	l.push_front(8);
	l.push_front(8);
	l.push_front(8);
	//创建链表迭代器
	list<int>::iterator it;
	it = l.begin();
	it++;//链表迭代器只能进行自增或自减操作
	//在链表头节点的下一节点插入元素 
	l.insert(it,20);
	//使用迭代器遍历链表
	for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	cout << endl; 
	//排序
	l.unique();
	 for(it = l.begin();it != l.end();it++){
		cout << *it << " ";
	} 
	return 0;
}

其他容器还有bitset位集合容器，multmap多重映照容器，multiset多重集合容器，set集合容器，这里就不一一进行介绍了。

CATALOG
    FEATURED TAGS
    ACM 开发技巧 数据结构 SSM框架 Java
    FRIENDS