手机网投网站建设,sem代运营推广公司,网站建设+网络科技公司,成都seo达人1.大体对比
在软件开发的漫长历程中#xff0c;数据结构与算法始终占据着核心地位#xff0c;犹如大厦的基石#xff0c;稳固支撑着整个程序的运行。在众多编程语言中#xff0c;数据的存储与管理方式各有千秋#xff0c;而 C 凭借其丰富且强大的工具集脱颖而出#xff…1.大体对比
在软件开发的漫长历程中数据结构与算法始终占据着核心地位犹如大厦的基石稳固支撑着整个程序的运行。在众多编程语言中数据的存储与管理方式各有千秋而 C 凭借其丰富且强大的工具集脱颖而出尤其是在处理序列数据方面C 标准模板库STL中的序列容器 vector、list 和 deque 更是展现出卓越的性能与高度的灵活性。 和一些编程语言中单一的数据存储方式相比C 这三种序列容器的存在无疑为开发者提供了更多样化的选择。例如在 Python 中主要通过列表list来存储序列数据其本质上是一种动态数组但在处理大规模数据的随机访问和频繁插入删除操作时性能表现往往不尽如人意。反观 C 的 vector它与传统数组有相似之处却具备了自动调整大小的功能这一特性让其在面对数据量动态变化的场景时能够轻松应对极大地提升了开发效率。
再将目光投向链表结构。在 Java 语言中虽然没有像 C list 这样直接对应的双向链表容器但开发者可以通过自定义类和节点来构建链表结构。然而这种方式不仅实现起来较为繁琐而且在进行常见的元素操作如插入和删除时其效率远不及 C 的 list。C 的 list 作为双向链表每个节点都包含指向前一个节点和后一个节点的指针这种数据结构使得在任意位置进行插入和删除操作的时间复杂度都保持在常数级别在需要频繁修改序列数据的场景中它的优势便得以充分彰显。
deque 则是 C 序列容器中的一颗独特 “新星”它巧妙地融合了 vector 和 list 的部分优势。和 Java 中的双端队列ArrayDeque相比C 的 deque 不仅在两端进行元素的插入和删除操作时具有高效性而且在支持随机访问方面也毫不逊色。这意味着在既需要快速在两端增减元素又要对序列中的元素进行随机访问的复杂场景下deque 能够提供更为平衡和高效的解决方案。
正是基于这些显著的特性差异深入了解 C 的 vector、list 和 deque 这三种序列容器对于每一位追求卓越编程质量的开发者而言都显得尤为重要。接下来让我们拨开迷雾详细剖析这三种序列容器的独特之处探寻它们在不同编程场景下的最佳应用方式 2.数据结构
1.vector(连续) 2.list指针 3.deque 3.成员函数
这个三个人的成员函数是一样
3.1 创建
vector()默认构造函数创建一个空的 vector。
vector(size_type n, const T value T())创建一个包含 n 个值为 value 的元素的 vector。
vector(const vector other)拷贝构造函数创建一个 other 的副本。
vector(InputIterator first, InputIterator last)使用迭代器 first 到 last 范围内的元素初始化list()默认构造函数创建一个空的 vector。
list(size_type n, const T value T())创建一个包含 n 个值为 value 的元素的 vector。
list(const vector other)拷贝构造函数创建一个 other 的副本。
list(InputIterator first, InputIterator last)使用迭代器 first 到 last 范围内的元素初始化 deque()默认构造函数创建一个空的 vector。
deque(size_type n, const T value T())创建一个包含 n 个值为 value 的元素的 vector。
deque(const vector other)拷贝构造函数创建一个 other 的副本。
deque(InputIterator first, InputIterator last)使用迭代器 first 到 last 范围内的元素初始化 3.2 访问 back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾1位置的迭代器//vector没有
rbegin()//返回逆头位置的迭代器
rend()//返回逆尾-1位置的迭代器 //list没有
下标访问 [] 3.3删除
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素
erase(iterator pos)移除 pos 位置的元素。
erase(iterator first, iterator last)移除 first 到 last 范围内的元素。
clear()移除 vector 中的所有元素
3.4插入
push_back(const T value)
push_front(const T value)
insert(iterator pos, const T value) 4.实现队列和栈 栈一种先进后出的数据结构
队列一种先进先出的数据结构
用vector实现栈
#includevector
#includestring
using namespace std;templateclass T class stack {
private:std::vectorT data;
public://创建stack();stack(const stack other):data(other.data){};stack operator(const stack other){dataother.data;return *this;}stack(int n, T val):data(n,val){}//访问int size()const {return data.size();}bool empty()const{if(data.size()0)return true;elsereturn false;}T top() const{if(data.empty()true)throw string(stack is empty);elsereturn data.back();}//插入void push(T val){data.push_back(val);}//删除void pop(){if(data.empty()true)throw string(stack is empty);else{data.pop_back();}}~stack();}; 5.总结
对比维度std::vectorstd::liststd::deque底层结构动态数组在内存中分配连续的存储空间。当容量不足时通常会重新分配更大的内存块将原数据复制过去并释放旧内存。双向链表由一系列节点构成每个节点包含数据、指向前一个节点的指针和指向后一个节点的指针。由多个固定大小的数组块组成每个数组块内部连续存储数组块之间通过指针连接形成双端队列结构。访问操作- 支持随机访问可通过下标直接访问元素时间复杂度为 \(O(1)\)。 - 访问元素非常高效就像操作普通数组一样。- 不支持随机访问若要访问特定位置元素需从头或尾开始遍历链表时间复杂度为 (O(n))。 - 只能顺序访问元素。- 支持随机访问通过下标访问元素的时间复杂度为(O(1))。 - 虽然能随机访问但由于是分段连续存储在效率上可能略低于 vector。插入操作 在尾部插入元素效率高平均时间复杂度为 (O(1))但若触发内存重新分配时间复杂度为 (O(n))。 在中间或头部插入元素需要移动插入位置之后的所有元素时间复杂度为 (O(n))。- 在任意位置插入元素的时间复杂度均为 (O(1))只需修改相邻节点的指针。 - 插入操作非常灵活效率高。- 在头部和尾部插入元素效率高时间复杂度为 (O(1))。 - 在中间插入元素需要移动部分元素时间复杂度为 (O(n))但通常比 vector 移动元素的开销小。删除操作- 在尾部删除元素效率高时间复杂度为(O(1))。 - 在中间或头部删除元素需要移动删除位置之后的所有元素时间复杂度为 (O(n))。 在任意位置删除元素的时间复杂度均为 (O(1))只需修改相邻节点的指针。- 在头部和尾部删除元素效率高时间复杂度为 \(O(1)\)。 - 在中间删除元素需要移动部分元素时间复杂度为 \(O(n)\)但通常比 vector 移动元素的开销小。空间利用- 由于是连续存储可能会有内存碎片问题。当容量不足重新分配内存时可能会预留一定的额外空间造成空间浪费。 - 不过它的空间利用率相对较高因为没有额外的指针开销。每个节点都需要额外的指针来指向前一个和后一个节点增加了内存开销。 - 但链表节点在内存中可以不连续存储不会因为预留空间而造成浪费。- 由于需要维护多个数组块以及块之间的连接信息会有一定的额外开销。 - 不过它在动态扩展时不需要像 vector 那样重新分配并复制大量数据空间管理相对灵活。迭代器-随机访问迭代器支持 、--、、- 等操作可以像指针一样灵活地在容器中移动。- 双向迭代器支持 和 -- 操作能双向遍历链表但不支持随机访问。- 随机访问迭代器与 vector 的迭代器类似支持高效的随机访问操作。迭代器失效情况- 当发生插入或删除操作导致内存重新分配时所有迭代器、指针和引用都会失效。 - 在插入或删除元素后插入或删除位置之后的迭代器、指针和引用会失效。- 插入操作不会使任何迭代器、指针和引用失效。 - 删除操作只会使指向被删除节点的迭代器、指针和引用失效。在头部或尾部插入元素时迭代器一般不会失效但指向元素的引用和指针可能会失效。 - 在中间插入或删除元素时插入或删除位置之后的迭代器、指针和引用会失效。使用场景 适合需要频繁随机访问元素且插入和删除操作主要在尾部进行的场景如存储一组数据并经常通过下标访问。 - 实现栈、队列等数据结构时若操作主要集中在尾部vector 是不错的选择。- 适合需要频繁在任意位置进行插入和删除操作而对随机访问需求较少的场景如实现链表类的数据结构。 - 当需要频繁进行元素的移动、插入和删除且不需要随机访问元素时list 更合适。- 适合需要在头部和尾部频繁进行插入和删除操作同时也需要随机访问元素的场景如实现双端队列。 - 当数据量较大且需要在两端进行高效操作时deque 是一个较好的选择。
