• 【C++MiNiSTL项目开发笔记】

    目录

    Part1-从git与github开始

    Part2-对STL的初步概览

    六大组件

    template

    代码概览

     Part3-源码阅读与剖析

    【分配器】

    C++中的new

    分配器概述

    【迭代器】

    【容器】

     uninitialized系列函数

    【算法】

    【仿函数】

    【适配器】

    Part1-从git与github开始

    GitHub 是一个用于版本控制和协作的代码托管平台，ta能够让你和任何地方的其他工作者一起做项目。

    Git是目前世界上最先进的分布式版本控制系统

    git clone

    用于从github上下载源码

     

    git init

    如果是自己新创建一个文件夹，就在里边git

    然后告诉git管理这个文件夹下的代码

    就是输入git init

    在工作区写完文件夹时，提交

    git add .（如果不是提交这个文件夹下所有的，就把点改成要提交的文件名就行）

    此时，那个文件就会进入准备提交的状态（把文件加入暂存区）

    git comit -m "这里写备注"

    这样，git会以数据库的形式把代码保存在git仓库中

    用git log 来查看提交的历史记录

    git checkout HEAD 要恢复的文件

    Part2-对STL的初步概览

    六大组件

    • 分配器：用来管理内存。
    • 迭代器：将容器和算法粘合在一起，用来遍历STL容器中的部分或全部元素。
    • 容器：封装了大量常用的数据结构。
    • 算法：定义了一些常用算法。
    • 仿函数：具有函数特质的对象。
    • 适配器：主要用来修改接口。

    总结：只有算法实现是函数模板，其他都是类模板 

    template

    STL都用到了template！很重要，在这里复习一下·······················

    在C++中，除了面向对象，还有一种编程思想：泛型编程

    主要基于模板来实现

    【1.函数模板】

     

     

     【2.类模板】

     

    （C++新特性支持自动类型推导了~~~） 

     

     

    类模板做参数 

     

    类模板的继承 

     

     若要灵活指定：

    类模板函数的类外实现 

     

    代码概览

    定义了输出的颜色

     

     Part3-源码阅读与剖析

    【分配器】

    参考文章1

     参考文章2
     

    C++中的new

    new(new operator)做两件事

    调用opeartor new分配内存（operator new会间接调用malloc）

    调用构造函数初始化内存中的对象（placement new）

    同样的，delete负责

    调用析构函数

    调用free释放内存

    分配器概述

    allocate()实现空间的申请

    申请内存分为一级配置器和二级配置器, 分配的空间小于128字节的就调用二级配置器, 大于就直接使用一级配置器, 一级配置器直接调用malloc申请, 二级使用内存池.

    1. template<class T>
    2. inline T* allocate(ptrdiff_t size, T*)
    3. {
    4.     set_new_handler(0);
    5.     T* tmp = (T*)(::operator new(size)(size * sizeof(T)));
    6.     if(!tmp)
    7.     {
    8.         cerr << "out of memort" << endl;
    9.         exit(1);
    10.     }
    11.     return tmp;
    12. }

    construct()实现在已获得的内存里建立一个对象

    1. // 这里的construct调用的是placement new, 在一个已经获得的内存里建立一个对象
    2. template <class T1, class T2>
    3. inline void construct(T1* p, const T2& value) 
    4. {
    5.   new (p) T1(value);
    6. }

    “delete”实现：

    destory()实现调用析构函数，有两个版本

    1. // 第一版本, 接收指针
    2. template <class T> inline void destroy(T* pointer) 
    3. {
    4.     pointer->~T();
    5. }
    1. // 第二个版本的, 接受两个迭代器, 并设法找出元素的类型. 通过__type_trais<> 找出最佳措施
    2. template <class ForwardIterator>
    3. inline void destroy(ForwardIterator first, ForwardIterator last) 
    4. {
    5.   __destroy(first, last, value_type(first));
    6. }
    7.  
    8. // 接受两个迭代器, 以__type_trais<> 判断是否有traival destructor 
    9. template <class ForwardIterator, class T>
    10. inline void __destroy(ForwardIterator first, ForwardIterator last, T*) 
    11. {
    12.   typedef typename __type_traits::has_trivial_destructor trivial_destructor;
    13.   __destroy_aux(first, last, trivial_destructor());
    14. }

     __type_traits为__false_type时

    1. // 没有non-travial destructor 
    2. template <class ForwardIterator>
    3. inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) 
    4. {
    5.   for ( ; first < last; ++first)
    6.     destroy(&*first);
    7. }

    __type_traits为__true_type时

    什么也不做，因为这样效率很高，不需要执行析构函数

    1. // 有travial destructor
    2. template <class ForwardIterator> 
    3. inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

    版本2的特化版 

    1. inline void destroy(char*, char*) {}
    2. inline void destroy(wchar_t*, wchar_t*) {}

    一级分配器（是一个类）

    STL对malloc和free用函数重新进行了封装

    allocate

    1. // 在分配和再次分配中, 都会检查内存不足, 在不足的时候直接调用private中相应的函数
    2. static void * allocate(size_t n)
    3. {
    4.       void *result = malloc(n);
    5.       if (0 == result) result = oom_malloc(n);
    6.       return result;
    7. }

    deallocate

    1. static void deallocate(void *p, size_t /* n */)
    2. {
    3.       free(p); //一级配置器直接调用free释放内存
    4. }

    统一的接口

    1. // 定义符合STL规格的配置器接口, 不管是一级配置器还是二级配置器都是使用这个接口进行分配的
    2. template<class T, class Alloc>
    3. class simple_alloc {
    4.   public:
    5.     static T *allocate(size_t n)
    6.     { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
    7.     static T *allocate(void)
    8.     { return (T*) Alloc::allocate(sizeof (T)); }
    9.     static void deallocate(T *p, size_t n)
    10.     { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
    11.     static void deallocate(T *p)
    12.     { Alloc::deallocate(p, sizeof (T)); }
    13. };

    第二级分配器 

    第一级是直接调用malloc分配空间, 调用free释放空间, 第二级就是建立一个内存池

    用链表来保存不同字节大小的内存块, 就很容易的进行维护, 而且每次的内存分配都直接可以从链表或者内存池中获得, 提升了我们申请内存的效率, 毕竟每次调用malloc和free有开销, 特别是很小内存的时候

    STL将第二级配置器设置为默认的

    3个常量&一个宏操作

    1. // 二级配置器
    2. enum {__ALIGN = 8}; // 设置对齐要求. 对齐为8字节, 没有8字节自动补齐
    3. enum {__MAX_BYTES = 128};   // 第二级配置器的最大一次性申请大小, 大于128就直接调用第一级配置器
    4. enum {__NFREELISTS = __MAX_BYTES/__ALIGN};  // 链表个数, 分别代表8, 16, 32....字节的链表
    1. static size_t FREELIST_INDEX(size_t bytes) \
    2. {\
    3.     return (((bytes) + ALIGN-1) / __ALIGN - 1);\
    4. }

    allocate()

    • 先判断申请的字节大小是不是大于128字节, 是, 则交给第一级配置器来处理. 否, 继续往下执行
    • 找到分配的地址对齐后分配的是第几个大小的链表.
    • 获得该链表指向的首地址, 如果链表没有多余的内存, 就先填充链表.
    • 返回链表的首地址, 和一块能容纳一个对象的内存, 并更新链表的首地址
    1. static void * allocate(size_t n)
    2. {
    3.       obj * __VOLATILE * my_free_list;
    4.       obj * __RESTRICT result;
    5.     
    6.       if (n > (size_t) __MAX_BYTES) 
    7.       {
    8.         return(malloc_alloc::allocate(n)); //大。去调用一级分配器
    9.       }
    10.       my_free_list = free_list + FREELIST_INDEX(n);//看是几号链表负责
    11.       result = *my_free_list;
    12.       if (result == 0) 	// 没有多余的内存, 就先填充链表.
    13.       {
    14.         void *r = refill(ROUND_UP(n));
    15.         return r;
    16.       }
    17.       *my_free_list = result -> free_list_link;
    18.       return (result);
    19. };

    refill()内存填充

    • 向内存池申请空间的起始地址
    • 如果只申请到一个对象的大小, 就直接返回一个内存的大小, 如果有更多的内存, 就继续执行
    • 从第二个块内存开始, 把从内存池里面分配的内存用链表给串起来, 并返回一个块内存的地址给用户
    1. // 内存填充
    2. template <bool threads, int inst>
    3. void* __default_alloc_template::refill(size_t n)
    4. {
    5.   	int nobjs = 20;
    6.   	char * chunk = chunk_alloc(n, nobjs);             // 向内存池申请空间的起始地址
    7.   	obj * __VOLATILE * my_free_list;
    8.   	obj * result;
    9.   	obj * current_obj, * next_obj;
    10.   	int i;
    11.  
    12.   	// 如果只申请到一个对象的大小, 就直接返回一个内存的大小
    13.   	if (1 == nobjs) return(chunk);
    14.   	my_free_list = free_list + FREELIST_INDEX(n);
    15.  
    16.   	// 申请的大小不只一个对象的大小的时候
    17.   	result = (obj *)chunk;
    18.   	// my_free_list指向内存池返回的地址的下一个对齐后的地址
    19.   	*my_free_list = next_obj = (obj *)(chunk + n);
    20.   	// 这里从第二个开始的原因主要是第一块地址返回给了用户, 现在需要把从内存池里面分配的内存用链表给串起来
    21.   	for (i = 1; ; i++) 
    22.   	{
    23. 	    current_obj = next_obj;
    24.     	next_obj = (obj *)((char *)next_obj + n);
    25. 	    if (nobjs - 1 == i) 
    26.         {
    27. 			current_obj -> free_list_link = 0;
    28.       		break;
    29.     	} 
    30.         else 
    31.         {
    32.       		current_obj -> free_list_link = next_obj;
    33.     	}
    34.   		}
    35.   	return(result);
    36. }

    deallocate()

    • 释放的内存大于128字节直接调用一级配置器进行释放
    • 将内存直接还给对应大小的链表就行了, 并不用直接释放内存, 以便后面分配内存
    1. static void deallocate(void *p, size_t n)
    2. {
    3.       obj *q = (obj *)p;
    4.       obj * __VOLATILE * my_free_list;
    5. 	
    6.       // 释放的内存大于128字节直接调用一级配置器进行释放
    7.       if (n > (size_t) __MAX_BYTES) 
    8.       {
    9.         malloc_alloc::deallocate(p, n);
    10.         return;
    11.       }
    12.       my_free_list = free_list + FREELIST_INDEX(n);
    13.       q -> free_list_link = *my_free_list;
    14.       *my_free_list = q;
    15. }

    内存池

    1. // 内存池
    2. template <bool threads, int inst>
    3. char* __default_alloc_template::chunk_alloc(size_t size, int& nobjs)
    4. {
    5.   	char * result;
    6.   	size_t total_bytes = size * nobjs;            // 链表需要申请的内存大小
    7.   	size_t bytes_left = end_free - start_free;    // 内存池里面总共还有多少内存空间
    8.  
    9. 	  // 内存池的大小大于需要的空间, 直接返回起始地址
    10.   	if (bytes_left >= total_bytes) 
    11.   	{
    12. 	    result = start_free;
    13.     	start_free += total_bytes;  // 内存池的首地址往后移
    14. 	    return(result);
    15.   	}
    16.   	// 内存池的内存不足以马上分配那么多内存, 但是还能满足分配一个即以上的大小, 那就按对齐方式全部分配出去
    17.   	else if (bytes_left >= size) 
    18.   	{
    19. 	    nobjs = bytes_left/size;
    20.     	total_bytes = size * nobjs;
    21.     	result = start_free;
    22.     	start_free += total_bytes;  // 内存池的首地址往后移
    23.     	return(result);
    24.   	} 
    25.   	else 
    26.   	{ 
    27. 	    // 如果一个对象的大小都已经提供不了了, 那就准备调用malloc申请两倍+额外大小的内存
    28. 	    size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
    29.     	// Try to make use of the left-over piece.
    30.     	// 内存池还剩下的零头内存分给给其他能利用的链表, 也就是绝不浪费一点.
    31.     	if (bytes_left > 0) 
    32.     	{
    33.       		// 链表指向申请内存的地址
    34.       		obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
    35.       		((obj *)start_free) -> free_list_link = *my_free_list;
    36.       		*my_free_list = (obj *)start_free;
    37.     	}
    38.     	start_free = (char *)malloc(bytes_to_get);
    39.     	// 内存不足了
    40.     	if (0 == start_free) 
    41.     	{
    42.       		int i;
    43.       		obj * __VOLATILE * my_free_list, *p;
    44.       		// 充分利用剩余链表的内存, 通过递归来申请
    45.       		for (i = size; i <= __MAX_BYTES; i += __ALIGN) 
    46.       		{	
    47. 	        	my_free_list = free_list + FREELIST_INDEX(i);
    48. 	        	p = *my_free_list;
    49. 	        	if (0 != p) 
    50. 	            {
    51. 	          		*my_free_list = p -> free_list_link;
    52.           			start_free = (char *)p;
    53. 	          		end_free = start_free + i;
    54.           			return(chunk_alloc(size, nobjs));
    55.     	    	}
    56.       		}
    57.       		// 如果一点内存都没有了的话, 就只有调用一级配置器来申请内存了, 并且用户没有设置处理例程就抛出异常
    58.       		end_free = 0;	// In case of exception.
    59.       		start_free = (char *)malloc_alloc::allocate(bytes_to_get);
    60. 	    }
    61. 	    	// 申请内存成功后重新修改内存起始地址和结束地址, 重新调用chunk_alloc分配内存
    62. 	    	heap_size += bytes_to_get;
    63. 	    	end_free = start_free + bytes_to_get;
    64.     		return(chunk_alloc(size, nobjs));
    65.   	}	
    66. }

    仅供个人理解的总结 

    【迭代器】

    每个组件都可能涉及到对元素的操作，每个组件的数据类型可能不同，所以每个组件可能都要自己设计对自己的操作。将每个组件的实现成统一的接口就是迭代器

    迭代器的优点

    1. 能屏蔽掉底层数据类型差异的
    2. 迭代器将容器和算法粘合在一起, 使版块之间更加的紧凑, 同时提高了执行效率, 让算法更加的得到优化

    这些实现大都通过traits编程实现的. 它的定义了一个类型名规则, 满足traits编程规则就可以自己实现对STL的扩展, 也体现了STL的灵活性. 同时traits编程让程序根据不同的参数类型选择执行更加合适参数类型的处理函数, 也就提高了STL的执行效率. 可见迭代器对STL的重要性


    迭代器最重要的就是对operator*和operator->进行重载，使它表现得像一个指针

    • input iterator(输入迭代器) : 迭代器所指的内容不能被修改, 只读且只能执行一次读操作.
    • output iterator(输出迭代器) : 只写并且一次只能执行一次写操作.
    • forward iterator(正向迭代器) : 支持读写操作且支持多次读写操作.
    • bidirectional iterator(双向迭代器) : 支持双向的移动且支持多次读写操作.
    • random access iterator(随即访问迭代器) : 支持双向移动且支持多次读写操作. p+n, p-n等.

     五种迭代器和其继承关系

    1. struct input_iterator_tag {};
    2. struct output_iterator_tag {};
    3. struct forward_iterator_tag : public input_iterator_tag {};
    4. struct bidirectional_iterator_tag : public forward_iterator_tag {};
    5. struct random_access_iterator_tag : public bidirectional_iterator_tag {};

     都是空类，只是为了调用时通过类选择不同的重载函数，继承是为了，当不存在某种迭代器类型匹配时编译器会根据继承层次向上查找进行传递

    用distance（计算两个迭代器之间的距离）来理解“如何选择最优调用”

    1. template <class InputIterator, class Distance>
    2. inline void distance(InputIterator first, InputIterator last, Distance& n) 
    3. {
    4.   	__distance(first, last, n, iterator_category(first));
    5. }
    6. 	
    7. template <class InputIterator, class Distance>
    8. inline void __distance(InputIterator first, InputIterator last, Distance& n, 
    9.                        input_iterator_tag) 
    10. {
    11.   	while (first != last) 
    12.     { ++first; ++n; }
    13. }
    14.  
    15. template <class RandomAccessIterator, class Distance>
    16. inline void __distance(RandomAccessIterator first, RandomAccessIterator last, 
    17.                        Distance& n, random_access_iterator_tag) 
    18. {
    19.   	n += last - first; //不同的迭代器有自己最佳的效率，通过iterator_category进行最优选择
    20. }

     五类迭代器源码

    1. template <class T, class Distance> struct input_iterator 
    2. {
    3.   	typedef input_iterator_tag iterator_category;
    4.   	typedef T                  value_type;
    5.   	typedef Distance           difference_type;
    6.   	typedef T*                 pointer;
    7.   	typedef T&                 reference;
    8. };
    9.  
    10. struct output_iterator {
    11.   typedef output_iterator_tag iterator_category;
    12.   typedef void                value_type;
    13.   typedef void                difference_type;
    14.   typedef void                pointer;
    15.   typedef void                reference;
    16. };
    17.  
    18. template <class T, class Distance> struct forward_iterator {
    19.   typedef forward_iterator_tag iterator_category;
    20.   typedef T                    value_type;
    21.   typedef Distance             difference_type;
    22.   typedef T*                   pointer;
    23.   typedef T&                   reference;
    24. };
    25.  
    26.  
    27. template <class T, class Distance> struct bidirectional_iterator {
    28.   typedef bidirectional_iterator_tag iterator_category;
    29.   typedef T                          value_type;
    30.   typedef Distance                   difference_type;
    31.   typedef T*                         pointer;
    32.   typedef T&                         reference;
    33. };
    34.  
    35. template <class T, class Distance> struct random_access_iterator {
    36.   typedef random_access_iterator_tag iterator_category;
    37.   typedef T                          value_type;
    38.   typedef Distance                   difference_type;
    39.   typedef T*                         pointer;
    40.   typedef T&                         reference;
    41. };

    在这里介绍一下typename相较于class的主要作用：

    • 对于模板参数是类的时候, typename能够提取(萃取)出该类所定义的参数类型
    1. template<class T>
    2. class people
    3. {
    4. 	public:
    5. 		typedef T	value_type;
    6. 		typedef T*	pointer;
    7. 		typedef T&	reference;
    8. };
    9.  
    10. template<class T>
    11. struct man 
    12. {
    13. 	public:
    14. 		typedef typename T::value_type	value_type;
    15. 		typedef typename T::pointer		pointer;
    16. 		typedef typename T::reference	reference;
    17. 		void print()
    18. 		{
    19. 			cout << "man" << endl;
    20. 		}
    21. };
    22.  
    23. int main()
    24. {
    25. 	manint>> Man;
    26. 	Man.print();
    27.  
    28. 	exit(0);
    29. }

     

    迭代器所指向对象的型别被称为value type. 传入参数的类型可以通过编译器自行推断出来, 但是如果是函数的返回值的话, 就无法通过value type让编译器自行推断出来了. 而traits就解决了函数返回值类型. 同样原生指针不能内嵌型别声明，所以内嵌型别在这里不适用, 迭代器无法表示原生指针(int *, char *等称为原生指针)
    ---------->这些问题如何被解决

     iterator_traits结构

    使用typename对参数类型进行萃取，并且对参数类型再进行一次命名

    1. template <class Iterator>
    2. struct iterator_traits {
    3.   typedef typename Iterator::iterator_category iterator_category;	//迭代器类型
    4.   typedef typename Iterator::value_type        value_type;			// 迭代器所指对象的类型
    5.   typedef typename Iterator::difference_type   difference_type;		// 两个迭代器之间的距离
    6.   typedef typename Iterator::pointer           pointer;				// 迭代器所指对象的类型指针
    7.   typedef typename Iterator::reference         reference;			// 迭代器所指对象的类型引用
    8. };

     上面的traits结构体并没有对原生指针做处理, 所以还要为特化, 偏特化版本(即原生指针)做统一

    1. // 针对原生指针 T* 生成的 traits 偏特化
    2. template <class T>
    3. struct iterator_traits {
    4.   typedef random_access_iterator_tag iterator_category;
    5.   typedef T                          value_type;
    6.   typedef ptrdiff_t                  difference_type;
    7.   typedef T*                         pointer;
    8.   typedef T&                         reference;
    9. };
    10. // 针对原生指针 const T* 生成的 traits 偏特化
    11. template <class T>
    12. struct iterator_traits<const T*> {
    13.   typedef random_access_iterator_tag iterator_category;
    14.   typedef T                          value_type;
    15.   typedef ptrdiff_t                  difference_type;
    16.   typedef const T*                   pointer;
    17.   typedef const T&                   reference;
    18. };

     

     __type_traits

    iterator_traits是萃取迭代器的特性，而__type_traits是萃取型别的特性

    萃取型别如下：

     编译器会为每个类构造以上四种默认的函数，如果没有定义自己的，就会用编译器默认函数，如果使用默认的函数，我们可以使用memcpy(),memmove(),malloc()等函数来加快速度，提高效率

    __iterator_traits允许针对不同的型别属性在编译期间决定执行哪个重载函数而不是在运行时才处理, 这大大提升了运行效率. 这就需要STL提前做好选择的准备. 是否为POD, non-trivial型别用__true_type和__false_type 来区分

    （之前的空间配置器就提过）

    __true_type和__false_type不是bool值，因为需要在编译期间就决定使用哪个函数。

    将它们表现为空类——无额外负担，能表示真假，还能在编译时类型推导确定执行相应的函数

    1. struct __true_type {};
    2. struct __false_type {};

     __type_traits源码

    1. __STL_TEMPLATE_NULL struct __type_traits<char> {
    2.    typedef __true_type    has_trivial_default_constructor;
    3.    typedef __true_type    has_trivial_copy_constructor;
    4.    typedef __true_type    has_trivial_assignment_operator;
    5.    typedef __true_type    has_trivial_destructor;
    6.    typedef __true_type    is_POD_type;
    7. };
    8.  
    9. __STL_TEMPLATE_NULL struct __type_traits<signed char> {
    10.    typedef __true_type    has_trivial_default_constructor;
    11.    typedef __true_type    has_trivial_copy_constructor;
    12.    typedef __true_type    has_trivial_assignment_operator;
    13.    typedef __true_type    has_trivial_destructor;
    14.    typedef __true_type    is_POD_type;
    15. };
    16.  
    17. ...

    以上是将基础的类型都设置为__true_type型别

     这里将指针进行特化处理, 同样是__true_type型别

    1. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    2.  
    3. template <class T>
    4. struct __type_traits {
    5.    typedef __true_type    has_trivial_default_constructor;
    6.    typedef __true_type    has_trivial_copy_constructor;
    7.    typedef __true_type    has_trivial_assignment_operator;
    8.    typedef __true_type    has_trivial_destructor;
    9.    typedef __true_type    is_POD_type;
    10. };
    11.  
    12. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    13.  
    14. struct __type_traits<char*> {
    15.    typedef __true_type    has_trivial_default_constructor;
    16.    typedef __true_type    has_trivial_copy_constructor;
    17.    typedef __true_type    has_trivial_assignment_operator;
    18.    typedef __true_type    has_trivial_destructor;
    19.    typedef __true_type    is_POD_type;
    20. };
    21.  
    22. struct __type_traits<signed char*> {
    23.    typedef __true_type    has_trivial_default_constructor;
    24.    typedef __true_type    has_trivial_copy_constructor;
    25.    typedef __true_type    has_trivial_assignment_operator;
    26.    typedef __true_type    has_trivial_destructor;
    27.    typedef __true_type    is_POD_type;
    28. };
    29.  
    30. struct __type_traits<unsigned char*> {
    31.    typedef __true_type    has_trivial_default_constructor;
    32.    typedef __true_type    has_trivial_copy_constructor;
    33.    typedef __true_type    has_trivial_assignment_operator;
    34.    typedef __true_type    has_trivial_destructor;
    35.    typedef __true_type    is_POD_type;
    36. };

     

     SGI对traits进行扩展，使得所有类型都满足traits编程规范, 这样SGI STL算法可以通过__type_traits获取类型信息在编译期间就能决定出使用哪一个重载函数, 解决了template是在运行时决定重载选择的问题. 并且通过true和false来确定POD和travial destructor, 让程序能选择更加符合其类型的处理函数, 大大提高了对基本类型的快速处理能力并保证了效率最高

    再好好理解复习一下啥是萃取器

    iterator_traits：是一个特性类，用来定义迭代器的属性

    一个算法的实现需要迭代器向算法提供这些信息：
    （1）difference_type：表示从另一个迭代器减去一个迭代器的结果的类型。
    （2）value_type：迭代器可以指向的元素的类型。
    （3）pointer：迭代器可以指向的元素的指针类型。
    （4）reference：迭代器可以指向的元素的引用类型。
    （5）iterator_category：迭代器类别。 可以是以下之一：
    input_iterator_tag
    output_iterator_tag
    forward_iterator_tag
    bidirectional_iterator_tag
    random_access_iterator_tag
     

    iterator_traits在算法中充当的角色：通过使用相应的iterator_traits实例化的成员来将迭代器以上所列的五个信息传递给算法 

    【容器】

    容器封装了大量常用的数据结构

    容器分为序列式和关联式

    序列式：vector list deque等，序列容器有头或尾，甚至有头有尾

    关联式：map set hashtable等，没有所谓头尾，只有最大值，最小值

     uninitialized系列函数

    uninitialized_copy功能 : 从first到last范围内的元素复制到从 result地址开始的内存

    1. template <class InputIterator, class ForwardIterator>
    2. inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
    3.                      ForwardIterator result) {
    4.   return __uninitialized_copy(first, last, result, value_type(result));
    5. }
    1. inline char* uninitialized_copy(const char* first, const char* last,
    2.                                 char* result) {
    3.   memmove(result, first, last - first);
    4.   return result + (last - first);
    5. }
    6.  
    7. inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
    8.                                    wchar_t* result) {
    9.   memmove(result, first, sizeof(wchar_t) * (last - first));
    10.   return result + (last - first);
    11. }

     __uninitialized_copy函数

    1. template <class InputIterator, class ForwardIterator, class T>
    2. inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
    3.                      ForwardIterator result, T*) {
    4.   typedef typename __type_traits::is_POD_type is_POD;
    5.   return __uninitialized_copy_aux(first, last, result, is_POD());
    6. }

     __uninitialized_copy使用了typename进行萃取, 并且萃取的类型是POD, 看来这里准备对__uninitialized_copy 进行最优化处理了, 我们接着来分析它是怎么实现优化处理的

    1. template <class InputIterator, class ForwardIterator> 
    2. inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
    3.                          ForwardIterator result,
    4.                          __true_type) {
    5.   return copy(first, last, result);
    6. }
    7.  
    8. template <class InputIterator, class ForwardIterator>
    9. ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
    10.                          ForwardIterator result,
    11.                          __false_type) {
    12.   ForwardIterator cur = result;
    13.   __STL_TRY {
    14.     for ( ; first != last; ++first, ++cur)
    15.       construct(&*cur, *first);
    16.     return cur;
    17.   }
    18.   __STL_UNWIND(destroy(result, cur));
    19. }

     uninitialized_copy_n也做了跟uninitialized_copy类似的处理, 只是它是采用tratis编程里iterator_category迭代器的类型来选择最优的处理函数.

    1. template <class InputIterator, class Size, class ForwardIterator>
    2. inline pair
    3. uninitialized_copy_n(InputIterator first, Size count,
    4.                      ForwardIterator result) {
    5.   return __uninitialized_copy_n(first, count, result, iterator_category(first)); // 根据iterator_category选择最优函数
    6. }
    7.  
    8. template <class InputIterator, class Size, class ForwardIterator>
    9. pair
    10. __uninitialized_copy_n(InputIterator first, Size count, ForwardIterator result,
    11.                        input_iterator_tag) // input_iterator_tag类型的迭代器
    12. {
    13.   ForwardIterator cur = result;
    14.   __STL_TRY {
    15.     for ( ; count > 0 ; --count, ++first, ++cur) 
    16.       construct(&*cur, *first);
    17.     return pair(first, cur);
    18.   }
    19.   __STL_UNWIND(destroy(result, cur));
    20. }
    21.  
    22. template <class RandomAccessIterator, class Size, class ForwardIterator>
    23. inline pair
    24. __uninitialized_copy_n(RandomAccessIterator first, Size count, ForwardIterator result,
    25.                        random_access_iterator_tag) // random_access_iterator_tag类型的迭代器
    26. {
    27.   RandomAccessIterator last = first + count;
    28.   return make_pair(last, uninitialized_copy(first, last, result));
    29. }

    uninitialized_fill功能 : 从first到last范围内的都填充为 x 的值.

    uninitialized_fill采用了与uninitialized_copy一样的处理方法选择最优处理函数, 这里就不过多的分析了

    1. template <class ForwardIterator, class T>
    2. inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) 
    3. {
    4.   __uninitialized_fill(first, last, x, value_type(first));
    5. }
    6.  
    7. template <class ForwardIterator, class T, class T1>
    8. inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last,  const T& x, T1*)
    9. {
    10.   typedef typename __type_traits::is_POD_type is_POD;
    11.   __uninitialized_fill_aux(first, last, x, is_POD());
    12.                    
    13. }
    14.  
    15. template <class ForwardIterator, class T>
    16. inline void
    17. __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,  const T& x, __true_type)
    18. {
    19.    fill(first, last, x);
    20. }
    21.  
    22. template <class ForwardIterator, class T>
    23. void
    24. __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, __false_type)
    25. {
    26.   ForwardIterator cur = first;
    27.   __STL_TRY {
    28.     for ( ; cur != last; ++cur)
    29.       construct(&*cur, x);
    30.   }
    31.   __STL_UNWIND(destroy(first, cur));
    32. }

     uninitialized_fill_n功能 : 从first开始n 个元素填充成 x 值

    1. template <class ForwardIterator, class Size, class T>
    2. inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x) 
    3. {
    4.   return __uninitialized_fill_n(first, n, x, value_type(first));
    5. }
    6.  
    7. template <class ForwardIterator, class Size, class T, class T1>
    8. inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, T1*) 
    9. {
    10.   typedef typename __type_traits::is_POD_type is_POD;
    11.   return __uninitialized_fill_n_aux(first, n, x, is_POD());                                
    12. }
    13.  
    14. template <class ForwardIterator, class Size, class T>
    15. inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type) 
    16. {
    17.   return fill_n(first, n, x);
    18. }
    19.  
    20. template <class ForwardIterator, class Size, class T>
    21. ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type) 
    22. {
    23.   	ForwardIterator cur = first;
    24.   	__STL_TRY 
    25.   	{
    26.    		for ( ; n > 0; --n, ++cur)
    27.      	 	construct(&*cur, x);
    28.     	return cur;
    29.   	}
    30.   	__STL_UNWIND(destroy(first, cur));
    31. }

      

     uninitialized_copy是为两段内存进行复制的函数, uninitialized_fill是为对一段内存进行初始化一个值的函数. 两者都对了traits编程中的迭代器类型和__type_traits定义的__false_type和__true_type的不同执行不同的处理函数, 也使效率最优化

    序列容器 

    **************************************************vector**************************************************** 

    【STL***vector容器一】_Micmic33的博客-CSDN博客

    【STL***vector容器二】_Micmic33的博客-CSDN博客

    【STL***vector容器三】_Micmic33的博客-CSDN博客

     

     

     

    **************************************************list****************************************************  

    【STL***list容器一】_Micmic33的博客-CSDN博客

    【STL***list容器二】_Micmic33的博客-CSDN博客

    【STL***list容器三】_Micmic33的博客-CSDN博客

     

     

     

     

     **************************************************deque**************************************************** 

    【STL***deque容器一】_Micmic33的博客-CSDN博客

    【STL***deque容器二】_Micmic33的博客-CSDN博客

    【STL***deque容器三】_Micmic33的博客-CSDN博客

     

     

     

     *****************************************stack&queue************************************************* 

     (37条消息) 【STL***stack配接器】_Micmic33的博客-CSDN博客

    (37条消息) 【STL***queue配接器】_Micmic33的博客-CSDN博客

     

    关联容器 

    (39条消息) 【STL***关联式容器】_Micmic33的博客-CSDN博客 

    【算法】

    挺多的，都是基于函数模板

    【仿函数】

    仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符

     为什么选择仿函数而不是函数指针

    1. 函数指针不能满足STL的抽象性
    2. 函数指针不能与STL的其他组件搭配, 不够灵活
    3. 仿函数具有可配接性, 可以满足traits编程, 也是能在编译期间就能完成, 不会有运行时的开销
    1. //算术类仿函数 + - * / %
    2. //plus仿函数，生成一个对象，里面仅仅有一个函数重载的方法。
    3. template <class T>
    4. struct plus : public binary_function {
    5.     T operator()(const T& x, const T& y) const { return x + y; }
    6. };
    7.  
    8. //minus仿函数
    9. template <class T>
    10. struct minus : public binary_function {
    11.     T operator()(const T& x, const T& y) const { return x - y; }
    12. };
    13.  
    14. template <class T>
    15. struct multiplies : public binary_function {
    16.     T operator()(const T& x, const T& y) const { return x * y; }
    17. };
    18.  
    19. template <class T>
    20. struct divides : public binary_function {
    21.     T operator()(const T& x, const T& y) const { return x / y; }
    22. };
    23. template <class T>
    24. struct modulus : public binary_function {
    25.     T operator()(const T& x, const T& y) const { return x % y; }
    26. };
    27.  
    28. //取负值
    29. template <class T>
    30. struct negate : public unary_function {
    31.     T operator()(const T& x) const { return -x; }
    32. };

     使用：

    1. #include      // std::cout
    2. #include    // std::plus
    3. #include     // std::transform
    4. using namespace std;
    5. int main(void)
    6. {
    7.     cout << minus<int>()(10,5) << endl;//5
    8.     cout << multiplies<int>()(10,5) << endl;//50
    9.     cout << divides<int>()(10,5) << endl;//2
    10.     cout << modulus<int>()(10,5) << endl;//0
    11.     cout << negate<int>()(10) << endl;//-10
    12.     return 0;
    13. }

    【适配器】

    配接器就像转接口一样, 将一个对class封装变成了另外一个功能的class

    适配器可以应用于：仿函数，迭代器，容器

  • 相关阅读:
    一个信号间相互干扰问题的发现及解决方法
    【REACT-router】
    数据结构第29节 后缀树和后缀数组
    swagger-01-swagger介绍
    World Tour Finals 2019 D - Distinct Boxes 题解
    Python OCR 文字检测使用模型：读光-文字检测-DBNet行检测模型-中英-通用领域
    软考中级—— 操作系统知识
    强化学习-DDPG算法
    临门一脚踢不进？面试官就是不要我？程序员面试隐藏加分项你做对了吗？！
    网课没有摄像头，手机如何变成电脑摄像头？
  • 原文地址：https://blog.csdn.net/weixin_53459056/article/details/126769754