willluckysmile 2019-06-29
用C++写数据结构习题也有一段时间了,不得不说STL容器对数据结构真的很有用。
C++ STL(Standard Template Library,标准模板库)是一套功能强大的 C++ 模板类,其中包含4个组件,分别为算法、容器、函数、迭代器。
所以想总结一下自己用的容器,为什么要用它以及怎么用?
C/C++原生的数组最讨厌的就是——每次定义一个数组之前,我都要规定好它的大小。
然而天知道我的数组到底会存放多少内容,所以,为了能让我的数组大小够用,不得不把数组写得足够大,如下:
int a[9999];
刚学C语言时我的数组经常就是这样定义的,用丑而low
来形容一点也不为过,我相信不少人到现在也是这样写的。
直到遇上了vector,它的第一个吸引我的地方就是——不用再为分配数组大小而困扰了,它是一种动态数组,简单来说就是想要什么时候有多大就有多大的数组
(如果你机器的内存足够大)
需要引的头文件:#include<vector>
注意:引完头文件后需要using namespace std;
1.基本用法:
// 定义 int old[10]; // 传统定义数组的方法 vector<int> new; // 定义的大小为0的vector容器 // 添加元素 old[0] = 1;// 将数组0号位置元素赋值为1 new.push_back(1);// 向vector最后添加一个数据为1的元素 // 读取元素 cout << old[0]; cout << new[0]; // 修改元素 old[0] = 10; new[0] = 10; // 删除最后一个元素 new.pop_back();
可以看到,vector的读取和修改数据元素和数组的操作还是一样的。
2.常用操作
预备知识:
vector<int> new(10);// 定义一个大小为10的vector容器 vector<int>::iterator it = new.begin();// 定义一个vector容器的迭代器,初始迭代项为第一个元素
这里的迭代器
,相当于指向容器某个元素的一个指针
,相当于如下语句:
int old[10]; int * it = old;
只有理解了迭代器的概念,下面的操作才能会用
例如,容器内此时有三个数据:1, 3, 5,利用上面定义迭代器,可以实现如下操作:
// 向指定位置前插入元素 new.insert(it + 1, 10);
结果容器中的元素变为:1, 10, 3, 5
// 删除指定位置元素 new.erase(it + 2);
结果容器中的元素变为:1, 10, 5
// 使用下标遍历 for(int i = 0; i < new.size(); i++) { cout << new[i]; } // 使用迭代器遍历 for(;it != new.end(); it++) { cout << (*it); }
容器的数据元素不光可以是int,double,char这些基本数据类型,也可以是结构体,类,如下:
class Teacher { int id; string name; }; vector<Teacher> teachers;
在写哈夫曼编码时,需要将符号和对应的编码一一对应存放,例如'A'=>01,'B'=>001等,在不知道map以前,要实现这样的一一对应,有这样两种思路:
但是无论是哪种,在定义和使用上都存在一定的不方便。
如果你还记得thinkphp5的教程,那你一定对数组这样的用法并不陌生:var_dump(teacher['id'])
map就可以让数组实现这样的一一对应:
需要引的头文件:#include<map>
1.基本用法
map<char, string> hafucode;// 声明一个键为char类型,值为string类型的map容器
简单解释一下键(key)和值(value),以这条语句为例teacher['A'] = 01
,[]中的就是键,而01就是值,两者一一对应
// 单个插入数据 hafucode['A'] = "01"; // 向容器内插入键为'A',值为"01"的键值对 // 读取数据 cout << hafucode['A']; // 输出结果为01 // 根据键查询,找到返回指向该键的迭代器,否则返回指向end的迭代器 map<char, string>::iterator it; it = hafucode.find('A'); // 修改数据 hafucode['A'] = "00"; // 删除键为A的元素 hafucode.erse('A');
其他操作与vector大同小异,在此不做赘述。