C++STL的基本学习(二)——STL各个容器

前言

上一篇文章我们将C++的一些规矩都学了学,今天我们开始正式的STL学习,函数上我不会记录的很详细,因为有文档可以查,所以没必要。我这里主要记录一些需要注意的点。

这里分享一下STL文档

链接:https://pan.baidu.com/s/1ftRyWOTjsjg9zxACnrTrzg
提取码:u2sl

 

 

 

 


STL理论基础

基本概念

STL(Standard Template Library,标准模板库)

既然是模板库,自然是基于模板实现的

STL从广义上分为三个概念:

  1. 容器(container)
  2. 算法(algorithm)
  3. 迭代器(iterator)

STL优点:

  1. STL是C++的一部分,因此不需要额外安装什么,它被内建在你的编译器之内
  2. STL的一个重要特点是数据结构和算法的分离,尽管这是个简单概念,但是这种分离确实使得STL变得非常通用。即Vector可以用来放入各种元素,而sort()函数可以用来操作vector、list等容器。
  3. 程序员可以不用思考STL具体的实现过程,只要熟练使用了STL就OK了

 

容器、算法、迭代器

  • 容器:承载很多元素的数据结构,另外容器还可以嵌套容器
    • 序列式容器:容器的元素的位置是由进入容器时机和地点来决定的
    • 关联式容器:容器已经有规则,进入容器的元素的位置不是由时机和地点决定
  • 迭代器:可以理解为容器内部的一个指针(对指针的基本操作都可以对迭代器操作),但是实际上,迭代器是一个类对象,这个类封装一个指针。
  • 算法:通过有限的步骤去解决问题

 

STL设计思想

写容器的人提供 迭代器;

写算法的人利用 迭代器;

实现容器与算法分开处理案例:

//算法:负责统计某个元素的个数
int myCount(int* begin,int* end,int val) {
	int temp = 0;
	while (begin != end) {
		if (*begin == val) {
			temp++;
		}
		begin++;
	}
	return temp;
}

int main() 
{
	//数组 容器
	int arr[] = { 0,7,5,4,9,2,0 };
	//指向开始元素位置
	int* pBegin = arr;
	//指向末尾元素的下一个元素的位置
	int* pEnd = arr+sizeof(arr)/sizeof(int);
	cout<<myCount(pBegin,pEnd,0);

	return 0;
}

 


学习STL

简单使用

void PrintVector(int v) {
	cout << v<<" "<<endl;
}

//STL基本语法
void test() {
	//定义一个向量容器,并且指定存放的元素类型是int
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

	//通过STL提供的算法for_each算法
	//容器提供迭代器(begin方法返回迭代器)
	vector<int>::iterator pBegin=v.begin();
	vector<int>::iterator pEnd=v.end();
	//遍历时需要使用回调函数进行具体操作
	for_each(pBegin, pEnd, PrintVector);
}
int main() 
{
	test();
	return 0;
}

10
20
30
40

 

string容器

string是我们的老朋友了,但它也是一个STL容器

string和char*(C风格字符串)对比:

  • char*是一个指针,string是一个类:string封装了char*,管理这个字符串,是一个char*型的容器
  • string封装了很多使用的成员方法:查找 find、拷贝 copy、删除 delete、替换 replace、插入 insert
  • 不用考虑内存释放和越界:string 管理 char*所分配的内存,每一次string的复制,取值都由string类负责维护。

函数:

Constructors 构造函数,用于字符串初始化
Operators 操作符,用于字符串比较和赋值
append() 在字符串的末尾添加文本
assign() 为字符串赋新值
at() 按给定索引值返回字符,溢出会抛异常:out_of_range
begin() 返回一个迭代器,指向第一个字符
c_str() 将字符串以C字符数组的形式返回
capacity() 返回重新分配空间前的字符容量
compare() 比较两个字符串
copy() 将内容复制为一个字符数组
data() 返回内容的字符数组形式
empty() 如果字符串为空,返回真
end() 返回一个迭代器,指向字符串的末尾。(最后一个字符的下一个位置)
erase() 删除字符
find() 在字符串中查找字符
find_first_of() 查找第一个与value中的某值相等的字符
find_first_not_of() 查找第一个与value中的所有值都不相等的字符
find_last_of() 查找最后一个与value中的某值相等的字符
find_last_not_of() 查找最后一个与value中的所有值都不相等的字符
get_allocator() 返回配置器
insert() 插入字符
length() 返回字符串的长度
max_size() 返回字符的最大可能个数
rbegin() 返回一个逆向迭代器,指向最后一个字符
rend() 返回一个逆向迭代器,指向第一个元素的前一个位置
replace() 替换字符
reserve() 保留一定容量以容纳字符串(设置capacity值)
resize() 重新设置字符串的大小
rfind() 查找最后一个与value相等的字符(逆向查找)
size() 返回字符串中字符的数量
substr() 返回某个子字符串
swap() 交换两个字符串的内容

 

