STL
实验环境
操作系统：win10
gcc：8.1.0
开发软件：qt5.14.2
STL简介
STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；
STL另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效；
从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；
从实现层次看，整个STL是以一种类型参数化的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性–模板（template）。
简而言之，STL是具有通用性的标准模板库，比如当我们有时要在程序中用到堆、栈、队列、链表等一些基本的算法，而你又实在不想自己去实现数据结构教科书中那些繁琐的算法，那么你就可以考虑使用STL，另外，STL作为一种标准，便于交流，掌握它，一方面可以让你写的程序，易于让别人理解，另一方面你也能够比较容易地理解别人写的程序。
其中使用STL还需要主要注意以下三个概念
- 容器：可以把它理解为存放数据的地方，常用的一些容器有 链表(list) 栈(stack) 动态数组 (vector) 双端队列(deque) 队列(queue) 映射(map)
- 迭代器(iterator)：可以把它理解为指针类型，STL中的许多函数需要用到它们作为参数
- 算法：它们通常需要与容器和游标配合使用，使用它们，你可以方便地对容器中的数据进行各种常见的操作，如排序操作，寻找最大元素的操作等
实例——序列与像素变换
那么在了解了STL的基本概念后，让我们实际试着使用一下STL来完成两个小的例子，即序列与像素的变换。
首先是自己编写函数实现对序列的求反，求平方和求立法，由于这部分比较简单，就只给出函数部分。
void transInv(int a[],int b[],int nNum) //对元素取反
{
for(int i=0;i<nNum;i++)
{
b[i] = -a[i];
}
}
void transSqr(int a[],int b[],int nNum) //对元素求平方
{
for(int i=0;i<nNum;i++)
{
b[i] = a[i]*a[i];
}
}
void transPow(int a[],int b[],int nNum) //对元素求立方
{
for(int i=0;i<nNum;i++)
{
b[i] = a[i]*a[i]*a[i];
}
}
然后接下来使用模板函数实现
template <typename T>
void transInvT(T a[],T b[],int nNum) //对元素取反
{
for(int i=0;i<nNum;i++)
{
b[i] = -a[i];
}
}
template <typename T>
void transSqrT(T a[],T b[],int nNum) //对元素求平方
{
for(int i=0;i<nNum;i++)
{
b[i] = a[i]*a[i];
}
}
template <typename T>
void transPow(T a[],T b[],int nNum) //对元素求立方
{
for(int i=0;i<nNum;i++)
{
b[i] = a[i]*a[i]*a[i];
}
}
template<typename T>
T InvT(T a)
{
return -a;
}
template <typename inputIter,typename outputIter,typename MyOperator>
void transInvT(inputIter begInput,inputIter endInput,outputIter begOutput,MyOperator op) //对元素取反
{
for(;begInput!=endInput;begInput++,begOutput++)
{
*(begOutput) = op(*begInput);
}
}
template <typename T>
void outputCont(string strName,ostream& os,T begin,T end) //输出元素
{
os<<strName<<":";
for(;begin!=end;begin++)
{
os<<*begin<<"\t";
}
os<<endl;
};
事实上上面的举得例子所运用的知识点在前几次的实验中都有涉及，这里不做太多的注释，下面写一个小的测试函数并试着运行来验证上面的结果。
const int N=5;
int a[N] = {1,2,3,4,5};
outputCont("a",cout,a,a+N);
int b[N];
vector<double> vb(N); //容器
transInv(a,b,N);
outputCont("Inv a",cout,b,b+N);
transSqr(a,b,N);
outputCont("Sqr a",cout,b,b+N);
transPow(a,b,N);
outputCont("Pow a",cout,b,b+N);
transInvT(a,b,N);
outputCont("InvT a",cout,b,b+N);
transSqrT(a,b,N);
outputCont("SqrT a",cout,b,b+N);
transInvT(a,a+N,b,InvT<int>);
outputCont("InvT a",cout,b,b+N);
transInvT(a,a+N,vb.begin(),InvT<int>); //容器
outputCont("InvT a(vector)",cout,vb.begin(),vb.end()); //容器
transInvT(a,a+N,vb.begin(),MyThreshold<int>(2));
outputCont("InvT a by treshold",cout,vb.begin(),vb.end());
上面的例子中需要注意的是最后四行；其中最后两行其实用到了下面的函数
template<typename T>
class MyThreshold
{
public:
int _nThreshold;
MyThreshold(int n=128):_nThreshold(n){}
int operator()(T val)
{
return val<_nThreshold?0:1; //小于_nThreshold返回0
}
}
即这个过程是近似于二值化的像素变换。在这里的体现就是大于1为1反之为0。
transInvT(a,a+N,vb.begin(),InvT<int>); //容器
outputCont("InvT a(vector)",cout,vb.begin(),vb.end()); //容器
而上面的两行则应用到了容器的概念；上面有提到，下面顺带给出STL中vector的自带函数
v.capacity(); //容器容量
v.size(); //容器大小
v.at(int idx); //用法和[]运算符相同
v.push_back(); //尾部插入
v.pop_back(); //尾部删除
v.front(); //获取头部元素
v.back(); //获取尾部元素
v.begin(); //头元素的迭代器
v.end(); //尾部元素的迭代器
v.insert(pos,elem); //pos是vector的插入元素的位置
v.insert(pos, n, elem) //在位置pos上插入n个元素elem
v.insert(pos, begin, end);
v.erase(pos); //移除pos位置上的元素，返回下一个数据的位置
v.erase(begin, end); //移除[begin, end)区间的数据，返回下一个元素的位置
v.reverse(pos1, pos2); //将vector中的pos1~pos2的元素逆序存储
在最后给出上面的例子的实际运行截图
实例——使用set构建存储信息
在这一部分中，将使用容器类set进行学生信息存储的小例子，set是STL中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。set，顾名思义是“集合”的意思，在set中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交,差，并，对称差等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用multiset。
为了方便理解，下面先给出一些常用的set自带函数
s.begin(); //返回set容器的第一个元素
s.end(); //返回set容器的最后一个元素
s.clear(); //删除set容器中的所有的元素
s.empty(); //判断set容器是否为空
s.insert(); //插入一个元素
s.erase(); //删除一个元素
s.size(); //返回当前set容器中的元素个数
那么接下来进入实例
首先完成本次实验所要求的实验信息类的构建
class studentInfo
{
public:
studentInfo(string strNo, string strName)
{
_strNo = strNo;
_strName = strName;
}
string _strNo;
string _strName;
friend ostream& operator<<(ostream& os, const studentInfo& info)
{
os << info._strNo << " " << info._strName;
return os;
}
friend bool operator<(const studentInfo& info1, const studentInfo& info2) {
return info1._strNo < info2._strNo;
}
};
//输出的函数模板
template < typename T>
void outputCont(string strNme, ostream& os, T begin, T end)
{
os << strNme << "：";
for (; begin != end; begin++)
{
os << *begin << " |";
}
os << endl;
}
这边简单解释一下上面的代码，实现了一个包含学生姓名和学号的学生类，并包含两个重载用于输出和排序比较。
实际上是很简单的例子，接下来试着写一个测试函数对上面提到的常用set函数进行测试。
vector<studentInfo> students;
students.push_back(studentInfo("1", "aa"));
students.push_back(studentInfo("2", "bb"));
students.push_back(studentInfo("3", "cc"));
students.push_back(studentInfo("4", "dd"));
students.push_back(studentInfo("5", "ee"));
set<studentInfo> studentSet(students.begin(), students.end());
outputCont("origin", cout, studentSet.begin(), studentSet.end());
studentSet.insert(studentInfo("6", "ff"));
outputCont("after insret", cout, studentSet.begin(), studentSet.end());
studentSet.erase(studentInfo("3", "cc"));
outputCont("after erase", cout, studentSet.begin(), studentSet.end());
stuTemp.strName = "dd";
stuTemp.strNo = "6";
iter = studentSet.find(stuTemp);
if(iter != studentSet.end()) {
cout << (*iter).strName<< endl;
} else {
cout << "Cannot fine the student!" << endl;
}
return 0;
上面的例子简单的测试set中的insret，erase和find三个函数的使用效果。显而易见的是，这可以组成一个简单的增删改查的demo。接下来贴上实际运行的测试截图
实例——使用map统计字符串中字符数量
map是关联容器之一,存储的都是 pair 对象（键值对）。其中，各个键值对的键和值可以是任意数据类型，包括C++基本数据类型（char、int、double 等）、自定义的结构体或类，键的值既不能重复也不能被修改。
有映射的功能,采用红黑树,自动按照键值排序。根据键的大小对所有键值对做升序排序。当然，根据实际情况的需要，我们可以手动指定map容器的排序规则，既可以选用STL标准库中提供的其它排序规则，也可以自定义排序规则。
依照惯例给出map常用函数
begin() 返回指向map头部的迭代器
clear() 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
接下来是一个简单的demo
void test()
{
map<char, int> str; //用来存储字母出现次数的映射
string test("thisisastringfortest");
for(int i=0;i<test.length();i++)
{
if(str.find(test[i])==str.end())
{
str[test[i]]=1;
}
else
{
str[test[i]]++;
}
}
for(auto i:str)
{
cout<<i.first<<": "<<i.second<<" ";
}
return 0;
}
需要补充的是，frist和second分别指的是map的键和map的值；下面看一下实际运行结果。
补充——红黑树
上面有提到，set和map的实现都是基于红黑树的，那么什么是红黑树呢？红黑树的英文是“Red-Black Tree”，简称 R-B Tree，它是一种不严格的平衡二叉查找树，示意图如下
红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据（图中将黑色的、空的叶子节点都省略掉了）；
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
以上解释摘自下博客，如果有需要了解的可以移步
https://blog.csdn.net/xiaofeng10330111/article/details/106080394