Cu1universe

这就是生活

List前言:之前分析了 vector 的实现, 可以发现vector 的缺点在于处理高频率的插入与删除时的效率很低, 由于其是采用整体移动的方式处理插入与删除, 时间复杂度最坏是 O(n) , 而 list 则在删除与插入上有着优秀的效率 list 是使用链表实现的, 其对于删除和插入的时间复杂度为 O(1), 有着极其优秀的效率, 但是在于随机访问方面时间复杂度则为 O(n) , list 将具体实现分为了几个部分, 并通过嵌套的方式进行调用, 所以list 的实现也很灵活. 同时, list 在插入和删除后迭代器不会失效 list 基本结构框架list 将基本的框架分为 __list_node (链表节点), __list_iterator (访问迭代器) __list_node 链表结构123456789template <class T>struct __list_node { //前后指针 typedef void* void_pointer; void_pointer next; void_pointer prev; //节点数据 T ...

deque 源码分析前言:deque 所提供的功能相较于其他顺序容器, 拥有较为强大的功能, 在实现上相对于 list , vector 更复杂, deque 的迭代器是属于 random_access_iterator_tag 类型, 在分析 vector 时, 可以发现, 在某些极端情况下, 由于 vector 采用连续的空间储存元素, 会出现头插入以及扩容时进行大量元素的复制, 导致复杂度很高, 且对于空间的要求也是相对较高的. deque 则是 相对连续的 即它将多个数组按照顺序排序, 这样即使每个数组的头地址并不是连续的, 但是并不影响元素是连续的, 这里的连续指的是逻辑上是连续, 而不是地址连续, deque 是一个双向开口的容器, 头尾插入和删除都是 O(1) 复杂度的, 空间也是可扩展的, 且扩展时不经常对已有的元素进行移动. __deque_iterator迭代器结构deque 的 iterator 和 vector 类似, 但是由于其结构为相对连续所以对于 iterator 的设计要比 vector 的 iterator 更为复杂 全局函数用来计算每一个数组的 ...

stackstack 是栈, 它只允许在元素在栈顶进出, 而且在实现 stack 这个数据结构的时候, 我们发现, 似乎有一个数据结构已经满足了 stack 只允许元素在尾部进出的功能, 就是 deque, 它已经实现了在头尾都允许元素进出的功能, 所以只需要将 deque 封装一下即也就提取出 pop_back, push_back 就行了. 其实, 不只是 deque , 只要是提供了 pop_back, push_back 功能的数据结构即可, list 也提供了这些方法. 由此发现, stack严格来说并不是容器, 它是一底部容器完成其所有的工作, 它只修改了容器的接口, 准确是叫配接器. stack 源码stack也满足straits编程规范 12345678910111213141516171819202122232425262728293031class stack { friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&); friend boo ...

queuequeue 是队列, 只允许元素从队首弹出, 在队尾进入, 其也是使用 deque 作为默认容器, 将其功能进行封装得到的, 其可参考 stack queue 结构1234567891011121314151617181920212223242526272829#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = deque<T> >#elsetemplate <class T, class Sequence>#endifclass queue { //定义友元函数 friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y); friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);public: ty ...

模板方法模式应对问题在项目构建过程中, 对于某一些问题, 都是有着稳定的整体操作结构, 但是在各个子步骤中却有着许多的改变需求, 并且由于某些原因不能将子任务和整体结构同时实现 比如对于一个应用程序具有 5 个步骤 作为 Library 开发人员, 设计了整个应用程序的架构和整体步骤, 但是对于 2, 4 步骤, 并不能知道作为程序开发者将如何实现这些步骤, 所以可以使用 模板方法模式 来保证流程的稳定 模式定义 定义一个操作中的算法的骨架 (稳定)，而将一些步骤延迟(变化)到子类中。Template Method使得子类可以不改变(复用)一个算法的结构即可重定义(override 重写)该算法的某些特定步骤 ——《设计模式》GoF 结构 (Structure) 代码实现对于整个算法(程序的某个任务)的具体骨架是稳定的, 但是对于 ...

STL 中的 heap前言源码来自 SIGSTL3.0 在看之前默认你已经拥有了关于 堆, 大小根堆, 堆排序 等前置知识. heap 严格来说并不属于容器, 它只是实现关于对操作的一些模板函数, 故没有迭代器和遍历等操作 heap 作用描述 将一段序列转换为满足堆的性质(大根堆或者小根堆) 进行堆排序 向上维护堆的性质 取出堆顶元素 heap 分析push 插入元素插入函数为 push_heap 由于堆排序是不稳定的以及可能需要交换两个不连续位置的值 所以 heap 只接受 RandomAccessIterator 类型的迭代器 123456789101112template <class RandomAccessIterator>inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { __push_heap_aux(first, last, distance_type(first), value_type(first));}templat ...

priority_queue前言之前分析的 heap 是为了分析 priority_queue 做准备, priority_queue 是一个堆优先队列, 支持插入和删除元素, 但是对于插入和删除进行了限制, 对于插入只能在堆的最后进行插入, 只能获取和删除堆顶元素, 由于priority_queue 也是队列的一种体现, 所以为了维护队列的特性, 不提供迭代器以进行遍历操作. 同时它也不能被严格称作容器, 它是以支持RandomAccessIterator 类型迭代器容器和 heap 支持对容器数据进行堆操作的一个配置器 源码分析类型定义12345678910111213141516171819#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >#elsetemplate <class T, cl ...

单例模式(Singleton Pattern)定义:​ 该设计模式属于创建型模式, 其意图是保证一个类仅有一个实例, 并提供一个可以访问它的全局访问点, 保证所有的程序都可以访问该类所提供的唯一 一个实例. 对于概念的部分, 本文并不过多叙述, 主要还是侧重于代码层面的问题 结构 如果要构建一个单例模式: 要使其构造函数私有化, 保证不会在类外被其他程序创建 使用静态变量或者静态指针定义或指向该唯一对象 使用一个 public 静态方法来获取该对象 最简单的懒汉型单例模式12345678910111213141516class Singleton {private: //****数据****public: static Singleton* p; static Singleton* getInstance() { if (p == nullptr) //1 p = new Singleton(); //2 return p; //3 }private: Singlet ...

vectorvector 是 STL 实现的一个动态数组类本文只是分析 vector 的结构以及一些重要的设计方法, 对于一些没有那么重要的方法或者函数将一笔掠过, 如果想仔细了解, 请自行阅读源码 vector 的内容主要定义在 stl_vector.h 中, 该文件只是定义了 vector 对象以及相应类方法, 而且由于不直接透露 vector 的实现, 对其进行了一次封装, 将 stl_vector.h 与它所需要的头文件组合成vector.h, 直接使用 stl_vector.h 会缺少 vector 所依赖的函数或者方法的定义以及实现 定义部分1234567891011121314151617181920212223242526template <class T, class Alloc = alloc>class vector {public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef ...