闲聊

简单聊一下目前的状态,生病!!生病!!,还是tm的生病,其实也不是大病,就是一个小感冒,但是困扰了我真正的两个星期的生活,不过今天,终于好了(快放假了,再不好我就要奔溃了),开始奋斗!!

不仅仅是生病导致我博客的闲置,要命的是我的拖延症也犯了,虽然我经常写笔记,最近一段时间也再没有再博客这里更新了,拖延的借口就是“等我整理了再发!!”,随后一拖再拖。

学习数据结构之后,就一直像C+ + 的STL一样简单封装一些数据结构(只是简单模仿了),检验自己的学习成果。想法有了,那么得开始实践!实现的过程中,我还是遇到了一些不大不小的问题,比如 如何理解C++中的迭代器哇,平衡二叉树的实现,函数如何传入不定参数哇?,啥是泛型编程?完成之后,代码还是有不少的提升空间!一遍总结一遍开始优化代码吧!

当然,感冒也没闲着,除了模仿STL之外,我还简单使用c语言实现了 一个简单的可以处理CGI请求的http服务器!抽空也总结一下!

环境

windows上地表最强IDE: Visual Studio 2019,编译器:MSVC, C++版本 C++14.

初次学习C+ +,学校课本当然还是拿着经典的vc6.0,C+ +的版本还是那个经典的C+ +98,对比众多编程语言,C+ +没有优秀的内存回收机制,没有编程语言级别的多线程支持,没有像java那样的生态(前面三点,至少我以前是这么认为的),我甚至一度怀疑c+ +这种“古老”的编程语言终会被时代抛弃,但是,随着我继续学习C+ +11,我才能体会到c+ +的高明之处,没有认真学习和了解c+ +,就不要给自己找借口“贬低”c+ +,然后给自己偷懒的机会!

学习资料:

  1. 侯捷老师的课程
  2. 第五版C++ PRIMER
  3. cppreference.com
  4. 现代 C++ 教程:高速上手 C++ 11/14/17/20

简单认识STL

泛型编程(generic programming),将程序写得尽可能通用,将算法从数据结构中抽象出来,成为通用的。
这里的关键就是就要使用我们模板(template)!!

模板类

简单复习模板类的语法吧

template <类型参数表>
class 类模板名{
    成员函数和成员变量
};

类型参数列表可以为:

typename 类塑参数1, typename 类型参数2, ...

typename 关键字 也可以换成class

类模板中的成员函数放到类模板定义外面写时的语法如下:

template <类型参数表>
返回值类型  类模板名<类型参数名列表>::成员函数名(参数表)
{
    ...
}

用类模板定义对象的写法如下:

类模板名<真实类型参数表> 对象名(构造函数实际参数表);

顺带提一嘴,模板类,头文件不能与cpp文件分离,这里的原因和c/c++程序编译器有关,一般模板类声明和定义直接写在一个文件里,可以将后缀改成hpp

六大部件

  1. 容器(Container)
  2. 分配器(Allocator)
  3. 算法(Algorithms)
  4. 迭代器(Iterators)
  5. 适配器(Adapters)
  6. 仿函数(Functors)

当然这里6大组件,重点是 算法 ,容器,迭代器,由于学习进度上的延误,我模仿stl的时候,重点放在了这三大组件之中。

**容器:**各种数据结构,如vector、list、deque、set、map等,用来存放数据,从实现角度来看,STL容器是一种class template。

算法:各种常用的算法,如sort、find、copy、for_each。从实现的角度来看,STL算法是一种function tempalte.

迭代器:扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数:行为类似函数,可作为算法的某种策略。从实现角度来看,仿函数是一种重载了operator()的class 或者class template

适配器:一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器:负责空间的配置与管理。从实现角度看,配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略的变化,适配器可以修饰仿函数。

他们之间的巧妙组合如下图

image-20210628173602868

瞅瞅STL的标准操作案例:

这段代码,进行了找出比40大或等于的元素个数,是不是非常简洁

image-20210628174114071

容器

容器类是容纳、包含一组元素或元素集合的对象
七种基本容器:

  1. 向量(vector)
  2. 双端队列(deque)
  3. 列表(list)
  4. 集合(set)
  5. 多重集合(multiset)
  6. 映射(map)
  7. 多重映射(multimap)
