外贸网站样式,免费追剧永久免费app,虚拟机wordpress安装教程,百度注册公司网站STL 中有哪些常见的容器 STL 中容器分为顺序容器、关联式容器、容器适配器三种类型#xff0c;三种类型容器特性分别如下#xff1a; 1. 顺序容器 容器并非排序的#xff0c;元素的插入位置同元素的值无关#xff0c;包含 vector、deque、list vector#xff1a;动态数组… STL 中有哪些常见的容器 STL 中容器分为顺序容器、关联式容器、容器适配器三种类型三种类型容器特性分别如下 1. 顺序容器 容器并非排序的元素的插入位置同元素的值无关包含 vector、deque、list vector动态数组 元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。deque双向队列 元素在内存连续存放。随机存取任何元素都能在常数时间完成仅次于 vector 。在两端增删元素具有较佳的性能大部分情况下是常数时间。list双向链表 元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。 2. 关联式容器 元素是排序的插入任何元素都按相应的排序规则来确定其位置在查找时具有非常好的性能通常以平衡二叉树的方式实现包含set、map。 set set中不允许相同元素map map 与 set 的不同在于 map 中存放的元素有且仅有两个成员变一个名为 first另一个名为 secondmap 根据 first 值对元素从小到大排序并可快速地根据 first 来检索元素。 3. 容器适配器 封装了一些基本的容器使之具备了新的函数功能包含 stack、queue。 stack栈 栈是项的有限序列并满足序列中被删除、检索和修改的项只能是最进插入序列的项栈顶的项后进先出。queue队列 插入只可以在尾部进行删除、检索和修改只允许从头部进行先进先出。 STL 容器用过哪些查找的时间复杂度是多少为什么 以下是其中一些常见容器的查找时间复杂度以及原因 vector向量查找时间复杂度为O(n)因为vector是基于数组实现的需要线性遍历整个数组来查找元素。 deque双端队列在未排序状态下查找时间复杂度为O(n)类似于vector。但在有序状态下可以利用二分查找降低查找时间复杂度为O(log n)。 list链表查找时间复杂度为O(n)因为链表是一种线性结构需要从头开始顺序查找元素。 set集合和multiset多重集合查找时间复杂度为O(log n)底层通常使用红黑树实现具有较好的平衡性能。 map映射和multimap多重映射查找时间复杂度为O(log n)底层通常使用红黑树实现按键进行自动排序。 stack栈和queue队列查找时间复杂度为O(n)因为它们是容器适配器提供了先进先出FIFO或后进先出LIFO的接口并不支持快速查找操作。 因此对于不同的STL容器其查找时间复杂度取决于底层数据结构的实现方式和算法设计。 vector 和 list 的区别分别适用于什么场景 vector 和 list 的区别 底层数据结构 vector 底层使用动态数组实现。list 底层使用双向链表实现。 插入和删除操作 vector 插入和删除元素效率低。list 插入和删除元素效率高因为只需要修改相邻节点的指针。 随机访问 vector 支持随机访问可以通过下标快速访问元素。list 不支持随机访问只能通过迭代器顺序访问元素。 空间和内存分配 vector vector 一次性分配好内存不够时才进行扩容。list list 每次插入新节点都会进行内存申请。 适用场景 vector 适用于连续存储支持随机访问而不在乎插入和删除的效率。 list 适用于不连续的内存空间如果需要高效的插入和删除而不关心随机访问。 简述 vector 的实现原理 vector 是一种动态数组在内存中具有连续的存储空间支持快速随机访问由于具有连续的存储空间所以在插入和删除操作方面效率比较慢。 当 vector 的大小和容量相等sizecapacity时如果再向其添加元素那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步 重新在堆上创建更大的动态数组大小是原来的2倍将旧内存空间中的数据按原有顺序移动到新的内存空间中最后将旧的内存空间释放。 扩容以后它的内存地址会发生改变 迭代器失效原因有哪些情况 迭代器失效是指迭代器在遍历容器过程中由于容器的结构发生改变而导致迭代器指向的元素不再有效。 以下是导致迭代器失效的常见情况 插入和删除操作 当在容器中插入或删除元素时可能会导致容器内存重新分配或元素位置的改变这可能会使迭代器失效。清空容器 清空容器会使容器内的所有元素被删除这样迭代器指向的元素就会失效。使用引起重新分配的操作 例如在vector中使用push_back()添加元素时如果超出了当前容量可能会触发重新分配操作从而使所有迭代器失效。排序操作 如果在排序过程中容器的元素被移动了位置迭代器可能会失效。使用非常量迭代器遍历过程中修改了容器 如果在使用非常量迭代器遍历容器的过程中修改了容器的结构例如插入或删除元素会使迭代器失效。 deque 的实现原理 分段连续内存、中控器 deque 是由一段一段的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间便配置一段连续定量的空间串接在 deque 的头端或者尾端。 deque 采取一块所谓的 map不是 STL 的 map 容器作为主控这里所谓的 map 是一小块连续的内存空间其中的每个元素此处成为一个结点都是一个指针指向另一段连续性内存空间称作缓冲区。缓冲区才是 deque的存储空间的主体。 红黑树的特性为什么要有红黑树 红黑树是一种自平衡的二叉搜索树它具有以下特性 节点颜色 每个节点要么是红色要么是黑色。根节点和叶子节点 根节点、叶子节点NIL节点即空节点是黑色的颜色相邻节点规则 不能有两个相邻的红色节点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这保证了红黑树的关键性质最长路径不超过最短路径的两倍。 2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN) map/Set 实现原理各操作的时间复杂度是多少 1. map 实现原理 map 内部实现了一个红黑树红黑树有自动排序的功能因此 map 内部所有元素都是有序的红黑树的每一个节点都代表着 map 的一个元素。因此对于 map 进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map 中的元素是按照二叉树存储的特点就是左子树上所有节点的键值都小于根节点的键值右子树所有节点的键值都大于根节点的键值使用中序遍历可将键值按照从小到大遍历出来。 2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN) unordered_map 实现原理 unordered_map 容器和 map 容器一样以键值对pair类型的形式存储数据存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构该结构本身不具有对数据的排序功能所以此容器内部不会自行对存储的键值对进行排序。底层采用哈希表实现无序容器时会将所有数据存储到一整块连续的内存空间中并且当数据存储位置发生冲突时解决方法选用的是“链地址法”又称“开链法”. mapunordered_map 的区别 map是基于红黑树实现的unordered_map是基于哈希表实现的map根据元素的键值会自动排序而unordered_map是乱序的map的增删改查时间复杂度是OlogN而unordered_map的时间复杂度是最好情况是O(1)最坏情况是ON。
