网站结构构图,爱网课,响应式网站首页,天元建设集团招聘官网本文主要介绍STL六大组件#xff0c;并主要介绍一些容器的使用。 目录
1 泛型编程
2 CSTL
3 STL 六大组件
4 容器
4.1 顺序性容器
4.1.1 顺序性容器的使用场景
4.2 关联式容器
4.2.1 关联式容器的使用场景
4.3 容器适配器
4.3.1 容器适配器的使用场景
5 具体容器的… 本文主要介绍STL六大组件并主要介绍一些容器的使用。 目录
1 泛型编程
2 CSTL
3 STL 六大组件
4 容器
4.1 顺序性容器
4.1.1 顺序性容器的使用场景
4.2 关联式容器
4.2.1 关联式容器的使用场景
4.3 容器适配器
4.3.1 容器适配器的使用场景
5 具体容器的使用和剖析
5.1 vector向量
5.1.2 vector扩容 1 泛型编程 泛型编程是一种代码重用技术尽可能的将代码写的抽象和通用将算法从数据结构抽象出来以便适配多种多样的数据结构C的模板编程就是一种泛型编程技术。
2 CSTL STLStandard Template Library即标准模板库是一个高效的C程序库。 被容纳于C标准程序库C Standard Library中是ANSI/ISO C标准中最新的也是极具革命性的一部分。 包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C程序员们提供了一个可扩展的应用框架高度体现了软件的可复用性。 从逻辑层次来看在STL中体现了泛型化程序设计的思想generic programming 在这种思想里大部分基本算法被抽象被泛化独立于与之对应的数据结构用于以相同或相近的方式处理各种不同情形。 从实现层次看整个STL是以一种类型参数化type parameterized的方式实现的,基于模板(template)。 简单理解 STL 的基本观念就是将数据和操作分离。数据由容器进行管理操作则由算法进行而迭代器在两者之间充当粘合剂使任何算法都可以和任何容器交互运作。
3 STL 六大组件
STL 六大组件 STL的组成含义容器一些封装数据结构的模板类例如 vector 向量容器、list 列表容器等。算法STL 提供了非常多大约 100 个的数据结构算法它们都被设计成一个个的模板函数这些算法在 std 命名空间中定义其中大部分算法都包含在头文件 algorithm 中少部分位于头文件 numeric 中。迭代器在 C STL 中对容器中数据的读和写是通过迭代器完成的扮演着容器和算法之间的胶合剂。函数对象如果一个类将 () 运算符重载为成员函数这个类就称为函数对象类这个类的对象就是函数对象又称仿函数。适配器可以使一个类的接口模板的参数适配成用户指定的形式从而让原本不能在一起工作的两个类工作在一起。值得一提的是容器、迭代器和函数都有适配器。内存分配器为容器类模板提供自定义的内存申请和释放功能由于往往只有高级用户才有改变内存分配策略的需求因此内存分配器对于一般用户来说并不常用。简称分配器。
4 容器 所谓容器就是可以承载包含元素的一个器件它是STL六大组件之一是容器、算法、迭代器中最重要也是最核心的一部分。
4.1 顺序性容器 顺序性容器就是将一组具有相同类型的元素以严格的线性形式组织起来。顺序性容器的存储结构有顺序存储和链式存储。 具体的顺序性容器如下 容器 简介说明 vector 可变大小数组。相当于数组可动态构建支持随机访问无头插和尾插仅支持inset插入除尾部外的元素删除比较麻烦。但使用最为广泛。 deque 双端队列。支持头插、删尾插、删随机访问较vector容器来说慢,但对于首尾的数据操作比较方便 list 双向循环链表。使用起来很高效对于任意位置的插入和删除都很快在操作过后以后指针、迭代器、引用都不会失效 forward_list 单向链表。只支持单向访问在链表的任何位置进行插入/删除操作都非常快 array 固定数组。vector的底层即为array数组它保存了一个以严格顺序排列的特定数量的元素
4.1.1 顺序性容器的使用场景 一般大多数的题目都可以使用vector容器除非有特定需求使用其他容器更加合理方便
如果需要在一串数字的头尾进行操作偏向deque对于较中间的元素操作不推荐 对于中间的元素插入或删除可采用forward_list单向链表或list双向链表不需要移动元素只需改变相关结点的指针域即可
一个例子
#include iostream
#include vectorusing namespace std;// vector容器大小:
// 1 2 4 8 16 32
// vector 容器大小的增长是以2的倍数
int main(int argc, char *argv[])
{vectorint v1;for (int i 0;i 17;i)v1.push_back(i);cout v1[3] endl;cout v1.size() endl;cout v1.capacity() endl;return 0;
} 运行结果 4.2 关联式容器 关联式容器每一个元素都有一个键值key对于二元关联容器还拥有实值value容器中的元素顺序不能由程序员来决定有set集合和map映射这两大类它们均是以RB-Treered-black tree红黑树为底层架构。
具体的关联式容器如下 容器 简介说明 set/mutliset 集合/多重集合。对于set在使用insert插入元素时已插入过的元素不可重复插入这正好符合了集合的互异性在插入完成显示后会默认按照升序进行排序对于multiset可插入多个重复的元素 map/mutlimap 映射/多重映射。二者均为二元关联容器在构造时需要写两个参数类型前者对key值后者对应value值因为有两个参数因此在插入元素的时候需要配合对组pair进行插入具体见深入详解
4.2.1 关联式容器的使用场景 如果只负责查找内容具体到某个单位使用场景比如对手机游戏的个人的计分的存储可以使用set或mutliset。 如果需要同时放入容器的数据不止一个并且是不同类型比如一个为整型int,一个为string字符串型就可以考虑使用map或mutlimap。
4.3 容器适配器 容器适配器是一个封装了序列容器的一个类模板它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能。
具体的容器适配器如下 容器 简介说明 stack 堆栈。其原理是先进后出FILO其底层容器可以是任何标准的容器适配器默认为deque双端队列 queue 队列。其原理是先进先出FIFO只有队头和队尾可以被访问故不可有遍历行为默认也为deque双端队列 pirority_queue 优先队列。它的第一个元素总是它所包含的元素中优先级最高的就像数据结构里的堆会默认形成大堆还可以使用仿函数来控制生成大根堆还是生成小根堆若没定义默认使用vector容器
4.3.1 容器适配器的使用场景 1对于 stack 堆栈在我们日常生活中类似于坐地铁、电梯 2对于 deque 队列在我们日常生活中类似于排队打饭 3对于 pirority_queue因为其本质是堆可以考虑解决一些贪心问题
5 具体容器的使用和剖析
5.1 vector向量 对于vector容器它的数据结构与数组非常类似但是他们之间的不同之处是数组是静态空间一旦配置了就不能更改vector却可以进行动态分配随着元素的插入和删除内部的空间也会灵活变动就和C语言中的malloc和C中的new是一个道理不用害怕空间不足而一开始就定义一个很大的数组节省了内存空间。容器的大小是可以改变的。vector扩容是2的倍数。
一些例子
#include iostream
#include vector/** 线性表是一种逻辑结构按照存储结构可以分为顺序表和链表**
*/
/* vector 本质上是一个动态变长数组顺序表连续的存储空间访问的时间复杂度为O(1),对于尾部元素的插入和删除时间复杂度都是常量级别的* vector 也是一个类模板vector底层本质就是一个顺序表它是一个可变长的数组采用连续存储的空间来存储数据它的元素类型也可以是任意的内置类型或者自定义类型。* 对于vector的扩容机制Linux一般是以2的倍数增加VS一般是以1.5的倍数增加增加快的性能会比较好但是对空间的浪费会增大* vector扩容是开辟一段新的空间将旧的数据拷贝到新的空间
*/
/** 扩容 vec.resize(n) vec.reserve(n)
*/int main(int argc, char *argv[])
{std::vectorint vec {1, 2, 3, 4, 5};// vec.begin()2 代表从第三个元素开始vec。begin()代表从第一个元素开始std::vectorint vec1(vec.begin()2,vec.end()); // vecstd::vectorint vec2(vec); // vecstd::vectorint vec3(4); // [0,0,0,0]std::vectorint vec4(2,4); // [4,4]// vec.erase(vec.begin()1); // 删除第二个元素vec.erase(vec.begin(),vec.begin()1);//删除[1,3) 删除两个元素for (auto i : vec1) {std::cout i ;std::cout ******* std::endl;}vec.push_back(18); //在尾部插入一个元素std::cout Front1: vec.front() std::endl;std::cout Back1: vec.back() std::endl;vec.pop_back(); // 弹出尾部的元素vec.insert(vec.begin()4,3,99);for (int i 0;i vec.size();i){// std::cout vec( i ): vec[i] std::endl;std::cout vec( i ): vec.at(i) std::endl;}for (int i 0;i vec.size();i){std::cout i : vec.data()[i] std::endl;}std::cout ********* std::endl;std::vectorint::iterator it;for (it vec.begin();it ! vec.end();it){std::cout : *it std::endl;}std::cout ********* std::endl;for (auto it vec.begin();it ! vec.end();it){std::cout : *it std::endl;}std::cout ********* std::endl;// 返回常量迭代器的元素for (auto it vec.cbegin();it ! vec.cend();it){std::cout : *it std::endl;}std::cout ********* std::endl;// 逆序返回常量迭代器的元素for (auto it vec.rbegin();it ! vec.rend();it){std::cout : *it std::endl;}std::cout ********* std::endl;std::cout size: vec.size() Capacity: vec.capacity() std::endl;vec.clear();/* vec.resize(n) resize的扩容不会改变容器中原来的值这里默认对扩容的部分初始化为0* n capacity 时 可以对vector进行扩容,此时 size capacity n,n 为任意的大于原来capacity的值* n capacity 时不能对vector进行扩容此时 size n,但是 capacity 仍然与原来的capacity 相等* vec.reserve(n) 是指将容器的容量改为n,容器中的数据的个数不做改变也就是不会对vec.size() 做改变* n capacity 时 可以仅仅对容器进行扩容此时size保持不变capacity n* n capacity 时 不做任何的改变对size 和capacity没有任何影响* vec.assign(n,0) assign的扩容会改变容器中原来的值第二个参数就是需要改变后的值* n capacity 时 可以对vector进行扩容,此时 size capacity n,n 为任意的大于原来capacity的值* n capacity 时不能对vector进行扩容此时 size n,但是 capacity 仍然与原来的capacity 相等* 总之对于vector容器只能增大其容量不能减小其容量*/vec.push_back(12);vec.push_back(13);// vec.resize(13);vec.assign(13,0);// vec.reserve(13); // 仅仅改变capacity 的大小std::cout Resize size: vec.size() Capacity: vec.capacity() std::endl;std::cout size: vec.size() vec [ ;for (int i 0;i vec.size();i){std::cout vec[i] ;}std::cout ] std::endl; // vec.assign(130) 的输出结果 size: 13 vec [ 0 0 0 0 0 0 0 0 0 0 0 0 0 ] vec.resize(13) 的输出结果 size: 13 vec [ 12 13 0 0 0 0 0 0 0 0 0 0 0 ] for (int i 0;i 10;i){vec.push_back(i);} // 需要对vector进行扩容一般扩容是2的指数级别的std::cout After clear size: vec.size() Capacity: vec.capacity() std::endl;if (vec.empty()){std::cout Vec is empty! std::endl;}std::vectorint vecT[3];// vector 定义二维数组for (int i 0;i 3;i){vecT[i].push_back(i);std::cout vecT i size: vecT[i].size() std::endl;}std::vectorstd::vectorint vecT1;// vector 定义二维数组vecT1.resize(5);//5 行for (int i 0;i 5;i){vecT1[i].resize(10);//10 列}for (int i 0;i vecT1.size();i){for (int j 0;j vecT1[i].size();j){vecT1[i][j] i*j;}}for (int i 0;i vecT1.size();i){for (int j 0;j vecT1[i].size();j){std::cout vecT1[i][j] ;}}std::cout std::endl;return 0;
}
5.1.2 vector扩容
1vec.resize(n) vec.resize(n) resize的扩容不会改变容器中原来的值这里默认对扩容的部分初始化为0 n capacity 时 可以对vector进行扩容,此时 size capacity n,n 为任意的大于原来capacity的值 n capacity 时不能对vector进行扩容此时 size n,但是 capacity 仍然与原来的capacity 相等
2vec.reserve(n) vec.reserve(n) 是指将容器的容量改为n,容器中的数据的个数不做改变也就是不会对vec.size() 做改变 n capacity 时 可以仅仅对容器进行扩容此时size保持不变capacity n n capacity 时 不做任何的改变对size 和capacity没有任何影响
3vec.assign(n,0) vec.assign(n,0) assign的扩容会改变容器中原来的值第二个参数就是需要改变后的值 n capacity 时 可以对vector进行扩容,此时 size capacity n,n 为任意的大于原来capacity的值 n capacity 时不能对vector进行扩容此时 size n,但是 capacity 仍然与原来的capacity 相等 总之对于vector容器只能增大其容量不能减小其容量