image-20210628175412723

vector 、deque、list称之为序列式容器,简单理解就是常说的线性结构 ;set、multiset、map、multimap是一种 关联式容器 ,元素位置取决于特定的排序准则以及元素值,和插入次序无关.

容器的简单使用

  1. 需要频繁在序列中间位置上进行插入和/或删除操作且不需要过多地在序列内部进行长距离跳转,应该选择list
  2. vector头部与中间插入删除效率较低,在尾部插入与删除效率高。
  3. deque是在头部与尾部插入与删除效率较高

deque是双向开口的连续线性空间(动态将多个连续空间通过指针数组接合在一起),随时可以增加一段新的空间,所以数据想vector里面的分配,复制,释放操作不会发生。deque头尾两端分别做插入和删除操作都是常数时间。

关联式容器是非线性的树结构,更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系,也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是:在值中选择一个值作为关键字key,这个关键字对值起到索引的作用,方便查找。Set/multiset容器 Map/multimap容器

迭代器

迭代器,看着名字高大上,其实他们就是对指针的封装。迭代器的设计思维-STL的关键所在,STL的中心思想在于将容器(container)和算法(algorithms)分开,彼此独立设计,最后再一贴胶着剂将他们撮合在一起。迭代器就是这里的指针!

常用的迭代器按功能强弱分为下面五种:

输入迭代器:仅仅读。支持++、==、!=;

输出迭代器:仅仅写,支持++;

前向迭代器:读写,支持++、==、!=。

双向迭代器:读写,支持++、--。

随机访问迭代器:读写,支持++、--、[n]、-n、<、<=、>、>=。

迭代器按照定义方式分成以下四种:

  1. 正向迭代器,定义方法如下:容器类名::iterator 迭代器名;
  2. 常量正向迭代器,定义方法如下:容器类名::const_iterator 迭代器名;
  3. 反向迭代器,定义方法如下:容器类名::reverse_iterator 迭代器名;
  4. 常量反向迭代器,定义方法如下:容器类名::const_reverse_iterator 迭代器名;

常见容器的迭代器功能如下:

容器迭代器功能
vector随机访问
deque随机访问
list双向
set / multiset双向
map / multimap双向
stack不支持迭代器
queue不支持迭代器

设计迭代器

每种容器在实现的时候设计了一个内嵌的iterator类,不同的容器有自己专属的迭代器(专属迭代器负责实现对应容器访问元素的具体细节),使用迭代器来访问容器中的数据。除此之外,通过迭代器可以将容器和通用算法结合在一起,只要给予算法不同的迭代器,就可以对不同容器执行相同的操作,例如find查找函数(因为迭代器提供了统一的访问方式,这是使用迭代器带来的好处)。迭代器对一些基本操作如*、->、++、==、!=、=进行了重载,使其具有了遍历复杂数据结构的能力,其遍历机制取决于所遍历的容器,所有迭代器的使用和指针的使用非常相似。通过begin,end函数获取容器的头部和尾部迭代器,end迭代器不包含在容器之内,当begin和end返回的迭代器相同时表示容器为空。

Iterator 需要遵守的规则

迭代器提供了统一的访问方式,那么迭代器要遵守一些设计原则

我们都知道type_traits 可以萃取出类型的型别,根据不同型别可以执行不同的处理流程。那么对于迭代器来说,是否有针对不同特性迭代器的优化方法呢?答案是肯定的。

根据迭代器不同的特性,将迭代器分为5类:

  1. Input Iterator:这种迭代器所指的对象为只读的。
  2. Ouput Iterator: 所指对象只能进行一次写入操作。
  3. Forward Iterator: 允许”读写型”算法在迭代器区间内进行读写操作,比如说replace函数需要读取区间内容,根据所读内容决定是否写入
  4. Bidirectional Iterator : 可双向移动。某些算法需要反向遍历某个迭代器区间
  5. Random Access Iterator : 前四种迭代器只提供部分指针算数能力(前三种支持++运算符,后一种还支持–运算符),第五种则支持所有指针的算术运算

根据五种迭代器,c++定义了如下类,并且非常奇妙的继承关系!

