[C++知识库]C++:线上课程3_4——3_5(alloc)

一、lambda表达式

1.mutable关键字

int main()
{
	int a = 0;
	auto f1 = [=]
	{
		return a++;//error，修改按值捕获的外部变量
	};
	auto f2 = [=]() mutable
	{
		return a++;//ok
	}
}

class Object
{
	int value;
	mutable int num;
public:
	Object(int x = 0, int y = 0) :value{ x }, num{ y } {}//列表初始化

	int fun() const
	{
		int a = 10;
		a += 10;
		num += 10;//加上mutable关键字才可编译成功
		return value + num;
	}
};

从上面的例子中我们知道，按值捕获得到的外部变量值是在lambda表达式定义时的值。此时所有外部变均被复制了一份存储在lambda表达式变量中。此时虽然修改lambda 表达式中的这些外部变量并不会真正影响到外部，我们却仍然无法修改它们。

那么如果希望去修改按值捕获的外部变量应当怎么办呢?这时，需要显式指明lambda表达式mutable

需要注意的一点是，被 mutable修饰的lambda表达式就算没有参数也要写明参数列表。

2. lambda表达式代码示例

template <class _BI ,class _Fn>
void my_for_each(_BI _first, _BI _last, _Fn _func)
{
	cout << typeid(_Fn).name() << endl;
	for (; _first != _last; ++first)
	{
		_func(*_first);
	}
}
void Print_Ar(int x)//函数指针
{
	printf("%d", x);
}
struct Print//仿函数
{
	void operator()(int x) const
	{
		printf("%d", x);
	}
};
int main()
{
	std::vector<int> ar = { 12,23,34,45,56,67,78 };
	my_for_each(ar.begin(), ar.end(), Print_Ar);
	cout << endl;
	my_for_each(ar.begin(), ar.end(), Print());
	cout << endl;
	//lambda表达式
	my_for_each(ar.begin(), ar.end(), [](int a)->void {printf("%d", a); });
	cout << endl;

	return 0;
}

二、 STL源码剖析（项目）

1. 迭代器

迭代器是一种抽象的设计概念，语言中并没有直接对应于这个概念的事物。《design patterns》一书提供有23种设计样式的完整描述，iterator样式定义如下：提供一种方法，使得依序寻访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

STL中心思想是将资料容器和演算法分离，彼此独立设计。

2. 代码示例

find适合list容器，也适合查找vector容器

using namespace std;
template<class _BI,class _Ty>
_BI my_find(_BI _first, _BI _last, const _Ty& val)
{
	cout << typeid(_BI).name() << endl;
	for (; _first != _last; ++_first)
	{
		if (*_first == val)
		{
			break;
		}
	}
	return _first;
}
int main()
{
	vector<int> ivec = { 12,23,34,45,56 };
	list<int> ilist = { 1,2,3,4,5,6 };
	deque<int> de = { 12,23,34,45 };

	vector<int>::iterator it = my_find(ivec.begin(), ivec.end(), 12);
	list<int>::iterator il = my_find(ilist.begin(), ilist.end(), 2);

	return 0;
}

3. 迭代器相应型别

3.1 value type

指得带起所指物件的型别，迭代器在迭代容器时候，除了访问数据，还要指明数据类型

3.2 diefference type

表示迭代器之间的距离，因此，它可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。

3.3 reference type

• 常性迭代器：不允许改变所指之物
• 普通迭代器：允许改变所指之物

3.4 pointer type（指针类型）

• 常性指针地址
• 普通指针地址

Item operator*() const
{
	return *ptr;
}
Item operator->() const
{
	return ptr;
}

3.5 iterator_category（迭代器相应型别）

是否能对数据操作的动作，把迭代器分为五类：

• input iterator：只读迭代器
• output iterator：可写迭代器
• forword iterator：正向迭代器
• bidirectional iterator：双向迭代器
• random access iterator：随机迭代器

4.代码示例

编译时候确定调用关系

my_iterator.h

#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H

