【C++】STL应用

【C++】STL应用

目录

实验要求

 实验内容

1 什么是STL？

STL中六大组件：

容器

STL迭代器

 结合容器和迭代器解决序列变换（如取反、平方、立方）

 结合容器和迭代器解决像素变换

用set存储学生信息，并进行增删改查 *** 作

Set的增删改查

用map统计每个输入字符出现的次数并输出字符及对应的次数。 

实验总结

verctor

list

deque

map

multimap

set

multiset

 在实际使用过程中，到底选择这几种容器中的哪一个，应该根据遵循以下原则：

---

实验要求

• 撰写自己的算法和函数，结合容器和迭代器解决序列变换（如取反、平方、立方），像素变换（二值化、灰度拉伸）；
• 用set存储学生信息，并进行增删改查 *** 作；
• 输入一个字符串，用map统计每个字符出现的次数并输出字符及对应的次数。

 实验内容 1 什么是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是以一种类型参数化的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。

STL中六大组件：

        容器（Container），是一种数据结构，如list，vector，和deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；
        迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的 *** 作符地方法的类对象；
        算法（Algorithm），是用来 *** 作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们 *** 作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；
        仿函数（Functor）
        适配器（Adaptor）
        分配器（allocator）

容器

STL中的容器有队列容器和关联容器，容器适配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。
（1）序列式容器（Sequence containers），每个元素都有固定位置－－取决于插入时机和地点，和元素值无关，vector、deque、list；
       Vector：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；
       Deque：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；
       List：双向链表，不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；
（2）关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap等。
       Set/Multiset：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找；
       Map/Multimap：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找；

容器类自动申请和释放内存，无需new和delete *** 作。

STL迭代器

         Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

        迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以 *** 作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator.

 结合容器和迭代器解决序列变换（如取反、平方、立方）

先写一个取反的模板函数

//对数组取反的函数模板（开始使用模板）
template
void transInvT(T a[], T b[], int nNum)
{
	for (int i = 0; i < nNum; i++)
	{
		b[i] = -a[i];
	}
}

计算平方的模板函数

//求平方
template
void transSqr(T a[], T b[], int nNum)
{
	for (int i = 0; i < nNum; i++)
	{
		b[i] = a[i] * a[i];
	}
}

输出函数

//输出的函数模板
template < typename T>
void outputCont(string strNme, ostream& os, T begin, T end)
{
	os << strNme << "：";
	for (; begin != end; begin++)
	{
		os << *begin << " ";
	}
	os << endl;
}

transInvT算法

template 
void transInvT(inputIter begInput, inputIter endInput,
			   outputIter begOutPut, MyOperator op)
{
	for (; begInput != endInput; begInput++, begOutPut++)
	{
		 //*begOutPut = ‐ (*begInput); 
		//改为函数的形式，就不需要对取反、平方等每一个算法重写一个函数
		*begOutPut = op(*begInput); 
	}
}

开始测试

void Test()
{
	//TestMap();
	//TestSet();
	//TestVector();

	const int N = 5;
	int a[N] = { 1,2,4,3,5 };
	//输出a
	outputCont("a", cout, a, a + N);

	//存储变换后的数组
	int b[N];
	//Vector（向量）是一个封装了动态大小数组的顺序容器（Sequence Container）,跟任意其它类型容器一样，
	//它能够存放各种类型的数据。可以简单的认为，向量是一个能够存放任意类型的动态数组
	vector vb(N);
	//对数组中的元素取反
	transInv(a, b, N);
	outputCont("Inv a", cout, b, b + N);
	//对数组中的元素取求平方
	transSqr(a, b, N);
	outputCont("Sqr a", cout, b, b + N);
	//对数组元素取反（使用模板）
	transInvT(a, b, N);
	outputCont("Inv a T", cout, b, b + N);

	transInvT(a, a + N, b);
	transInvT(a, a + N, vb.begin());
	transInvT(a, a + N, b, InvT);
	transInvT(a, a + N, vb.begin(), InvT);
	outputCont("Inv a by iter", cout, vb.begin(), vb.end());
}

运行结果

 结合容器和迭代器解决像素变换

template
class MyThreshold {
public:
	//带参构造函数，后面的则是初始化，这样的初始化方式效率比较高
	MyThreshold(int n = 128) : _nThreshold(n)
	{

	}
	int operator()(T val)
	{
		return val < _nThreshold ? 0 : 1;
	}
	int _nThreshold;
};

 测试函数

void Test()
{
    transInvT(a, a + N, vb.begin(), MyThreshold(2));
	outputCont("Inv a by treshold", cout, vb.begin(), vb.end());

}

运行结果

由于MyThreshold(2)设定阈值为2，则1会变为0大于等于2的都会输出1。 

用set存储学生信息，并进行增删改查 *** 作

        set 的特性是，所有元素都会根据元素的键值自动被排序，set 只拥有一个元素，它的键值就是实值，实值就是键值，并且set 不允许两个元素有相同的键值。

        首先构建studentInfo类，其中有一个构造函数，学号和姓名两个变量，还有两个对运算符的重载，一个是为了输出，一个是为了比较学号的大小以便于排序。

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;

	}
};

        接着用容器vector创建一个students对象，将学生信息存储在vector当中，再通过遍历vector将其存储在set当中。

