主任说到学校新网站的建设工作,人像摄影作品,wordpress 迁移 群晖,建站交流目录 C标准模板库STL容器容器分类容器通用接口 顺序容器vectorlistdeque 容器适配器queuestackpriority_queue 关联容器#xff1a;红黑树setmultisetmapmultimap 关联容器#xff1a;哈希表unordered_set和unordered_multisetunordered_map和unordered_multimap 附1#xf… 目录 C标准模板库STL容器容器分类容器通用接口 顺序容器vectorlistdeque 容器适配器queuestackpriority_queue 关联容器红黑树setmultisetmapmultimap 关联容器哈希表unordered_set和unordered_multisetunordered_map和unordered_multimap 附1红黑树数据结构附2哈希表数据结构附3reserve和resize C标准模板库STL容器
容器都是类模板它们实例化后就成为容器类。用容器类定义的对象称为容器对象。对象或变量插入容器时实际插入的是对象或变量的一个复制品。
容器分类
顺序容器 1、元素在容器中的位置同元素的值无关即容器不是排序的。 2、顺序容器包括vector、deque、list。
关联容器 1、关联容器内的元素是有规则排列的排序或加入哈希桶插入元素时容器会按一定的排序规则将元素放在适当的位置上。因为按规则排列关联容器在查找时具有非常好的性能。 2、关联容器包括set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、std::unordered_multimap等。 3、不能修改关联容器中key的值因为元素修改后容器并不会自动重新排序。正确的做法的是 先删除该元素再插入新元素。
容器适配器 1、STL在两类容器的基础上屏蔽一部分功能突出或增加另一部分功能实现了容器适配器。 2、STL中容器适配器有stack、queue、priority_queue三种它们都是在顺序容器的基础上实现的。
容器通用接口
所有容器 int size( ) 返回容器对象中元素的个数 bool empty( ) 判断容器对象是否为空 顺序容器 front() 返回容器中第一个元素的引用 back() 返回容器中最后一个元素的引用 push_back() 在容器末尾增加新元素 pop_back() 删除容器末尾的元素 insert() 插入一个或多个元素 顺序容器和关联容器 begin( ) 返回指向容器中第一个元素的迭代器 end( ) 返回指向容器中最后一个元素后面的位置的迭代器 rbegin( ) 返回指向容器中最后一个元素的反向迭代器 rend( ) 返回指向容器中第一个元素前面的位置的反响迭代器 erase( ) 从容器中删除一个或几个元素 clear( ) 从容器中删除所有的元素 如果一个容器为空则begin()和end()的返回值相等rbegin()和rend()的返回值也相等 容器适配器 push添加一个元素 top返回顶部或对头的元素的引用 pop删除一个元素 顺序容器
vector 1、动态数组也叫可变长数组在堆中分配内存元素存放在连续的内存空间支持下标随机访问元素可重复且是无序存放。 2、在头部或中间进行插入和删除操作时会造成内存块的拷贝对尾部进行插入和删除时一般不会拷贝内存扩容时会内存拷贝。
扩容方式 开辟二倍的内存旧的数据拷贝到新的内存释放旧内存重新指向新内存。
时间复杂度 1、[ ]或at()下标访问任意元素时间复杂度是O(1)。 2、push_back尾部插入、pop_back尾部删除时间复杂度O(1)。 3、insert插入、erase删除时间复杂度O(n)。
#include vectorstd::vectorint _v;_v.push_back(20);//尾部添加元素_v.push_back(10);_v.push_back(10);//{20,10,10}printf(_v.front%d\n,_v.front());//队首元素_v.front20printf(_v.back%d\n,_v.back());//队尾元素_v.back10_v.pop_back();//移除尾部元素{20,10}_v.insert(_v.begin() 1, 30); //在指定的位置插入元素10的拷贝{20,30,10}_v.erase(_v.begin() 2);//删除指定位置的元素{20,30}//遍历可以使用下标遍历也可以使用迭代器遍历auto iter _v.begin();while(iter ! _v.end()){printf(value%d\n,*iter);iter;}printf(_v[0]%d,_v.at(1)%d\n,_v[0],_v.at(1));//下标访问越界crashat抛出异常打印
_v.front20
_v.back10
value20
value30
_v[0]20,_v.at(1)30list 1、双向链表存放在堆中内存空间是不连续的每个元素都存放在一块内存中通过指针指向上一个元素和下一个元素。元素可重复且是无序存放。 2、不需要扩容添加元素时分配内存删除元素时回收内存。 3、在任何位置添加和删除元素效率都很高无需内存拷贝。 4、不能下标随机访问访问任意元素效率低。
时间复杂度 1、访问首部和尾部是O(1)访问其他元素是O(n)。 2、push_back、push_front、insert插入是O(1)pop_front、pop_back、erase删除是O(1)。
#include liststd::listint _l;_l.push_back(20);//尾部添加元素_l.push_back(30);_l.push_back(40);_l.push_front(10);//头部添加元素{10,20,30,40}printf(_l.front%d\n,_l.front());//访问队首元素_l.front10printf(_l.back%d\n,_l.back());//访问队尾元素_l.back40_l.pop_back();//移除尾部元素{10,20,30}_l.pop_front();//移除头部元素{20,30}//list迭代器只能/--不能i随机访问_l.erase(_l.begin());//删除指定位置的元素{30}_l.insert(_l.begin(), 50); //在指定的位置插入元素10的拷贝{30,50}//使用迭代器遍历,不能使用下标访问auto iter _l.begin();while(iter ! _l.end()){printf(value%d\n,*iter);iter;}打印
_l.front10
_l.back40
value30
value50deque 1、双端队列deque类似于一个二维数组由多个连续小空间拼接而成引入map管理分段空间map是一块连续的空间map的每个元素是指向缓存区buffer的指针每个缓存区buffer存储多个元素。 2、deque底层是假象的连续空间实际上是分段连续的为了“整体连续”和下标随机访问deque定义了复杂的迭代器实现随机访问。 3、deque结合了vector和list的优缺点在队首和队尾进行插入和删除操作时效率高遍历和排序效率低中间插入和删除元素仍然存在内存拷贝随机访问时需要计算数据在哪个buffer的第几个数据效率低于vector。 4、deque功能全面但效率普遍较低实际应用时很少使用通常作为stack和queue的底层默认容器stack和queue不需要遍历只需要在固定的一端或者两端进行操作且deque扩容时不需要内存拷贝。
时间复杂度 1、访问首部和尾部是O(1)下标访问其他元素时接近O(1)。 2、push_back、push_front插入是O(1)pop_front、pop_back删除是O(1)。 3、insert插入、erase删除时间复杂度O(n)。
支持首尾添加元素/访问元素/移除元素支持下标访问和迭代器随机访问几乎支持vector和list的所有功能。
#include dequestd::dequeint _d;_d.push_back(20);//尾部添加元素_d.push_back(30);_d.push_back(40);_d.push_front(10);//头部添加元素{10,20,30,40}printf(_d.front%d\n,_d.front());//访问队首元素_d.front10printf(_d.back%d\n,_d.back());//访问队尾元素_d.back40_d.pop_back();//移除尾部元素{10,20,30}_d.pop_front();//移除头部元素{20,30}_d.erase(_d.begin());//删除指定位置的元素{30}_d.insert(_d.begin() 1, 80); //在指定的位置插入元素{30,80}//使用迭代器遍历auto iter _d.begin();while(iter ! _d.end()){printf(value%d\n,*iter);iter;}printf(_d[0]%d,_d.at(1)%d\n,_d[0],_d.at(1));//下标访问越界crashat抛出异常打印
_d.front10
_d.back40
value30
value80
_d[0]30,_d.at(1)80容器适配器
queue 1、队列先进先出的数据结构只支持在队尾添加元素在队首删除元素。 2、queue可以指定底层容器例如std::queueint, std::list q1可以是基于数组的队列也可以是基于链表的队列即顺序队列和链表队列。 3、queue不提供迭代器访问不能使用下标访问。
时间复杂度 1、插入push和删除pop是O(1)。 2、front和back访问是O(1)。
#include queuestd::queueint _q;_q.push(10);//尾部添加元素_q.push(20);_q.push(30);_q.push(40);//{10,20,30,40}printf(_q.front%d\n,_q.front());//访问队首元素_q.front10printf(_q.back%d\n,_q.back());//访问队尾元素_q.back40_q.pop();//移除队首元素{20,30,40}//不能使用下标和迭代器访问打印
_q.front10
_q.back40stack 1、数据栈先进后出的数据结构单端口进出数据入栈只能加入栈顶数据出栈也只能取栈顶的元素。 2、stack和queue数据结构类似可以指定底层容器默认是deque分数组栈和链表栈。 3、stack不提供迭代器访问不能使用下标访问。
时间复杂度 1、入栈push和出栈pop是O(1)。 2、top访问是O(1)。
#include stackstd::stackint _s;_s.push(10);//顶部添加元素_s.push(20);_s.push(30);_s.push(40);//{10,20,30,40}printf(_s.top%d\n,_s.top());//访问顶部元素_s.top40_s.pop();//移除顶部元素{10,20,30}priority_queue
1、优先级队列 priority_queue常用来对数据进行优先级处理比如优先级高的值在前面常用堆Heap来实现底层是以vector数组存储的完全二叉树。 2、优先级队列是一个拥有权值的queue其内部元素按照元素的权值排列。权值较高者排在最前优先出队。 3、priority_queue不提供迭代器访问不能使用下标访问。
堆是一种特殊的树只要满足以下两个条件就可以称这棵树为堆 1、堆是一颗完全二叉树完全二叉树要求除了最后一层其他节点个数都是满的最后一层的节点都靠左排列。 2、堆中的每一个节点都必须大于等于(或者小于等于)其子树中每个节点的值。
时间复杂度 1、使用vector数组构造priority_queue是O(n)。 2、插入元素push和移除堆顶pop是O(log(n))。 3、访问堆顶top是O(1)。
以下面程序举例数据结构如下
#include queuestd::vectorint v{ 1,2,3,4,5,6,7,8,9,10 };std::priority_queueint p1(v.begin(), v.end());//使用vector数组构造大顶堆printf(p1.top%d\n,p1.top());//访问顶部元素.top10// std::priority_queue int,std::vectorint,std::greaterint _p2;//小顶堆std::priority_queueint _p;//默认大顶堆_p.push(56);//添加一个元素自动排序_p.push(15);_p.push(70);_p.push(30);_p.push(10);_p.push(25);//{70,30,56,15,10,25}printf(_p.top%d\n,_p.top());//访问顶部元素_p.top70_p.pop();//移除顶部元素重新排序{56,30,25,15,10}打印
p1.top10
_p.top70关联容器红黑树
set
1、set是排序的、不重复的数据集合。 2、set元素类型是pair存储键值对且key和value必须相等。 3、set中的元素不能直接改变可以先删除再添加。 4、set底层是以红黑树数据结构实现节点存储值key。 5、set在内存中表现为一个排序的数组。 6、不支持下标访问。
时间复杂度 1、插入、删除、查找都是严格在O(logn)时间内完成。
#include setstd::setint s1;//定义一个空setstd::setint::iterator it;//s1的迭代器类型std::pairstd::setint::iterator,bool ret;//插入数据的返回值类型,first是指向插入数据的迭代器second标识是否插入成功// 单个数据插入for (int i1; i5; i)s1.insert(i*10); // {10,20,30,40,50}ret s1.insert(20); // 重复插入时失败返回的迭代器指向容器中已存在的值bool为falseif (ret.secondfalse)itret.first; // it now points to element 20s1.erase(50);// 通过值删除元素{10,20,30,40}s1.insert (it,25);//通过迭代器插入{10,20,25,30,40}//区间插入int myints[] {5,10,15};s1.insert (myints,myints3);//迭代器遍历访问for (its1.begin(); it!s1.end(); it)printf(*it%d ,*it);printf(\n);auto iter s1.find(20);//find查询元素是否在set集合中if(iter ! s1.end()){printf(found 20\n);}打印
*it5 *it10 *it15 *it20 *it25 *it30 *it40
found 20multiset
multiset类似与set区别在于multiset支持插入重复的元素insert函数没有返回值有重复元素时count函数返回值大于1。
map
1、map中存储的是键值对key,value根据key有序排列且key唯一。 2、map底层是以红黑树数据结构实现。 3、使用迭代器可以对value进行修改但不能修改key若要修改key可以先删除再添加。 4、可以通过[key]或at(key)下标访问若map中没有该key则[ ]会向map中添加键值对at()抛出异常或crash。 5、map在内存中表现为根据key排序的一组键值对。
时间复杂度 1、插入、删除、查找都是严格在O(logn)时间内完成。
#include mapstd::mapint,std::string map1;//定义一个空mapstd::mapint,std::string::iterator it;//map1的迭代器类型//插入数据的返回值类型,first是指向插入数据的迭代器second标识是否插入成功std::pairstd::mapint,std::string::iterator,bool ret;//1.通过pairint, string(1,lilei) 构造pair元素map1.insert(std::pairint, std::string(1,lilei));//2.通过make_pair构造pair元素map1.insert(std::make_pair(2,hmm));//3.通过value_type构造pair元素map1.insert(std::mapint, std::string::value_type(3,zsan));//4.[ ]下标插入map1[4] zsi;//5.emplace插入map1.emplace(5,chw);ret map1.emplace(2,hmei);if(ret.second false)//插入失败返回falseprintf(ret.first%s\n,ret.first-second.c_str());bool ret2 map1.erase(1);//通过key删除元素成功返回true失败返回falseprintf(erase ret2%d\n,ret2);//find查找keyauto iter_find map1.find(3);if(iter_find ! map1.end()){printf(find key%d,value%s\n,iter_find-first,iter_find-second.c_str());}//迭代器安全删除std::mapint,std::string::iterator ite_es map1.begin();while(ite_es ! map1.end()){if(ite_es-first 3){ite_es map1.erase(ite_es);}elseite_es;}//迭代器遍历auto iter_bl map1.begin();while(iter_bl ! map1.end()){printf(key%d,value%s\n,iter_bl-first,iter_bl-second.c_str());iter_bl;}
打印
ret.firsthmm
erase ret21
find key3,valuezsan
key2,valuehmm
key4,valuezsi
key5,valuechwmultimap
multimap类似与map区别在于multimap支持插入重复的元素insert和emplace函数没有返回值有重复元素时count函数返回值大于1。multimap不能使用[ ]下标插入。
关联容器哈希表
unordered_set和unordered_multiset
1、这两个容器的操作集类似于set和multiset区别在于unordered_set和unordered_multiset的底层数据结构是哈希表。 2、哈希表是通过把key进行哈希运算分配到哈希桶哈希桶内使用链表法解决哈希冲突。通过key就可以快速找到哈希桶的位置因此查找效率高。
时间复杂度 1、在没有哈希冲突的情况下查找是O(1)。
unordered_map和unordered_multimap
1、这两个容器的操作集类似于map和multimap区别在于unordered_map和unordered_multimap的底层数据结构是哈希表。 2、哈希表是通过把key进行哈希运算分配到哈希桶哈希桶内使用链表法解决哈希冲突。通过key就可以快速找到哈希桶的位置因此查找效率高。
时间复杂度 1、在没有哈希冲突的情况下查找是O(1)。
unordered_map用法参考这里https://blog.csdn.net/weixin_40355471/article/details/131803322?spm1001.2014.3001.5502。
附1红黑树数据结构
红黑树并不是严格的平衡二叉树它要求从根到叶子的最长路径不多于最短路径的两倍长为了满足这个特性红黑树设置了五大规则 1、节点是红色或者黑色 2、根节点是黑色 3、每个叶子的节点都是黑色的空节点 4、每个红色节点的两个子节点都是黑色的 5、从任意节点到其叶子节点的每条路径都包含相同个数的黑色节点 红黑树的高度近似logn是近似平衡的二叉树插入、删除、查找的时间复杂度都是O(logn)性能非常稳定在实际工作中凡是动态插入、删除、查找数据的场景都可以用它。 附2哈希表数据结构
哈希表也叫散列表Hash table是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表。
下图是一个典型应用key经过哈希函数计算得到哈希值哈希值对一个常数n取模得到下标通过下标可以直接访问哈希桶哈希桶内存放key,value如果有哈希冲突在哈希桶内使用链表存储。
附3reserve和resize
这两个函数常用于STL容器容量操作。 1、reserve只分配空间不创建对象不可访问用于大量成员创建一次性分配空间push_back时就不用再分配提高执行效率。 2、resize分配空间的同时还创建对象并给对象赋初始值可访问。 std::vectorint v1;v1.resize(5);//分配空间并初始化对象为0此时元素个数是5v1.push_back(10);for(int index0;indexv1.size();index)printf(v1[%d]%d ,index,v1[index]);printf(\n);std::vectorint v2;v2.reserve(5);//只分配空间不创建对象此时元素个数是0v2.push_back(20);for(int index0;indexv2.size();index)printf(v2[%d]%d ,index,v2[index]);printf(\n);打印
v1[0]0 v1[1]0 v1[2]0 v1[3]0 v1[4]0 v1[5]10
v2[0]20
