安徽飞亚建设网站,如何自己做资源网站,logo网站设计素材,seo查询工具deque 容器 Vector 容器是单向开口的连续内存空间#xff0c; deque 则是一种双向开口的连续线性空 间。所谓的双向开口#xff0c;意思是可以在头尾两端分别做元素的插入和删除操作#xff0c;当然#xff0c; vector 容器也可以在头尾两端插入元素#xff0c;但是在其…deque 容器 Vector 容器是单向开口的连续内存空间 deque 则是一种双向开口的连续线性空 间。所谓的双向开口意思是可以在头尾两端分别做元素的插入和删除操作当然 vector 容器也可以在头尾两端插入元素但是在其头部操作效率奇差无法被接受。 Deque 容器和 vector 容器最大的差异一在于 deque 允许使用常数项时间对头端 进行元素的插入和删除操作。二在于 deque 没有容量的概念因为它是动态的以 分段连续空间组合而成随时可以增加一段新的空间并链接起来换句话说像 vector 那样 ” 旧空间不足而重新配置一块更大空间然后复制元素再释放旧空间” 这样的事情在 deque 身上是不会发生的。也因此 deque 没有必须要提供所谓的空间保留(reserve) 功能 . 虽然 deque 容器也提供了 Random Access Iterator, 但是它的迭代器并不是普通的指针其复杂度和 vector 不是一个量级这当然影响各个运算的层面。因此除非 有必要我们应该尽可能的使用 vector 而不是 deque 。对 deque 进行的排序操作为了最高效率可将 deque 先完整的复制到一个 vector 中对 vector 容器进行排序再复制回 deque. deque 容器实现原理 Deque 容器是连续的空间至少逻辑上看来如此连续现行空间总是令我们联想 到 array 和 vector,array 无法成长 vector 虽可成长却只能向尾端成长而且其 成长其实是一个假象事实上(1) 申请更大空间 (2) 原数据复制新空间 (3) 释放原空间 三步骤如果不是 vector 每次配置新的空间时都留有余裕其成长假象所带来 的代价是非常昂贵的。 Deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间便配置一段连续定量的空间串接在 deque 的头端或者尾端。 Deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象并提供随 机存取的接口避开了重新配置空间复制释放的轮回代价就是复杂的迭代器架构。 既然 deque 是分段连续内存空间那么就必须有中央控制维持整体连续的假象 数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque 代码的实现远比 vector 或 list 都多得多。 Deque 采取一块所谓的 map( 注意不是 STL 的 map 容器 ) 作为主控这里所谓map 是一小块连续的内存空间其中每一个元素 ( 此处成为一个结点 ) 都是一个指针 指向另一段连续性内存空间称作缓冲区。缓冲区才是 deque 的存储空间的主体。 deque 构造函数 dequeT deqT; // 默认构造形式 deque(beg, end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。 deque(n, elem); // 构造函数将 n 个 elem 拷贝给本身。 deque( const deque deq); // 拷贝构造函数。 deque 赋值操作 assign(beg, end); // 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem); // 将 n 个 elem 拷贝赋值给本身。 deque operator ( const deque deq); // 重载等号操作符 swap(deq); // 将 deq 与本身的元素互换 deque 大小操作 deque.size(); // 返回容器中元素的个数 deque.empty(); // 判断容器是否为空 deque.resize(num); // 重新指定容器的长度为 num, 若容器变长则以默认值填充新位 置。如果容器变短则末尾超出容器长度的元素被删除。 deque.resize(num, elem); // 重新指定容器的长度为 num, 若容器变长则以 elem 值 填充新位置 , 如果容器变短则末尾超出容器长度的元素被删除。 deque 双端插入和删除操作 push_back(elem); // 在容器尾部添加一个数据 push_front(elem); // 在容器头部插入一个数据 pop_back(); // 删除容器最后一个数据 pop_front(); // 删除容器第一个数据 deque 数据存取 at(idx); // 返回索引 idx 所指的数据如果 idx 越界抛出 out_of_range 。 operator []; // 返回索引 idx 所指的数据如果 idx 越界不抛出异常直接出错。 front(); // 返回第一个数据。 back(); // 返回最后一个数据 deque 插入操作 insert(pos,elem); // 在 pos 位置插入一个 elem 元素的拷贝返回新数据的位置。 insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据无返回值。 insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据无返回值。 deque 删除操作 clear(); // 移除容器的所有数据 erase(beg,end); // 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase(pos); // 删除 pos 位置的数据返回下一个数据的位置。 stack 容器 容器基本概念 stack 是一种先进后出 (First In Last Out,FILO) 的数据结构它只有一个出口形式 如图所示。stack 容器允许新增元素移除元素取得栈顶元素但是除了最顶端 外没有任何其他方法可以存取 stack 的其他元素。换言之 stack 不允许有遍历 行为。 有元素推入栈的操作称为 :push, 将元素推出 stack 的操作称为 pop stack 没有迭代器 Stack 所有元素的进出都必须符合 ” 先进后出 ” 的条件只有 stack 顶端的元素才有机会被外界取用。Stack 不提供遍历功能也不提供迭代器。 stack 构造函数 stackT stkT; //stack 采用模板类实现 stack 对象的默认构造形式 stack( const stack stk); // 拷贝构造函数 stack 赋值操作 stack operator ( const stack stk); // 重载等号操作符 stack 数据存取操作 push(elem); // 向栈顶添加元素 pop(); // 从栈顶移除第一个元素 top(); // 返回栈顶元素 stack 大小操作 empty(); // 判断堆栈是否为空 size(); // 返回堆栈的大小 queue 容器 容器基本概念 Queue 是一种先进先出 (First In First Out,FIFO) 的数据结构它有两个出口 queue 容器允许从一端新增元素从另一端移除元素。 queue 没有迭代器 Queue 所有元素的进出都必须符合 ” 先进先出 ” 的条件只有 queue 的顶端元素才 有机会被外界取用。Queue 不提供遍历功能也不提供迭代器。 queue 构造函数 queueT queT; //queue 采用模板类实现 queue 对象的默认构造形式 queue( const queue que); // 拷贝构造函数 queue 存取、插入和删除操作 push(elem); // 往队尾添加元素 pop(); // 从队头移除第一个元素 back(); // 返回最后一个元素 front(); // 返回第一个元素 queue 赋值操作 queue operator ( const queue que); // 重载等号操作符 queue 大小操作 empty(); // 判断队列是否为空 size(); // 返回队列的大小 list 容器 list 容器基本概念 链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点 组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素 的数据域另一个是存储下一个结点地址的指针域。 相较于 vector 的连续线性空间 list 就显得负责许多它的好处是每次插入或者删除一个元素就是配置或者释放一个元素的空间。因此list 对于空间的运用有绝对的精准一点也不浪费。而且对于任何位置的元素插入或元素的移除list 永远是常数时间。 List 和 vector 是两个最常被使用的容器。 List 容器是一个双向链表。 采用动态存储分配不会造成内存浪费和溢出 链表执行插入和删除操作十分方便修改指针即可不需要移动大量元素 链表灵活但是空间和时间额外耗费较大 list 容器的迭代器 List 容器不能像 vector 一样以普通指针作为迭代器因为其节点不能保证在同一 块连续的内存空间上。List 迭代器必须有能力指向 list 的节点并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list 正确的递增递减、取值、成员 取用” 是指递增时指向下一个节点递减时指向上一个节点取值时取的是节点 的数据值成员取用时取的是节点的成员。 由于 list 是一个双向链表迭代器必须能够具备前移、后移的能力所以 list 容器 提供的是 Bidirectional Iterators. List 有一个重要的性质插入操作和删除操作都不会造成原有 list 迭代器的失效。 这在 vector 是不成立的因为 vector 的插入操作可能造成记忆体重新配置导致 原有的迭代器全部失效甚至 List 元素的删除也只有被删除的那个元素的迭代 器失效其他迭代器不受任何影响。 list 容器的数据结构 list 容器不仅是一个双向链表而且还是一个循环的双向链表。 list 构造函数 listT lstT; //list 采用采用模板类实现 , 对象的默认构造形式 list(beg,end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。 list(n,elem); // 构造函数将 n 个 elem 拷贝给本身。 list( const list lst); // 拷贝构造函数。 list 数据元素插入和删除操作 push_back(elem); // 在容器尾部加入一个元素 pop_back(); // 删除容器中最后一个元素 push_front(elem); // 在容器开头插入一个元素 pop_front(); // 从容器开头移除第一个元素 insert(pos,elem); // 在 pos 位置插 elem 元素的拷贝返回新数据的位置。 insert(pos,n,elem); // 在 pos 位置插入 n 个 elem 数据无返回值。 insert(pos,beg,end); // 在 pos 位置插入 [beg,end) 区间的数据无返回值。 clear(); // 移除容器的所有数据 erase(beg,end); // 删除 [beg,end) 区间的数据返回下一个数据的位置。 erase(pos); // 删除 pos 位置的数据返回下一个数据的位置。 remove(elem); // 删除容器中所有与 elem 值匹配的元素。 list 大小操作 size(); // 返回容器中元素的个数 empty(); // 判断容器是否为空 resize(num); // 重新指定容器的长度为 num 若容器变长则以默认值填充新位置。 如果容器变短则末尾超出容器长度的元素被删除。 resize(num, elem); // 重新指定容器的长度为 num 若容器变长则以 elem 值填充新位置。 如果容器变短则末尾超出容器长度的元素被删除。 list 赋值操作 assign(beg, end); // 将 [beg, end) 区间中的数据拷贝赋值给本身。 assign(n, elem); // 将 n 个 elem 拷贝赋值给本身。 list operator ( const list lst); // 重载等号操作符 swap(lst); // 将 lst 与本身的元素互换。 3.6.4.5 list 数据的存取 front(); // 返回第一个元素。 back(); // 返回最后一个元素。 3.6 .4 .6 list 反转排序 reverse(); // 反转链表比如 lst 包含 1,3,5 元素运行此方法后 lst 就包含 5,3,1 元素。 sort(); //list 排序 list 反转排序 reverse(); // 反转链表比如 lst 包含 1,3,5 元素运行此方法后 lst 就包含 5,3,1 元素。 sort(); //list 排序 set/multiset 容器 set/multiset 容器基本概念 Set 的特性是。所有元素都会根据元素的键值自动被排序。 Set 的元素不像 map 那样可以同时拥有实值和键值set 的元素即是键值又是实值。 Set 不允许两个元素 有相同的键值。 我们可以通过 set 的迭代器改变 set 元素的值吗不行因为 set 元素值就是其键 值关系到 set 元素的排序规则。如果任意改变 set 元素值会严重破坏 set 组织。 换句话说set 的 iterator 是一种 const_iterator. set 拥有和 list 某些相同的性质当对容器中的元素进行插入操作或者删除操作的 时候操作之前所有的迭代器在操作完成之后依然有效被删除的那个元素的迭代器必然是一个例外。 multiset 特性及用法和 set 完全相同唯一的差别在于它允许键值重复。 set 和 multiset 的底层实现是红黑树红黑树为平衡二叉树的一种。 树的简单知识 二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。 二叉树示意图 二叉搜索树是指二叉树中的节点按照一定的规则进行排序使得对二叉树中元素 访问更加高效。二叉搜索树的放置规则是任何节点的元素值一定大于其左子树中 的每一个节点的元素值并且小于其右子树的值。因此从根节点一直向左走一直 到无路可走即得到最小值一直向右走直至无路可走可得到最大值。那么在 儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树 上面我们介绍了二叉搜索树那么当一个二叉搜索树的左子树和右子树不平衡的时候那么搜索依据上图表示搜索 9 所花费的时间要比搜索 17 所花费的时间要多 由于我们的输入或者经过我们插入或者删除操作二叉树失去平衡造成搜索效率降低。 所以我们有了一个平衡二叉树的概念所谓的平衡不是指的完全平衡。 set 构造函数 setT st; //set 默认构造函数 mulitsetT mst; //multiset 默认构造函数 : set( const set st); // 拷贝构造函数 set 赋值操作 set operator ( const set st); // 重载等号操作符 swap(st); // 交换两个集合容器 set 大小操作 size(); // 返回容器中元素的数目 empty(); // 判断容器是否为空 set 插入和删除操作 insert(elem); // 在容器中插入元素。 clear(); // 清除所有元素 erase(pos); // 删除 pos 迭代器所指的元素返回下一个元素的迭代器。 erase(beg, end); // 删除区间 [beg,end) 的所有元素 返回下一个元素的迭代器。 erase(elem); // 删除容器中值为 elem 的元素。 set 查找操作 find(key); // 查找键 key 是否存在 , 若存在返回该键的元素的迭代器若不存在返 回 set.end(); count(key); // 查找键 key 的元素个数 lower_bound(keyElem); // 返回第一个 keykeyElem 元素的迭代器。 upper_bound(keyElem); // 返回第一个 keykeyElem 元素的迭代器。 equal_range(keyElem); // 返回容器中 key 与 keyElem 相等的上下限的两个迭代器。 set 的返回值 指定 set 排序规则: // 插入操作返回值 // 插入操作返回值 void test01(){ set int s; pairset int ::iterator, bool ret s.insert( 10 ); if (ret.second){ cout 插入成功 : *ret.first endl; } else { cout 插入失败 : *ret.first endl; } ret s.insert( 10 ); if (ret.second){ cout 插入成功 : *ret.first endl; } else { cout 插入失败 : *ret.first endl; } } struct MyCompare02{ bool operator ()( int v1, int v2){ return v1 v2; } }; //set 从大到小 void test02(){ srand(( unsigned int )time(NULL)); //我们发现 set 容器的第二个模板参数可以设置排序规则默认规则是 less_Kt y set int , MyCompare02 s; for ( int i 0 ; i 10 ;i){ s.insert(rand() % 100 ); } for (set int , MyCompare02::iterator it s.begin(); it ! s.end (); it ){ cout *it ; } cout endl; } //set 容器中存放对象 class Person{ public : Person(string name, int age){ this -mName name; this -mAge age; } public : string mName; int mAge; }; struct MyCompare03{ bool operator ()( const Person p1, const Person p2){ return p1.mAge p2.mAge; } }; void test03(){ setPerson, MyCompare03 s; Person p1( aaa , 20 ); Person p2( bbb , 30 ); Person p3( ccc , 40 ); Person p4( ddd , 50 ); s.insert(p1); s.insert(p2); s.insert(p3); s.insert(p4); for (setPerson, MyCompare03::iterator it s.begin(); it ! s.end(); it){ cout Name: it-mName Age: it-mAge endl; } } 对组(pair) 对组(pair) 将一对值组合成一个值这一对值可以具有不同的数据类型两个值可 以分别用 pair 的两个公有属性 first 和 second 访问。 类模板 template class T1, class T2 struct pair. 如何创建对组 ? // 第一种方法创建一个对组 pairstring, int pair1(string( name ), 20 ); cout pair1.first endl; // 访问 pair 第一个值 cout pair1.second endl; // 访问 pair 第二个值 // 第二种 pairstring, int pair2 make_pair( name , 30 ); cout pair2.first endl; cout pair2.second endl; //pair 赋值 pairstring, int pair3 pair2; cout pair3.first endl; cout pair3.second endl; map/multimap 容器 map/multimap 基本概念 Map 的特性是所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair,同时拥有实值和键值 pair 的第一元素被视为键值第二元素被视为实值 map 不允许两个元素有相同的键值。 我们可以通过 map 的迭代器改变 map 的键值吗答案是不行因为 map 的键值 关系到 map 元素的排列规则任意改变 map 键值将会严重破坏 map 组织。如果 想要修改元素的实值那么是可以的。 Map 和 list 拥有相同的某些性质当对它的容器元素进行新增操作或者删除操作 时操作之前的所有迭代器在操作完成之后依然有效当然被删除的那个元素的迭代器必然是个例外。 Multimap 和 map 的操作类似唯一区别 multimap 键值可重复。 Map 和 multimap 都是以红黑树为底层实现机制。 map 构造函数 mapT1, T2 mapTT; //map 默认构造函数 : map( const map mp); // 拷贝构造函数 map 赋值操作 map operator ( const map mp); // 重载等号操作符 swap(mp); // 交换两个集合容器 map 大小操作 size(); // 返回容器中元素的数目 empty(); // 判断容器是否为空 map 插入数据元素操作 map.insert(...); // 往容器插入元素返回 pairiterator,bool map int , string mapStu; // 第一种 通过 pair 的方式插入对象 mapStu.insert(pair int , string( 3 , 小张 )); // 第二种 通过 pair 的方式插入对象 mapStu.inset(make_pair(- 1 , 校长 )); // 第三种 通过 value_type 的方式插入对象 mapStu.insert(map int , string:: value_type ( 1 , 小李 )); // 第四种 通过数组的方式插入值 mapStu[ 3 ] 小刘 ; mapStu[ 5 ] 小王 ; map 删除操作 clear(); // 删除所有元素 erase(pos); // 删除 pos 迭代器所指的元素返回下一个元素的迭代器。 erase(beg,end); // 删除区间 [beg,end) 的所有元素 返回下一个元素的迭代器。 erase(keyElem); // 删除容器中 key 为 keyElem 的对组。 map 查找操作 find(key); // 查找键 key 是否存在 , 若存在返回该键的元素的迭代器 / 若不存在返 回 map.end(); count(keyElem); // 返回容器中 key 为 keyElem 的对组个数。对 map 来说要么是 0 要么是 1 。对 multimap 来说值可能大于 1 。 lower_bound(keyElem); // 返回第一个 keykeyElem 元素的迭代器。 upper_bound(keyElem); // 返回第一个 keykeyElem 元素的迭代器。 equal_range(keyElem); // 返回容器中 key 与 keyElem 相等的上下限的两个迭代器。 multimap 案例 公司今天招聘了 5 个员工 5 名员工进入公司之后需要指派员工在那个部门工作 人员信息有: 姓名 年龄 电话 工资等组成 通过 Multimap 进行信息的插入 保存 显示 分部门显示员工信息 显示全部员工信息 #define _CRT_SECURE_NO_WARNINGS
#include iostream
#include map
#include string
#include vector
using namespace std;
// multimap 案例
// 公司今天招聘了 5 个员工5 名员工进入公司之后需要指派员工在那个部门工作
// 人员信息有: 姓名 年龄 电话 工资等组成
// 通过 Multimap 进行信息的插入 保存 显示
// 分部门显示员工信息 显示全部员工信息
#define SALE_DEPATMENT 1 // 销售部门
#define DEVELOP_DEPATMENT 2 // 研发部门
#define FINACIAL_DEPATMENT 3 // 财务部门
#define ALL_DEPATMENT 4 // 所有部门
// 员工类
class person
{
public:string name; // 员工姓名int age; // 员工年龄double salary; // 员工工资string tele; // 员工电话
};
// 创建 5 个员工
void CreatePerson(vectorperson vlist)
{string seed ABCDE;for (int i 0; i 5; i){person p;p.name 员工;p.name seed[i];p.age rand() % 30 20;p.salary rand() % 20000 10000;p.tele 010-8888888;vlist.push_back(p);}
}
// 5 名员工分配到不同的部门
void PersonByGroup(vectorperson vlist, multimapint, person plist)
{int operate -1; // 用户的操作for (vectorperson::iterator it vlist.begin(); it ! vlist.end(); it){cout 当前员工信息: endl;
cout 姓名 it-name 年龄: it-age 工
资: it-salary 电话 it-tele endl;
cout 请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务
部门): endl;
scanf(%d, operate);
while (true)
{if (operate SALE_DEPATMENT){ // 将该员工加入到销售部门plist.insert(make_pair(SALE_DEPATMENT, *it));break;}else if (operate DEVELOP_DEPATMENT){plist.insert(make_pair(DEVELOP_DEPATMENT, *it));break;}else if (operate FINACIAL_DEPATMENT){plist.insert(make_pair(FINACIAL_DEPATMENT, *it));break;}else{
cout 您的输入有误请重新输入(1 销售部门, 2 研
发部门, 3 财务部门): endl;
scanf(%d, operate);}
}}cout 员工部门分配完毕! endl;cout ********************************************************* ** endl;
}
// 打印员工信息
void printList(multimapint, person plist, int myoperate)
{if (myoperate ALL_DEPATMENT){for (multimapint, person::iterator it plist.begin(); it ! plist.end(); it){cout 姓名 it-second.name 年龄: it-second.age 工资: it-second.salary 电话 it-second.t ele endl;}return;}multimapint, person::iterator it plist.find(myoperate);int depatCount plist.count(myoperate);int num 0;if (it ! plist.end()){while (it ! plist.end() num depatCount){cout 姓名 it-second.name 年龄: it-second.age 工资: it-second.salary 电话 it-second.t ele endl;it;num;}}
}
// 根据用户操作显示不同部门的人员列表
void ShowPersonList(multimapint, person plist, int myoperate)
{switch (myoperate){case SALE_DEPATMENT:printList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:printList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:printList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:printList(plist, ALL_DEPATMENT);break;}
}
// 用户操作菜单
void PersonMenue(multimapint, person plist)
{int flag -1;int isexit 0;while (true){
cout 请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4
所有部门, 0 退出) endl;
scanf(%d, flag);
switch (flag)
{
case SALE_DEPATMENT:ShowPersonList(plist, SALE_DEPATMENT);break;
case DEVELOP_DEPATMENT:ShowPersonList(plist, DEVELOP_DEPATMENT);break;
case FINACIAL_DEPATMENT:ShowPersonList(plist, FINACIAL_DEPATMENT);break;
case ALL_DEPATMENT:ShowPersonList(plist, ALL_DEPATMENT);break;
case 0:isexit 1;break;
default:cout 您的输入有误请重新输入! endl;break;
}
if (isexit 1)
{break;
}}
}
int main()
{vectorperson vlist; // 创建的 5 个员工 未分组multimapint, person plist; // 保存分组后员工信息// 创建 5 个员工CreatePerson(vlist);// 5 名员工分配到不同的部门PersonByGroup(vlist, plist);// 根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表PersonMenue(plist);system(pause);return EXIT_SUCCESS;
} STL 容器使用时机 比如上一次的记录上上次的记录但却不会去删除记录因为记录是事实的描述。 deque 的使用场景比如排队购票系统对排队者的存储可以采用 deque 支持 头端的快速移除尾端的快速添加。如果采用 vector 则头端移除时会移动大量 的数据速度慢。 vector 与 deque 的比较 一vector.at() 比 deque.at() 效率高比如 vector.at(0) 是固定的 deque 的开始位 置 却是不固定的。 二如果有大量释放操作的话vector 花的时间更少这跟二者的内部实现有关。 三deque 支持头部的快速插入与快速移除这是 deque 的优点。 list 的使用场景比如公交车乘客的存储随时可能有乘客下车支持频繁的不确实位置元素的移除插入。 set 的使用场景比如对手机游戏的个人得分记录的存储存储要求从高分到低分 的顺序排列。 map 的使用场景比如按 ID 号存储十万个用户想要快速要通过 ID 查找对应的 用户。二叉树的查找效率这时就体现出来了。如果是 vector 容器最坏的情况 下可能要遍历完整个容器才能找到该用户。