vector容器

vector,我喜欢叫它向量,是一个可以动态增长的数组

动态数组实现原理

vector是一个“单口容器”,即数据被pushback只能被放在vector的尾部,pop_back只能弹出最尾部的元素,很明显,这是一个“序列式容器”。

听起来是个“栈”?不不不,vector提供的迭代器和反向迭代器可以让你对vector中任意的元素操作,只不过pushback和pop_back针对尾部而已。

vector实现动态增长基本原理:

当插入新元素的时候,如果空间不足,那么vector会申请一块更大的内存空间,然后将原空间数据拷贝到新空间,释放旧空间的数据,再把新元素插入新申请空间。(默认增长策略是申请两倍的空间)

 

vector函数

Constructors 构造函数
Operators 对vector进行赋值或比较
assign() 对Vector中的元素赋值
at() 返回指定位置的元素
back() 返回最末一个元素
begin() 返回第一个元素的迭代器
capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下)
clear() 清空所有元素
empty() 判断Vector是否为空(返回true时为空)
end() 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
erase() 删除指定元素
front() 返回第一个元素
get_allocator() 返回vector的内存分配器
insert() 插入元素到Vector中
max_size() 返回Vector所能容纳元素的最大数量(上限)
pop_back() 移除最后一个元素
push_back() 在Vector最后添加一个元素
rbegin() 返回Vector尾部的逆迭代器
rend() 返回Vector起始的逆迭代器
reserve() 设置Vector最小的元素容纳数量
resize() 改变Vector元素数量的大小
size() 返回Vector元素数量的大小
swap() 交换两个Vector

 

swap()函数

其中swap()的交换原理并不是数据重新拷贝,借助第三块内存交换,而是Vector对象中有一个指针维护这个对象的内存,交换的时候只是这两个对象的指针指向变了而已。

void test() {
	vector<int> a(5,10);
	vector<int>::iterator it = a.begin();
	cout << &it<<endl;

	vector<int> b(5, 12);
	vector<int>::iterator it2 = b.begin();
	cout << &it2 << endl;

	a.swap(b);
	it = a.begin();
	it2 = b.begin();
	cout << &it << endl;
	cout << &it2 << endl;
}

可以测试一下,你会发现swap后,begin()迭代器的地址还是没有变化,说明数据的地址没有变。

另外,添加元素时,Vector可以自动扩容,但是在删除元素时,Vector却不会减少:

void test() {
	vector<int> v;
	for (int i = 0; i < 10000; i++) {
		v.push_back(i);
	}
	cout<<"元素数量:"<<v.size()<<endl
		<<"容量:"<<v.capacity()<<endl;
	cout << "弹出——————" << endl;
	v.resize(10);
	cout << "元素数量:" << v.size() << endl
		<< "容量:" << v.capacity() << endl;
}

元素数量:10000
容量:12138
弹出——————
元素数量:10
容量:12138

我们可以利用Swap来进行收缩:

	//收缩空间
	/* vector<int>(v):利用v来创建一个匿名对象
	   然后调用swap,
	   这样匿名对象内部指针指向了原来v的空间
	   v内部的指针指向了匿名对象的空间
	   语句结束之后匿名对象销毁(原v的空间释放)
	   从此v指向了新空间,也就实现了缩容
	*/
	vector<int>(v).swap(v);
	cout << "元素数量:" << v.size() << endl
		<< "容量:" << v.capacity() << endl;

vector<int>(v):利用v来创建一个匿名对象
然后调用swap,
这样匿名对象内部指针指向了原来v的空间
v内部的指针指向了匿名对象的空间
语句结束之后匿名对象销毁(原v的空间释放)
从此v指向了新空间,也就实现了缩容。