namespace h
{
typedef int ptrdiff_t;

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forword_iterator_tag :public input_iterator_tag {};
struct bidirectional_iterator_tag :public forword_iterator_tag {};
struct random_access_iterator_tag :public bidirectional_iterator_tag {};

template<class _C,class _Ty,class _D=ptrdiff_t,class _Pointer=_Ty*,class _Reference=_Ty&>
struct iterator
{
	typedef _C               iterator_category;//迭代器类型
	typedef _Ty              value_type;//迭代器迭代数据之物
	typedef _D               difference_type;//差值
	typedef _Pointer         pointer;//指针
	typedef _Reference       reference;//引用类型
};

//类型萃取（泛化版本）
template<class _Iterator>
struct iterator_traits
{
	//构造函数
	iterator_traits() {}
	typedef typename _Iterator::iterator_category   iterator_category;//迭代器类型
	typedef typename _Iterator::value_type          value_type;//迭代器迭代数据之物
	typedef typename _Iterator::difference_type     difference_type;//差值
	typedef typename _Iterator::pointer             pointer;//指针
	typedef typename _Iterator::reference           reference;//引用类型
};

//类型萃取（特化版本）-裸指针
template<class T>
struct iterator_traits<T*>
{
	//构造函数
	iterator_traits() {}
	typedef typename random_access_iterator_tag   iterator_category;//迭代器类型
	typedef typename T                            value_type;//迭代器迭代数据之物
	typedef typename int                          difference_type;//差值
	typedef typename T*                           pointer;//指针
	typedef typename T&                           reference;//引用类型
};
//类型萃取（部分特化版本）-常性指针
template<class T>
struct iterator_traits<const T*>
{
	//构造函数
	iterator_traits() {}
	typedef typename random_access_iterator_tag   iterator_category;//迭代器类型
	typedef typename T                            value_type;//迭代器迭代数据之物
	typedef typename int                          difference_type;//差值
	typedef typename const T*                     pointer;//指针
	typedef typename const T&                     reference;//引用类型
};
//SGI
template<class _II>
inline typename iterator_traits<_II>::iterator_category
iterator_category(const _II&)
{
	typedef typename iterator_traits<_II>::iterator_category cate;
	return cate();
}

//SGI——萃取值类型
template<class _II>
inline typename iterator_traits<_II>::value_type*
value_type(const _II&)
{
	//强转为指针类型
	return static_cast<typename iterator_traits<_II>::value_type*>(0);
}
//正向迭代器
template<class _Ty,class _D>
struct _Forit :public iterator<forword_iterator_tag, _Ty, _D> {};

//双向迭代器
template<class _Ty,class _D>
struct _Bidit :public iterator<bidirectional_iterator_tag, _Ty, _D> {};

//随机迭代器
template<class _Ty,class _D=ptrdiff_t>
struct _Ranit :public iterator<random_access_iterator_tag, _Ty, _D> {};

template<class _II,class _D>
inline void __advance(_II& i, _D n, input_iterator_tag)
{
	while (n--) ++i;
}

template<class _BI, class _D>
inline void __advance(_BI& i, _D n, bidirectional_iterator_tag)
{
	if (n >= 0)//正向
	{
		while (n--) ++i;
	}
	else//逆向
	{
		while (n++) --i;
	}
}

template<class _RAI, class _D>
inline void __advance(_RAI& i, _D n, random_access_iterator_tag)
{
	i += n;
}

template<class _II,class _D>
inline void advance(_II& i, _D n)
{
	iterator_traits<_II>();
	typedef typename iterator_traits<_II>::iterator_category cate;
	__advance(i, n, cate());
	//__advance(i, n, iterator_category(i));
}

//一个一个，效率低下，但是适用于所有迭代器
template<class _II>
inline typename iterator_traits<_II>::difference_type
__distance(_II _F, _II _L, input_iterator_tag)
{
	inline typename iterator_traits<_II>::difference_type n = 0;
	while (_F != _L)
	{
		_F++;
		n++;
	}
	return n;
}

//随机迭代器
template<class _RAI>
inline typename iterator_traits<_RAI>::difference_type
__distance(_RAI _F, _RAI _L, random_access_iterator_tag)
{
	return _L = _F;
}

//计算差值的函数
template<class _II>
inline typename iterator_traits<_II>::difference_type
distance(_II _F, _II _L)
{
	return __distance(_F, _L, iterator_category(_F));
}

}


#endif

my_list.h

#ifndef MY_LIST_H
#define MY_LIST_H
#include"my_iterator.h"
namespace h
{
template<class _Ty>
class my_list
{
public:
	class iteratir;
	class const_iterator;
	//双向迭代器
	class const_iterator :public h::_Bidit<_Ty, int> {};
	class iterator :public const_iterator {};
};
}
#endif

my_vector.h

#ifndef MY_VECTOR_H
#define MY_VECTOR_H
#include"my_iterator.h"
namespace h
{
template<class _Ty>
class my_vector
{
public:
	class iteratir;
	class const_iterator;
	//随机迭代器
	class const_iterator :public h::_Ranit<int, int> {};
	class iterator :public const_iterator {};
};
}
#endif

my_hash_table.h

#ifndef MY_HASHTABLE_H
#define MY_HASHTABLE_H
#include"my_iterator.h"
namespace h
{
	template<class _Ty>
class my_hashtable
{
public:
	class iterator;
	class const_iterator;
	//正向迭代器
	class const_iterator :public h::_Forit<_Ty, int> {};
	class iterator :public const_iterator {};
};
}
#endif

