郑州网站建设 郑州网站设计,成都有哪些网站建设的公司,济南市住宅与房地产信息网,商城网站设计注意什么文章目录 简述STL容器list链表vector向量deque双端队列map映射表set集合hash_map哈希表 简述
STL是“Standard Template Library”的缩写#xff0c;中文译为“标准模板库”。STL是C标准库的一部分#xff0c;位与各个C的头文件中#xff0c;即他并非以二进制代码的形式提供… 文章目录 简述STL容器list链表vector向量deque双端队列map映射表set集合hash_map哈希表 简述
STL是“Standard Template Library”的缩写中文译为“标准模板库”。STL是C标准库的一部分位与各个C的头文件中即他并非以二进制代码的形式提供而是以源码的形式提供。STL体现了泛型编程的思想大部分基本算法被抽象被泛化独立于与之对应的数据结构用于以相同或近似的方式处理各种不同情形为我们提供了一个可扩展的应用框架高度体现了程序的可复用性。STL的一个重要特点是数据结构和算法的分离。
STL的头文件都不加扩展名且打开std命名空间。
包含了六大组件 STL容器
主要分为两大类
序列性容器序列容器保持插入元素的原始顺序。允许指定在容器中插入元素的位置。每个元素都有固定位置取决于插入时机和地点和元素值无关如链表list向量vector双端队列deque。
关联性容器元素位置取决于特定的排序规则和插入顺序无关map、hash-map、set。容器类自动申请和释放内存无需new和delete操作。
list链表
STL链表是序列性容器的模板类它将其元素保持在线性排列中链式结构并允许在队列中的任何位置进行有效的插入和删除。
特点list在任何指定位置动态的添加删除效率不变时间复杂度为O(1)操作相比于vector比较方便。但其查找效率为O(n)若想访问、查看、读取数据使用vector。
双向循环链表 require#include using namespace std;
构造链表的几种方式
空链表
listint lst;构建指定长度的链表且有默认的初始值
listint lst(3);构建了指定长度的链表手动指定初始值
listint lst(3, 4);使用初始化列表进行构建 类似new int[3]{1,2,3};
listint lst{ 2,3,4 };链表中的一些方法
begin()获取头节点的迭代器。end()获取尾节点的迭代器。front()返回头节点里的值。back()返回尾节点里的值。clear()清空链表。size()返回链表的长度、元素的数量。bool empty()链表是否为空。erase()删除指定迭代器位置的节点返回的是删除节点的下一个节点的迭代器。insert()指定迭代器位置插入一个元素返回的是插入的元素的迭代器。
insert() listint::iterator ite lst.insert(lst.begin(), 1); //在指定位置之前for (int v : lst) {cout v ;}cout endl;cout ite *ite endl; //返回的是增加的erase() ite;ite lst.erase(ite);//返回的是删除的下一个for (int v : lst) {cout v ;}cout endl;if (ite ! lst.end()) { cout ite *ite endl; //ite3}注意如果我们删除的是最后一个值那么ite返回的就是尾节点但是尾节点中没有元素强行获取元素就会崩所以要加一个判断
push_back()、push_front()、pop_back()、pop_front()链表头尾添加、删除。remove(const Type_Val)将值为val的所有节点删除。
将值为4的所有节点移除
lst.remove(4);unique()对连续而相同的节点移除只剩一个。 lst.push_back(0);lst.push_back(0);lst.push_back(1);lst.push_back(2);lst.push_back(0);lst.unique(); //连续且相同移除只剩一个for (int v : lst) {cout v ;}cout endl;sort()对链表元素进行排序默认升序。如果要指定排序规则需要指定排序规则函数。bool func(Type,Type);或greater()降序less()升序。
默认 lst2.sort(); //默认升序for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;指定规则
bool rule(int a, int b) {return a b;
}lst2.sort(rule); //指定规则for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;greater/less降序/升序 lst2.sort(lessint()/*greaterint()*/); for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;reverse()链表进行翻转。 lst2.reverse(); //翻转链表for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;**剪切拷贝整个链表**splice(iterator Where,list Right)将Right链表整个结合到另一个链表Where位置之前这是一个剪切操作Right链表将为空。 listint lst3{ 1,10,5 };ite lst2.begin();::advance(ite, 3); //ite3lst2.splice(ite, lst3); //将lst3 整个链表放到 3位置之前 剪切操作for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;cout size lst3.size() endl; //size 0这里我们了解到了一个函数advance();它可以用来偏移迭代器正常我们只能通过来偏移如果想偏移多个就要用循环而不能用那么我们就可以用这个方法
**剪切拷贝链表某个节点**splice(iterator Where,list Right,iterator First)将Right链表的First位置节点结合到this链表的Where位置之前这是一个剪切操作。this和Right可以为同一个链表。 lst2.splice(ite, lst3, lst3.begin());for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;for (ite lst3.begin(); ite ! lst3.end(); ite) {cout *ite ;}cout endl;**剪切拷贝链表的某一段节点**splice(iterator Where,list Right,iterator First,iterator Last)将Right链表的First位置到Last位置的一段元素[First,Last)不包含Last结合到this链表的Where位置之前这是一个剪切操作。this和Right可以为同一个链表但Where不能位于[First,Last)内。 lst2.splice(ite, lst3, lst3.begin(), --lst3.end());for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;for (ite lst3.begin(); ite ! lst3.end(); ite) {cout *ite ;}cout endl;merge(list Right,Traits Comp)将Right链表合并到this链表上this和Right必须经过排序两者或都为递增、或都为递减Comp描述了递增合并还是递减合并bool func(Type,Type);或greater()降序less()升序。这是一个剪切操作Right将为空链表。
升序 lst2.sort();lst3.sort();lst2.merge(lst3); //合并 剪切操作for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;cout size lst3.size() endl;降序 lst2.sort(greaterint());lst3.sort(greaterint());lst2.merge(lst3,greaterint());for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;cout size lst3.size() endl;swap(list Rigth)交换两个链表。 lst2.swap(lst3);for (ite lst2.begin(); ite ! lst2.end(); ite) {cout *ite ;}cout endl;for (ite lst3.begin(); ite ! lst3.end(); ite) {cout *ite ;}cout endl;vector向量
vector的行为类似于数组array但是其容量会随着需求自动增长动态数组向量在尾部的push和pop操作时间是恒定的.在向量的中间insert或erase元素需要线性时间在序列结尾插入、删除操作比开始位置性能要优越。
当向量元素增加超过当前的存储容量时会发生重新分配操作。重载了[]操作符就意味着它可以像数组一样使用[下标]访问元素。
特点数据的存储访问比较方便可以像数组一样使用[index]访问或修改值适用于对元素修改和查看比较多的情况对于insert或erase比较多的操作很影响效率不建议使用vector。 构造向量
require#include using namespace std;
vector(size_type Count)。vector(size_type Count,const Type Val)。构造函数构造指定长度的向量并设定初始值。有默认值。
空向量
vectorint vec;指定向量的容量默认值为0
vectorint vec(3);指定向量的容量并且指定默认值
vectorint vec(3, 1);初始化列表初始化向量
vectorint vec{ 1,2,3 };向量中的方法
begin()end()返回向量头尾元素的迭代器。front()back()返回头尾元素中的值。size()返回向量的使用量capacity()返回向量的容量。push_back()pop_back()在向量尾部添加删除当用push_back向vector尾部加元素的时候如果当前的空间不足会重新申请一块更大的空间。pop_back删除时使用量减少但容量不会减少。不同于list并没有提供push_front()和pop_front()。insert(const_iterator Where,const Type Val)向量的某个位置之前插入指定值。insert(const_iterator Where,size_type Count,const Type Val)。向量的某个位置之前插入count个指定值。 返回插入元素的迭代器size会增加。
ite vec.insert(vec.begin(), 0);erase(count_iterator Where)删除迭代器指向的元素返回的是删除元素的下一个元素的迭代器。size减少capacity不变。 ite vec.begin() 3;//ite 3;ite vec.erase(ite);向量中的迭代器可以有操作
clear()清空向量元素size使用量为0capacity不变。empty()向量是否为空描述的是使用量size。resize(size_type Newsize)resize(size_type _Newsoze,Type _Val)。为向量指定新的使用量如果使用量减少元素按顺序截取但容量不变如果使用量增加则会有默认值0如果使用量增加大于原容量则扩展容量有默认值也可以指定新的扩展元素的值。swap(vector Right)交换两个向量的元素。 vectorint v1(3);vec.swap(v1);可以利用交换将向量中的使用量和容量都清零
vectorint().swap(vec);对比 list 和 vector
vector是连续性空间是顺序存储list是链式结构体链式存储。vector在非尾部插入、删除节点会导致其他元素的拷贝移动list则不会影响其他节点元素。vector一次性分配好内存使用量不够时申请内存重新分配。list每次插入新节点时都会申请内存。vector随机访问性能好插入删除性能差list随机访问性能差插入删除性能好。vector具有容量和使用量的概念而list只有使用量即长度概念。
deque双端队列
deque没有容量的观念。它是动态以分段连续空间组合而成一旦有必要在deque的前端和尾端增加新空间串接在整个deque的头端或尾端deque的迭代器不是普通的指针其复杂度比vector复杂的多。除非必要我们应该尽量选择使用vector而非deque。
deque是一种双向开口的连续性空间可在头尾两端分别做元素的插入和删除操作。
deque模型图 构造双端队列
require:#include using namespace std;
deque(size_type Count)deque(size_type_Count,const Type Val)构造函数构造指定长度的向量并设定初始值。有默认值。
同样也是有三种构造方法指定元素个数给定默认值手动给值初始化参数列表。
dequeint de{ 1,2,3,4 };方法
push_back()、push_front()、pop_back()、pop_front()。begin()、end()、back()、front()、erase()、insert()。size()、empty()、clear()支持[]下标访问所以可以使用下标遍历。
双端队列的几种遍历方法
下标 for (int i 0; i de.size(); i) {cout de[i] ;}cout endl;增强的范围for for (int v : de) {cout v ;}cout endl;迭代器遍历 dequeint::iterator ite de.begin();while (ite ! de.end()) {cout *ite ;ite;}map映射表
Map的特性是所有元素都会根据元素的键值自动被排序map的所有元素都是pair同时拥有键值key和实值value。pair的第一元素被视为键值第二元素被视为实值。Map不允许两个元素拥有相同的键值Map的键值关系到Map的元素排列规则任意改变Map的元素键值将严重破坏Map的组织。所以不可以通过Map的迭代器来改变Map的键值。但可以通过迭代器来修改元素的实值。
查找效率O(log2(n))内部实现红黑树。
map模型图 构造
require#include using namespace std;
mapchar, int mm{ {d,1},{f,2},{b,3} };可以直接使用key值增加元素
mm[c] 4;方法
begin()、end()支持迭代器遍历。 mapchar, int ::iterator ite mm.begin();while (ite ! mm.end()) {cout ite-first - ite-second ;ite;}cout endl;pairiterator,boolinsert(value_type Val)插入一个元素如果key值重复则插入失败。iterator erase(iterator Where)返回删除的下一个。没有push和pop的插入删除。
插入 pairmapchar, int ::iterator,bool pr mm.insert(pairchar, int(a, 5)); //插入成功返回true迭代器指向新增的元素if (pr.second) {cout 插入成功 endl; //插入成功}else {cout 插入失败 endl;}cout pr.first-first -- pr.first-second endl; pr mm.insert(pairchar, int(a, 6)); //插入失败返回false迭代器指向的是已存在的元素if (pr.second) {cout 插入成功 endl;}else {cout 插入失败 endl; //插入失败}cout pr.first-first -- pr.first-second endl;删除 ite mm.begin();ite mm.erase(ite);for (pairchar, int pr : mm) {cout pr.first - pr.second ;}cout endl;if (ite ! mm.end()) {cout ite-first - ite-second endl;}clear()、size()、empty()iterator find(const Key Key)、按键值查找未匹配到返回end()count(const Key Key)按键值统计元素返回1或0。
通过键值查找删除元素 ite mm.find(d);if (ite ! mm.end()) { //如果找到了元素则删除ite mm.erase(ite);}for (pairchar, int pr : mm) {cout pr.first - pr.second ;}cout endl;upper_bound(const Key Key)、返回大于该键值的map的迭代器。lower_bound(const Key Key)返回该键值或者大于该键值的map的迭代器。 mapchar,int::iterator ite mm.upper_bound(b);cout ite-first - ite-second endl; //c-4ite mm.lower_bound(b);cout ite-first - ite-second endl; //b-3如果upper_bound和lower_bound返回的迭代器相同那么代表元素不存在 char e e;if (mm.upper_bound(e) mm.lower_bound(e)) { //元素不存在cout e 不存在 endl;}else {cout e 存在 endl;}set集合
所有元素都会根据元素的键值自动被排序Set的元素Map那样可以同时拥有实值和键值Set元素的简直就是实值实值就是键值。Set不允许两个元素有相同的键值因为Set元素值就是其键值关系到Set元素的排列规则。如果任意改变Set的元素值会严重的破坏Set组织。
查找效率O(log2(n))内部实现红黑树。
构造
require#include using namespace std;
setint st{ 4,1,6,3 };因为没有实值键值的区分了所以不能像map一样用[]去添加了
方法
begin()、end()支持迭代器遍历。 setint::iterator ite st.begin();while (ite ! st.end()) {cout *ite ;ite;}cout endl;pairiterator,boolinsert(const value_type Val)插入一个元素如果key值重复则插入失败。iterator erase(iterator Where)返回删除的下一个。 pairsetint::iterator,bool pr st.insert(6);if (!pr.second) {cout 插入失败 endl;}cout *pr.first endl;clear()、size()、empty()。iterator find(const Key Key)、按键值查找未匹配到返回end()count(const Key Key)按键值统计元素返回1或0。 ite st.find(44);if (ite st.end()) {cout 没找到 endl;}upper_bound(const Key Key)、返回大于该键值的set的迭代器。lower_bound(const Key Key)返回该键值或者大于该键值的set的迭代器。
hash_map哈希表
基于hash table哈希表数据的存储和查找效率非常高几乎可以看作常量时间相应的代价是消耗更多的内存。使用一个较大的数组来存储元素经过算法使得每个元素与数组下标有唯一的对应关系查找时直接定位。
查找效率O(1)。
构造
require#includehash_map using namespace std;
若高版本需要 #define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS 来去除error或使用unordered_map
#includeunordered_map
using namespace std;unordered_mapstring, int mm;mm[aa] 1;mm[ff] 2;mm[oo] 3;mm[cc] 4;方法
begin()、end()返回头、尾节点的迭代器。支持迭代器遍历。 unordered_mapstring, int::iterator ite mm.begin();while (ite ! mm.end()) {cout ite-first - ite-second ;ite;}cout endl;遍历结果为无序的
pairiterator,bool insert(const value_type Val)插入一个元素如果key值重复则插入失败。iterator erase(iterator Where)返回删除的下一个。iterator find(const Key _Key)按照key值进行查找 注意查找速度数据量内存使用。 ite mm.find(cc);ite mm.erase(ite);for (pairstring, int pr : mm) {cout pr.first - pr.second ;}cout endl;cout ite-first - ite-second endl;
