越行勤‘s Blog

C++ 认识STL

闲聊

简单聊一下目前的状态，生病！！生病！！，还是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);
    }

努力成长的程序员

Code happily

© 2024 越行勤‘s Blog