int main

#include<queue>
#include<unordered_map>
#include<set>
#include"my_iterator.h"
#include"my_list.h"
#include"my_vector.h"
#include"my_hash_table.h"

using namespace std;

int main()
{
	vector<int> ar = { 12,23,34,45,56 };//随机迭代器
	list<int> ilist = { 1,2,3,4,5,6,7 };//双向迭代器

	std::vector<int>::iterator sit = ar.begin();
	std::vector<int>::iterator eit = ar.end();

	//计算差值函数,计算两迭代器之间的距离
	int len = std::distance(eit, sit);
	len = std::distance(ilist.end(), ilist.begin());

	return 0;
}

my_type_traits

#ifndef MY_TYPE_TRAITS_H
#define MY_TYPE_TRAITS_H
namespace h
{
	//类型萃取
	struct __true_type {};
	struct __false_type {};

	template<class type>
	struct __type_traits
	{
		typedef __true_type  this_dummy_member_must_be_first;
		typedef __false_type  has_trivial_default_constructor;
		typedef __false_type  has_trivial_copy_constructor;
		typedef __false_type  has_trivial_assignment_operator;
		typedef __false_type  has_trivial_destructor;
		typedef __false_type  is_POD_type; // struct int 
	};
	//特化版本
	template<> struct __type_traits<char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//有符号特化版本
	template<> struct __type_traits<signed char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//无符号特化版本
	template<> struct __type_traits<unsigned char>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//短整型特化版本
	template<> struct __type_traits<short>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//无符号短整型特化版本
	template<> struct __type_traits<unsigned short>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//整型特化版本
	template<> struct __type_traits<int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//无符号整型特化版本
	template<> struct __type_traits<unsigned int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//长整型特化版本
	template<> struct __type_traits<long int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//无符号长整型特化版本
	template<> struct __type_traits<unsigned long int>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	
	template<> struct __type_traits<long long>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<unsigned long long>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	template<> struct __type_traits<float>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<double>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};

	template<> struct __type_traits<long double>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
	//指针
	template<class T>
	struct __type_traits<T*>
	{
		typedef __true_type  has_trivial_default_constructor;
		typedef __true_type  has_trivial_copy_constructor;
		typedef __true_type  has_trivial_assignment_operator;
		typedef __true_type  has_trivial_destructor;
		typedef __true_type  is_POD_type; // struct int 
	};
}
#endif

my_alloc.h

#ifndef MY_ALLOC_H
#define MY_ALLOC_H
#include<iostream>

namespace h
{
#if 0
#include<new>
#define __THROW_BAD_ALLOC throw std::bad_alloc;
#elif !defined(__THROW_BAD_ALLOC)
#define __THROW_BAD_ALLOC std::cerr<<"out of memory"<<std::endl; exit(1)
#endif

	template<int inst>
	//一级空间配置器
	class __malloc_alloc_template
	{
	public:
		using PFUN = void (*)();
	private:
		//当allocate函数申请空间不足时候调用
		static void* oom_malloc(size_t n)
		{
			void* result = NULL;
			void (*my_malloc_handler) () = nullptr;
			for (;;)
			{
				my_malloc_handler = __malloc_alloc_oom_handler;
				if (nullptr == my_malloc_handler)
				{
					__THROW_BAD_ALLOC;//宏抛出异常，或者终止程序
				}
				//释放更多内存
				my_malloc_handler();
				result = malloc(n);
				if (nullptr != result)
				{
					return result;
				}
			}
		}
		//当reallocate函数扩容不足时候调用
		static void* oom_realloc(void* p, size_t new_sz)
		{
			void* result = NULL;
			void (*my_malloc_handler) () = nullptr;
			for (;;)
			{
				my_malloc_handler = __malloc_alloc_oom_handler;
				if (nullptr == my_malloc_handler)
				{
					__THROW_BAD_ALLOC;
				}
				my_malloc_handler();
				result = realloc(p, new_sz);
				if (nullptr != result)
				{
					return result;
				}
			}
		}
		//函数指针——解决内存不足问题
		static PFUN __malloc_alloc_oom_handler;
	//用户函数
	public:
		//申请空间
		static void* allocate(size_t n)
		{
			void* result = malloc(n);
			if (nullptr == result)
			{
				result = oom_malloc(n);
			}
			return result;
		}
		//释放空间
		static void deallocate(void* p, size_t n)
		{
			free(p);
		}
		//扩容函数
		static void* reallocate(void* p, size_t old_sz, size_t new_sz)
		{
			void* result = realloc(p, new_sz);
			if (nullptr == result)
			{
				result = oom_realloc(p, new_sz);
			}
			return result;
		}
		//解决内存不足情况
		static  PFUN set_malloc_handler(PFUN p)
		{
			PFUN old = __malloc_alloc_oom_handler;
			__malloc_alloc_oom_handler = p;
			return old;
		}
	};
	template<int inst>
	typename __malloc_alloc_template<inst>::PFUN
		//类型名里面的静态成员
		__malloc_alloc_template<inst>::__malloc_alloc_oom_handler = nullptr;