reserve()函数

reserve:储备、预留

reserve() 和 resize() 的区别?

reserve 是容器预留空间,但在空间内不真正创建元素对象,所以在没有添加新的对象之前,不能引用容器内的元素;resize是改变容器的大小,且在创建对象,因此,调用这个函数之后,就可以引用容器内的对象了。

void test() {
	vector<int> v;
	v.reserve(100000);
	int num = 0;
	int* address = NULL;
	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
		//堆加元素的时候,首地址变化了几次
		if (address != &(v[0])) {
			address = &(v[0]);
			num++;
		}
	}
	cout << num;
	//如果你知道容器大概要存储的容器个数
	//那么可以利用reserve预留空间
}

打印num的值是1。

如果你没有reserve空间,那么堆加100000个数据的时候会变化29次空间(num为30),即扩容29次,如果你预留好了100000个空间,那么就一开始就不需要因为自动扩容而变化地址,提高了效率。

 

 

deque容器

deque就是“Double Ended Queues

即“双向队列”

deque类似于vector,但是我们知道,vector是一个单口容器,而deque则是一个双口容器。

deque存在的主要原因是因为vector(单向开口)对于头部插入和删除效果很差,从效率方面考虑,所以出现了deque(双向开口)。

可用API

Constructors 创建一个新双向队列
Operators 比较和赋值双向队列
assign() 设置双向队列的值
at() 返回指定的元素
back() 返回最后一个元素
begin() 返回指向第一个元素的迭代器
clear() 删除所有元素
empty() 返回真如果双向队列为空
end() 返回指向尾部的迭代器
erase() 删除一个元素
front() 返回第一个元素
get_allocator() 返回双向队列的配置器
insert() 插入一个元素到双向队列中
max_size() 返回双向队列能容纳的最大元素个数
pop_back() 删除尾部的元素
pop_front() 删除头部的元素
push_back() 在尾部加入一个元素
push_front() 在头部加入一个元素
rbegin() 返回指向尾部的逆向迭代器
rend() 返回指向头部的逆向迭代器
resize() 改变双向队列的大小
size() 返回双向队列中元素的个数
swap() 和另一个双向队列交换元素

 

deque打分案例

#include <iostream>
#include<string>
#include<iomanip>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;

/*评委打分案例(sort 算法排序)
  创建5个选手(姓名、得分),10个评委对5个选手进行打分
  得分规则:去掉最高分。去掉最低分,取出平均分
  按得分对5名选手进行排名
*/
class Player {
public:
	Player() {};
	Player(string name, int score)
		:mName(name),mScore(score) {}
public:
	string mName;
	int mScore;
};
//创建选手
void CreatePlayer(vector<Player> &v) {
	string nameSeed = "ABCDE";
	for (int i = 0; i < 5; i++) {
		Player p;
		p.mName = "选手";
		p.mName += nameSeed[i];
		p.mScore = 0;

		v.push_back(p);
	}
}
void PrintScore(int a) {
	cout << a << "\t";
}
//打分
void SetScore(vector<Player> &v) {
	for (vector<Player>::iterator it = v.begin();
		it != v.end(); it++) {
		//当前学生进行打分
		deque<int> dScore;
		for (int i = 0; i < 10; i++) {
			int score = rand() % 41+60;
			dScore.push_back(score);
		}
		//对分数进行排序(参数是区间),默认升序
		sort(dScore.begin(),dScore.end());
		for_each(dScore.begin(), dScore.end(), PrintScore);
		cout << endl;

		//去除最高分、去除最低分
		dScore.pop_front();
		dScore.pop_back();

		//求平均分
		int totalScore = 0;
		for (deque<int>::iterator dit = dScore.begin();
			dit < dScore.end(); dit++) {
			totalScore += (*dit);
		}
		int avgScore = totalScore / dScore.size();

		(*it).mScore = avgScore; 
	}
}
//排序规则,定义排序规则
bool mycompare(Player p1,Player p2) {
	return p1.mScore > p2.mScore;
}
//根据选手分数进行排序,降序排列
void PrintRank(vector<Player> &v) {
	//排序(使用自定义规则)
	sort(v.begin(), v.end(), mycompare);
	//打印
	for (vector<Player>::iterator it = v.begin(); 
		it != v.end(); it++) {
		cout << "姓名:" << (*it).mName <<
                    " 得分:" << (*it).mScore << endl;
	}
}
int main() 
{
	//定义vector容器,保存选手信息
	vector<Player> PList;
	CreatePlayer(PList);
	SetScore(PList);
	PrintRank(PList);
	return 0;
}

 

 