#include 

#include 
#include 
using namespace std;
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;
}


int main(int argc, char** argv) {

	vector students;
	students.push_back(studentInfo("101", "小马"));
	students.push_back(studentInfo("104", "小明"));
	students.push_back(studentInfo("106", "小庞"));
	students.push_back(studentInfo("108", "小林"));
	students.push_back(studentInfo("109", "李华"));
	set studentSet(students.begin(), students.end());
	outputCont("student set", cout, studentSet.begin(), studentSet.end());

	return 0;
}

        运行结果

        由于set关联式容器性质，所有元素都会根据元素的键值自动被排序，因此我们可以看到学生信息已经按升序的方式排好了序

Set的增删改查

增：insert(a) 插入某个元素，因为set有序，所以怎么插入无所谓
删：erase(it) 该函数用于根据元素的值或元素在集合中的迭代器位置来擦除它
改：set的迭代器it有const修饰符,那么对它元素的修改就必然不能成功了。
查：find用于检查元素是否属于集合，如果元素在集合容器中找到，则返回指向该元素的迭代器。否则返回set.end()
 

int main(int argc, char** argv) {

	vector students;
	students.push_back(studentInfo("101", "小马"));
	students.push_back(studentInfo("104", "小明"));
	students.push_back(studentInfo("106", "小庞"));
	students.push_back(studentInfo("108", "小林"));
	students.push_back(studentInfo("109", "李华"));
	set studentSet(students.begin(), students.end());
	outputCont("student set", cout, studentSet.begin(), studentSet.end());
		//增 insert(a) 插入某个元素  set有序，所以怎么插入无所谓
	studentSet.insert(studentInfo("100", "小红"));
	outputCont("student set insret", cout, studentSet.begin(), studentSet.end());
	//删 erase(it) 该函数用于根据元素的值或元素在集合中的迭代器位置来擦除它
	studentSet.erase(studentInfo("109", "李华"));
	outputCont("student set erase", cout, studentSet.begin(), studentSet.end());
	//改，set的迭代器it有const修饰符,那么对它元素的修改就必然不能成功了。
	//查 find用于检查元素是否属于集合，如果元素在集合容器中找到，则返回指向该元素的迭代器。否则返回set.end()
	//set::iterator it = studentSet.find(studentInfo("10010", "WuLiu"));
	if (studentSet.find(studentInfo("106", "小庞")) != studentSet.end())
	{
		cout << "find it!" << endl;
	}
	else
	{
		cout << "not found!" << endl;
	}

	return 0;
}

         运行结果

 

用map统计每个输入字符出现的次数并输出字符及对应的次数。 

        Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

实现代码

int main(int argc, char** argv) {

	map s;   //用来存储字母出现次数的映射
	char c;				//存储输入字符
	do {
		cin >> c;//输入下一个字符
		if (isalpha(c))//判断是否是字母
		{
			c = tolower(c);//将字母转换为小写
			s[c]++;//将该字母的出现频率加1
		}
	} while (c != '.');//碰到“.”则结束输入
		//输出每个字母出现次数
	for (map::iterator iter = s.begin(); iter != s.end(); ++iter)
		cout << iter->first << "" << iter->second << " ";
	cout << endl;
	return 0;
}

运行结果

 可以看到map关联容器统计每个输入字符出现的次数效果非常，代码简洁好用。

实验总结 verctor

vector类似于C语言中的数组，它维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] *** 作符，但因为它的内存区域是连续的，所以在它中间插入或删除某个元素，需要复制并移动现有的元素。此外，当被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是，vector每次扩容为原来的两倍，对小对象来说执行效率高，但如果遇到大对象，执行效率就低了。

list

list类似于C语言中的双向链表，它通过指针来进行数据的访问，因此维护的内存空间可以不连续，这也非常有利于数据的随机存取，因而它没有提供 [] *** 作符重载。

deque

deque类似于C语言中的双向队列，即两端都可以插入或者删除的队列。queue支持 [] *** 作符，也就是支持随机存取，而且跟vector的效率相差无几。它支持两端的 *** 作：push_back,push_front,pop_back,pop_front等，并且在两端 *** 作上与list的效率
也差不多。或者我们可以这么认为，deque是vector跟list的折中。

map

map类似于数据库中的１:１关系，它是一种关联容器，提供一对一(C++ primer中文版中将第一个译为键，每个键只能在map中出现一次，第二个被译为该键对应的值)的数据处理能力，这种特性了使得map类似于数据结构里的红黑二叉树。

multimap

multimap类似于数据库中的１:Ｎ关系，它是一种关联容器,提供一对多的数据处理能力。

set

set类似于数学里面的集合，不过set的集合中不包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。

multiset

multiset类似于数学里面的集合，集合中可以包含重复的元素。

 在实际使用过程中，到底选择这几种容器中的哪一个，应该根据遵循以下原则：

• 如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；
• 如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；
• 如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；
• 如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；
• 如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。