	//typedef __malloc_alloc_template<0> malloc_alloc;
	using malloc_alloc = __malloc_alloc_template<0>;//重命名

	enum { __ALIGN = 8 };
	enum { __MAX_BYTES = 128 };
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 16

	template<bool threads, int inst>
	class __default_alloc_template
	{
	private:
		union obj
		{
			union obj* free_list_link; // next;
			//char client_data[1];
		};
	private:
		//自由链表
		static obj* volatile free_list[__NFREELISTS];
		//内存池的起始位置
		static char* start_free;
		static char* end_free;
		static size_t heap_size;//从堆区申请的总空间数
		//提升函数：8的倍数
		static size_t ROUND_UP(size_t bytes)
		{
			return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
		}
		//哈希函数：申请块的数字
		static size_t FREELIST_INDEX(size_t bytes)
		{
			return (bytes + __ALIGN - 1) / __ALIGN - 1;
		}
		//填充函数
		static char* chunk_alloc(size_t size, int& nobjs);
		static void* refill(size_t size);
	public:
		static void* allocate(size_t size)
		{
			if (size > (size_t)__MAX_BYTES)
			{
				return malloc_alloc::allocate(size);//转给一级配置器
			}
			obj* result = nullptr;
			obj* volatile* my_free_list = nullptr;//链表
			my_free_list = free_list + FREELIST_INDEX(size);
			result = *my_free_list;
			if (nullptr == result)
			{

			}
			*my_free_list = result->free_list_link;
			return result;
		}
		static void deallocate(void* p, size_t n)
		{
			if (n > (size_t)__MAX_BYTES)
			{
				malloc_alloc::deallocate(p, n);
				return;
			}

		}
		static void* reallocate(void* p, size_t old_sz, size_t new_sz); // 
	};


	template<bool threads, int inst>
	typename __default_alloc_template<threads, inst>::obj* volatile
		__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {};

	template<bool threads, int inst>
	char* __default_alloc_template<threads, inst>::start_free = nullptr;

	template<bool threads, int inst>
	char* __default_alloc_template<threads, inst>::end_free = nullptr;

	template<bool threads, int inst>
	size_t __default_alloc_template<threads, inst>::heap_size = 0;


}
#endif

my_construct.h

#ifndef MY_CONSTRUCT_H
#define MY_CONSTRUCT_H
#include"my_iterator.h"
#include"my_type_traits.h"
namespace h
{
	template<class T1, class T2>
	inline void construct(T1* p, const T2& val)
	{
		new (p) T1(val);//定位new构建
	}
	template<class T>
	inline void construct(T* p)
	{
		new (p) T();
	}

	template<class T>
	inline void destroy(T* p)
	{
		p->~T();
	}
	template<class _FI>
	inline void __destroy_aux(_FI _F, _FI _L, h::__true_type)
	{}
	template<class _FI>
	inline void __destroy_aux(_FI _F, _FI _L, h::__false_type)
	{
		for (; _F != _L; ++_F)
		{
			destroy(&*_F);//只析构迭代器所指对象，迭代器本身并未失效
		}
	}
	template<class _FI, class T>
	inline void __destroy(_FI _F, _FI _L, T*) // value_type;
	{
		//cout << typeid(T).name() << endl;
		//h::__type_traits<T>();
		typedef typename yhp::__type_traits<T>::has_trivial_destructor dest;
		__destroy_aux(_F, _L, dest());
	}
	template<class _FI>
	inline void destroy(_FI _F, _FI _L)
	{
		__destroy(_F, _L, yhp::value_type(_F));
	}
}
#endif

三、 空间配置器

1. 概念

总是隐藏在一切组件，容器的背后，整个STL所有操作对象都存放在容器中，容器一定需要配置空间以存放对象。空间不一定来自于内存。

2. 内存设计

对象构建前的空间配置，和对象析构的空间释放，由<atl_alloc.h>负责，SGL设计如下：

• 向系统堆空间要求空间
• 考虑多线程情况
• 考虑内存不足情况
• 考虑小段内存造成内存破碎问题

3.内存池

一级配置器和二级配置器

3.1二级配置器

申请空间太多太小的空间造成内存遂安，额外负担无法避免，毕竟系统要靠多出来的空间来管理内存，额外负担所占的比例就越大，空间浪费越大。
如果申请的内存块足够大，大于128，

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