stack容器

stack——栈

先进后出

栈不能遍历,并且不支持指定存取

栈不提供迭代器

 

queue队列

queue——队列

先进先出

队列也不能遍历,并且不支持指定存取

队列也不提供迭代器

 

List链表

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢.

这个链表和数据结构的链表是一回事,链表是由一系列的结点组成,结点包含两个域,一个数据域,一个指针域,链表的数据在内存中是非连续的方式存放的,添加和删除元素,时间复杂度都是常数项(因为不需要大动干戈的移动元素了)。

 

常用API

assign() 给list赋值
back() 返回最后一个元素
begin() 返回指向第一个元素的迭代器
clear() 删除所有元素
empty() 如果list是空的则返回true
end() 返回末尾的迭代器
erase() 删除一个元素
front() 返回第一个元素
get_allocator() 返回list的配置器
insert() 插入一个元素到list中
max_size() 返回list能容纳的最大元素数量
merge() 合并两个list
pop_back() 删除最后一个元素
pop_front() 删除第一个元素
push_back() 在list的末尾添加一个元素
push_front() 在list的头部添加一个元素
rbegin() 返回指向第一个元素的逆向迭代器
remove() 从list删除元素
remove_if() 按指定条件删除元素
rend() 指向list末尾的逆向迭代器
resize() 改变list的大小
reverse() 把list的元素倒转
size() 返回list中的元素个数
sort() 给list排序
splice() 合并两个list
swap() 交换两个list
unique() 删除list中重复的元素

大小操作

size():返回容器中元素的个数

empty():判断容器是否为空

resize(num):重新制定容器的长度为num,若容器变长,则以默认值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。

resize(num,elem):重新制定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。

 

对组

对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公有函数first和second访问。

类模板:template<class T1,class T2> struct pair;

	//构造方法
	pair<string, int> p1("cool",20);
	cout << p1.first<<" "<<p1.second;
	//利用make_pair
	pair<string, int> p2 = make_pair("cool",5);
	cout << p2.first << " " << p2.second;

 

 

 

set/multiset 容器

set/multiset 的特性是所有元素会根据元素的值自动进行排序。set是以RB-tree(红黑树,平衡二叉树的一种)为基础。

集合(Set)是一种包含已排序对象的关联容器

multiset允许重复对象,set则不允许。

因为底层是红黑树,所以不可以通过迭代器修改元素(但是有的vs版本编译器不会报错),可以将元素删了再加一个新的实现“修改”。

set排序问题

了解set排序问题之前我们来补充一个知识点:仿函数

转载文章,另外我们的下一篇文章也会学习到

如果让你统计一个数组中比10大的数,你会怎么做?

//统计数组中比10大的数字的数量
int RecallFunc(int *start,int *end,bool (*pf)(int)) {
	int count = 0;
	for (int *i = start; i != end + 1; i++) {
		//pf函数指针调用函数,i是int*,故*i即为int内容
		count = pf(*i) ? count + 1 : count;
	}
	return count;
}
bool IsGreaterThanTen(int num) {
	return num > 10 ? true : false;
}

int main(void) {
	int a[5] = { 10,100,11,5,19 };
	int result = RecallFunc(a, a + 4, IsGreaterThanTen);
	cout << result << endl;
	return 0;
}

RecallFunc() 函数的第三个参数是一个函数指针,用于外部调用,而 IsGreaterThanTen() 函数通常也是外部已经定义好的,它只接受一个参数的函数。如果此时希望将判定的阈值也作为一个变量传入,变为如下函数就不可行了:

bool IsGreaterThanThreshold(int num, int threshold) 
{
	return num>threshold ? true : false;
}