image-20210628184900535

class input_iterator_tag {};
class output_iterator_tag {};
class forward_iterator_tag:public input_iterator_tag {};
class bidirectional_iterator_tag :public forward_iterator_tag {};
class random_access_iterator_tag :public bidirectional_iterator_tag {};

这是五种空壳类,没其他用处就是用来标识迭代器类型,用来激活函数重载机制(因为泛型算法中要求的参数都会只给最上层的类型,这样调用时,下层迭代器来了也接受)

为什么要有这么多中的迭代器呢?你看容器人手一个!因为迭代器中有operator的实现,每个容器存储的方式也不尽相同,vector是顺序存储,list是链式存储,operator内部实现肯定不一样的,但是又想泛型编程,继承咯,封装咯。。。

最常使用到的迭代器的相应类别有5种 标签 :value_type,difference_type,pointer,reference,iterator_category,value_type就是迭代器所指向的对象的型别,每个迭代器都应该定义有自己的value_type内嵌型别

  • difference_type用来表示两个迭代器之间的距离,因此也可以表示一个容器的最大容量
  • referecne引用?左值,因为有需要const iterator的情况出现,这时候需要一个不能改变所指向对象的迭代器
  • pointer_type就是简单的迭代器所指向对象的地址,
  • iterator_category就是之前用的那个类型萃取,萃取出迭代器的名称,作为函数参数,激活函数重载机制,就是利用traits实现的
template<class Category,class T,class Distance = ptrdiff_t,class Pointer=T*,class Reference=T&>
class iterator{
    typedef Category iterator_category;//迭代器的种类
    typedef T        value_type;//元素类型
    typedef Pointer  pointer;//指针
    typedef Reference reference;//引用
     typedef Distance difference_type;
};

如果你希望你所开发的容器能与STL兼容,一定要为你的容器的迭代器定义这五种相应型别。

实际中可以直接继承STL中定义的iterator模板,模板后三个参数都有默认值,因此继承时只需要指定前两个模板参数即可

实例

当然,我在这里实现迭代器的时候,并没有考虑这么多,简化了一些,当然这也无法兼容STL了

template<class T,class Pointer=T*,class Reference=T&>
class iterator{
    typedef T        value_type;//元素类型
    typedef Pointer  pointer;//指针
    typedef Reference reference;//引用
};

现在如果让我们自己设计一个list容器的简单迭代器,应该如何实现呢?

  1. list类需要有操作迭代器的方法
    1. begin/end
    2. insert/erase
  2. list类有一个内部类list_iterator , const_iterator
    1. 有一个成员变量ptr指向list容器中的某个元素
    2. iterator负责重载++、--、*、->等基本操作
  3. list类定义内部类list_iterator的类型别名
//list 双向链表
	template<typename T>
	class _list_node;
	template<class T>
	class list;
	template<typename T, typename Ref, typename Ptr>
	class _list_iterator;


//_list_node
	template<typename T>
	class _list_node
	{
        friend class _list_iterator;
        friend class _list_node;
		_list_node<T>* _prev;
		_list_node<T>* _next;
		T _data;
		_list_node(const T& x = T()) :_prev(nullptr), _next(nullptr), _data(x)
		{}
	};
//list

template<typename T>
	class list
	{
		using node = _list_node<T>;
		node* _head;
	public:
		using iterator =_list_iterator<T, T&, T*> ;
		using const_iterator = _list_iterator<T, const T&, const T*> ;
        iterator begin();
        iterator end();
        const_iterator begin()const;
        const_iterator end()const;
        void insert(iterator pos, const T& x);
        iterator erase(iterator pos);
    }
//_list_iterator
	template<typename T, typename Ref, typename Ptr>
	class _list_iterator
	{
		friend class list<T>;
		using node = _list_node<T>;
		using Self = _list_iterator<T, Ref, Ptr>;
		node* _node;
	public:
        Ref operator*();
        Ptr operator->();
        Self& operator++();
        Self operator++(int);
        Self& operator--();
        Self operator--(int);
        bool operator!=(const Self& it);
        bool operator==(const Self& it);
    }

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://blog.yxqin.top/2021/07/04/cstl
最后更新于:  153  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