虽然这个函数看起来比前面一个版本更具有一般性,但是它不能满足已经定义好的函数指针参数的要求,因为函数指针参数的类型是bool (*)(int),与函数bool IsGreaterThanThreshold(int num, int threshold)的类型不相符。如果一定要完成这个任务,按照以往的经验,我们可以考虑如下可能途径:
(1)阈值作为函数的局部变量。局部变量不能在函数调用中传递,故不可行;
(2)函数传参。这种方法我们已经讨论过了,多个参数不适用于已定义好的 RecallFunc() 函数,当然,你也可以修改RecallFunc的形参要求。
(3)全局变量。我们可以将阈值设置成一个全局变量。这种方法虽然可行,但是不优雅,且非常容易引入 Bug,比如全局变量容易同名,造成命名空间污染。

那么有什么好的处理方法呢?仿函数应运而生。

仿函数(Functor)又称为函数对象(Function Object)是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样,不过作为仿函数的类,都必须重载 operator() 运算符。因为调用仿函数,实际上就是通过类对象调用重载后的 operator() 运算符。

使用仿函数了,写一个简单类,除了维护类的基本成员函数外,只需要重载 operator() 运算符 。这样既可以免去对一些公共变量的维护,也可以使重复使用的代码独立出来,以便下次复用。而且相对于函数更优秀的性质,仿函数还可以进行依赖、组合与继承等,这样有利于资源的管理。如果再配合模板技术和 Policy 编程思想,则更加威力无穷,大家可以慢慢体会。Policy 表述了泛型函数和泛型类的一些可配置行为(通常都具有被经常使用的缺省值)。

STL 中也大量涉及到仿函数,有时仿函数的使用是为了函数拥有类的性质,以达到安全传递函数指针、依据函数生成对象、甚至是让函数之间有继承关系、对函数进行运算和操作的效果。比如 STL 中的容器 set 就使用了仿函数 less ,而 less 继承的 binary_function,就可以看作是对于一类函数的总体声明,这是函数做不到的。

我们先来看一个仿函数的例子。

class StringAppend
{
public:
    explicit StringAppend(const string& str) : ss(str){}
    void operator() (const string& str) const
    {
         cout<<str<<' '<<ss<<endl;
    }
private:
    const string ss;
};

int main()
{
    StringAppend myFunctor2("and world!");
    myFunctor2("Hello");
}

接下来,我们利用仿函数来完成排序。

//仿函数
//这个仿函数实现了一个排序规则,并且是一个函数模板,利于扩展
template <class T>
class MyCompare {
public:
	bool operator()(T v1, T v2) {
		return v1 > v2;
	}
};

int main(void) {
	//利用类内部的枚举类型初始化对象
	MyCompare<int> mCom();

	set<int, MyCompare<int>> s1;
	s1.insert(2);
	s1.insert(4);
	s1.insert(6);
	s1.insert(3);
	for (set<int>::iterator it = s1.begin();
		it != s1.end(); it++) {
		cout <<*it<< " ";
	}
	cout << endl;
	return 0;
}

输出:6 4 3 2

这样我们就可以手动指定排序规则,同理,如果是自定义对象需要指定比较规则,也是这样的方法,一个仿函数重载好( )即可。

 

 

map/multimap容器

相对于set的只有一个值,map是按照 键值对 的方式存储。map也是以红黑树为底层实现机制(所以会根据键进行自动排序)。

multimap允许重复的key,map则不允许。

因为底层是红黑树,所以不可以通过迭代器修改元素(但是有的vs版本编译器不会报错),可以将元素删了再加一个新的实现“修改”。

 

有一点需要注意,map中可以用[ ]来索引key,例如mymap[10],就是mymap的key为10。如果你这样操作:mymap[10]=20,而通过这种方法操作后,如果下标(key)不存在,则创建一个pair插入到map容器中,如果下标(key)存在,那么会修改key对应的value;如果你要取一个不存在于map的key的value,例如输出mymap[60](不存在key为60),则会创建一个pair,key就是60,而value是默认值,如果是int则为0.

 

map应用实例

公司今天招聘了5个员工,5名员工进入公司之后,需要指派员工在哪个部门工作,人员信息有:姓名、年龄、电话、工资等组成。

通过Multimap进行信息的插入、保存、显示。

实现分部门显示员工信息,显示全部员工信息。

代码:

#include <iostream>
#include<string>
#include<iomanip>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

#define SALE_DEPARTMENT 1 //销售部门
#define DEVELOP_DEPARTMENT 2 //研发部门
#define FINACIAL_DEPARTMENT 3 //财务部门
#define ALL_DEPARTMENT 4 //所有部门

#define WORKER_NUM 5

//员工类
class Person {
protected:
	string mName;
	int mAge;
public:
	Person() {}
	Person(string name,int age)
		:mName(name),mAge(age) {}
};
class Worker:public Person{
private:
	string mTele;
	int mSalary;
public:
	Worker() {}
	Worker(string name, string tele, int age, int salary) :Person(name, age) {
		this->mTele = tele;
		this->mSalary = salary;
	}
	string getmName() { return mName; }
	string getmTele() { return mTele; }
	int getmAge() { return mAge; }
	int getmSalary() { return mSalary; }
	void setmName(string name) {  mName=name; }
	void setmTele(string tele) { mTele= tele; }
	void setmAge(int age) { mAge=age; }
	void setmSalary(int salary) { mSalary=salary; }
};
void Create_Worker(vector<Worker> &vWorker) {
	string seedName = "ABCDEFG";
	for (int i = 0; i < WORKER_NUM; i++) {
		Worker worker;
		string name = "员工" ;
		name += seedName[i];
		worker.setmName(name);
		worker.setmAge(rand() % 10 + 20);
		worker.setmTele("010-12321312321");
		worker.setmSalary(rand()%3000+4000);

		vWorker.push_back(worker);
	}
}
void WorkerByGroup(vector<Worker> vWorker,
				multimap<int,Worker> &workerGroup) 
{
	//把员工随机分配不同部门
	for (vector<Worker>::iterator it = vWorker.begin();
		it < vWorker.end(); it++) {
		int departID = rand() % 3 + 1;
		switch (departID)
		{
		case SALE_DEPARTMENT:
			workerGroup.insert(
				make_pair(SALE_DEPARTMENT, *it));
			break;
		case DEVELOP_DEPARTMENT:
			workerGroup.insert(
				make_pair(DEVELOP_DEPARTMENT, *it));
			break;
		case FINACIAL_DEPARTMENT:
			workerGroup.insert(
				make_pair(FINACIAL_DEPARTMENT, *it));
			break;
		default:
			break;
		}
	}
}
void showGroupWorkers(multimap<int, Worker> workerGroup,
	int whichDepartment, string tips) {
	multimap<int, Worker>::iterator it = workerGroup.find(whichDepartment);
	//找当前部门人数
	/* map底层红黑树已经自动排序,所以key是相连着的,
	   所以我们找到第一个和知道数量就可以全找出来
	*/
	//count方法,找到map/multimap中key的数量
	int departMentCount = workerGroup.count(whichDepartment);
	int num = 0;
	cout << tips << endl;
	for (multimap<int, Worker>::iterator pos = it;
		it != workerGroup.end() && num < departMentCount;
		pos++, num++) {
		cout << "姓名:" << pos->second.getmName() << " "
			<< "年龄:" << pos->second.getmAge() << " "
			<< "电话:" << pos->second.getmTele() << " "
			<< "工资:" << pos->second.getmSalary() << endl;
	}
}
void PrintWorkerByGroup(multimap<int, Worker> workerGroup) {
	showGroupWorkers(workerGroup, SALE_DEPARTMENT, "销售部门人员:");
	showGroupWorkers(workerGroup, DEVELOP_DEPARTMENT, "研发部门人员:");
	showGroupWorkers(workerGroup, FINACIAL_DEPARTMENT, "财务部门人员:");
}
int main(void) {
	//存放新员工的信息
	vector<Worker> vWorker;
	//存放分组信息(利用multimap)
	multimap<int, Worker> workerGroup;

	//创建员工
	Create_Worker(vWorker);
	//员工分组
	WorkerByGroup(vWorker,workerGroup);
	//打印信息
	PrintWorkerByGroup(workerGroup);
	return 0;
}

没有加随机种子,所以测试结果是一直一样的,有兴趣的朋友可以加一下。

map排序问题

既然key可以存放自定义类型,那么不可避免就遇到一个排序问题,解决方法是自己可以重载一下( )符号

class MyKey {
public :
	MyKey(int index,int id)
		:mIndex(index),mID(id) {}
public:
	int mIndex;
	int mID;
};
struct mycompare {
	bool operator()(MyKey k1, MyKey k2) {
		return k1.mIndex > k2.mIndex;
	}
};
void test01(){
	map<MyKey, int, mycompare> mymap;
	//key:MyKey匿名对象
	//value:整型常量
	mymap.insert(make_pair(MyKey(5,4),10));
	mymap.insert(make_pair(MyKey(1, 7), 20));
	mymap.insert(make_pair(MyKey(3, 3), 14));

	for (map<MyKey, int, mycompare>::iterator it = mymap.begin();
		it != mymap.end(); it++) {
		cout << it->first.mIndex << ":"
			<< it->first.mID << "="
			<< it->second << endl;
	}
}

这样就可以对MyKey按照mIndex进行排序了!

 


补充

容器元素深拷贝和浅拷贝的问题

我们可以直接执行此代码测试一下,会发现程序会崩溃:

class Person {
public :
	Person(char* name,int age) {
		this->pName = new char[strlen(name) + 1];
		strcpy(this->pName, name);
		this->mAge = age;
	}
	~Person(){
		if (this->pName != NULL) {
			delete[] this->pName;
			/*在删除一个指针之后,编译器只会释放该指针
			所指向的内存空间,而不会删除这个指针本身。
			所以delete之后记得随手将指针置空。
			*/
			pName = NULL;
		}
	}
public:
	char* pName;
	int mAge;
};
void test01(){
	char s[5] = "aaa";
	Person p(s, 20);
	vector<Person> vPerson;
	vPerson.push_back(p);
}
int main(void) {
	test01();
	return 0;
}

运行代码,程序崩溃。

程序崩溃原因:

  1. 我们在栈上创建了一个对象p,其中p的成员属性pName指向一个堆上的空间。
  2. 我们后来创建了一个容器,当我们将p放进容器中,底层操作实际是将p拷贝了一份放在容器中,这个拷贝是将全部的p的值拷贝了一份,故p中的指针pName也就完全复制了一份,数值完全相同,故这个指针指向的还是第一个p中的pName指向的堆内存。
  3. 程序执行完后对象会调用析构函数,vector中的p(第二个p)析构了,pName释放了那个空间,然后第一个p又调用了析构函数,于是就报错了。

解决方法:

只要让对象进入容器时拷贝的那个对象中的指针成员指向新开辟的堆空间即可。

上述代码加上如下内容即可:

	Person(const Person& p) {
		this->pName = new char[strlen(p.pName) + 1];
		strcpy(this->pName, p.pName);
		this->mAge = p.mAge;

		cout << "调用了重载构造";
	}
	Person& operator=(const Person& p) {
		if (this->pName != NULL) {
			delete[] this->pName;
		}
		this->pName = new char[strlen(p.pName) + 1];
		strcpy(this->pName, p.pName);
		this->mAge = p.mAge;
		return *this;

		cout << "调用了等号重载";
	}

根据输出结果可知,vector容器在加入对象时候,其实只是调用了重载构造,并没有调用等号重载,不过考虑以后更多的情况,建议两种都写上。

STL共性机制

STL的共性:

  • 可拷贝

STL容器所提供的都是值(value)寓意,而非引用(reference)寓意,也就是说当我们给容器插入元素的时候,容器内部实施了拷贝动作,将我们要插入的元素另行拷贝了一份放入到容器中,而不是将原数据直接放进去容器中,也就是说我们提供的元素必须能够被拷贝。

  • 除了queue和stack之外,每个容器都提供可返回迭代器的函数,运用返回的迭代器就可以访问元素
  • 通常STL不会抛出异常,需要使用者传入正确的参数
  • 每个容器都提供了一个默认的构造函数和默认的拷贝构造函数
  • 大小相关的构造方法:size()返回容器中元素的个数、empty判断容器是否为空

 

STL各个容器使用时机

常见使用常见:

  • vector:软件历史操作记录的存储
  • deque:排队购票系统、服务器处理请求

vector和deque的比较:

  1. vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置是不固定的(往前插会补空间)
  2. 如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关
  • list:公交车乘客的存储
  • set:对手机游戏的个人得分的存储
  • map:根据ID存储用户

 

 

 


 

 

商业转载 请联系作者获得授权,非商业转载 请标明出处,谢谢

 

发表评论