您现在的位置是：首页 > 工具

当前栏目

STL：源码剖析(部分）—— 目录

源码目录部分剖析 STL

2023-09-27 14:29:24 时间

文章目录

迭代器
- 迭代器剖析
- my_iterator.h
类型萃取
- 类型萃取剖析
- my_type_traits.h
构造和析构
- 源码剖析
- my_construct.h
空间配置器

迭代器

my_iterator.h

#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H

namespace Srh
{

typedef int ptrdiff_t;

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

template<typename _C, typename _Ty, typename _D = ptrdiff_t,
	typename _Pointer = _Ty*, typename _Reference = _Ty&>
	struct iterator
{
	typedef _C			iterator_category;
	typedef _Ty			value_type;
	typedef _D          difference_type;
	typedef _Pointer    pointer;
	typedef _Reference  reference;
};

// 类型萃取
template<typename _Iterator>
struct iterator_traits
{
	//ietrator_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<typename T>
struct iterator_traits<T*>
{
	typedef typename random_access_iterator_tag   iterator_category;
	typedef typename T							  value_type;
	typedef typename ptrdiff_t					  difference_type;
	typedef typename T* pointer;
	typedef typename T& reference;
};

// 常性指针（偏特化版本）
template<typename T>
struct iterator_traits<const T*>
{
	typedef typename random_access_iterator_tag   iterator_category;
	typedef typename T							  value_type;
	typedef typename ptrdiff_t					  difference_type;
	typedef typename const T* pointer;
	typedef typename const T& reference;
};

// 决定某个迭代器类型
template<typename _Iterator>
inline typename iterator_traits<_Iterator>::iterator_category
iterator_category(const _Iterator&) {
	typedef typename iterator_traits<_Iterator>::iterator_category category;
	return category();
}

// 决定某个迭代器的distance_type
template<typename _Iterator>
inline typename iterator_traits<_Iterator>::difference_type*
distance_type(const _Iterator&) {
	return static_cast<typename iterator_traits<_Iterator>::difference_type*>(0);
}

// 决定某个迭代器的value_type
template<typename _Iterator>
inline typename iterator_traits<_Iterator>::value_type*
value_type(const _Iterator&) {
	return static_cast<typename iterator_traits<_Iterator>::value_type*>(0);
}

// 正向迭代器
template<typename _Ty, typename _D = ptrdiff_t>
struct _Forit : public iterator<forward_iterator_tag, _Ty, _D> {};

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

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

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

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

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

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

template<typename _II>
inline typename iterator_traits<_II>::difference_type
__distance(_II _F, _II _L, input_iterator_tag)
{
	typename iterator_traits<_II>::difference_type n = 0;
	while (_F != _L)
	{
		_F++;
		n++;
	}
	return n;
}

template<typename _RAI>
inline typename iterator_traits<_RAI>::difference_type
__distance(_RAI _F, _RAI _L, random_access_iterator_tag)
{
	return _L - _F;
}

template<typename _II>
inline typename iterator_traits<_II>::difference_type
distance(_II _F, _II _L)
{
	return __distance(_F, _L, iterator_category(_F));
}

}

#endif

类型萃取

my_type_traits.h

#ifndef MY_TYPE_TRAITS_H
#define MY_TYPE_TRAITS_H

namespace Srh
{
	struct __true_type {};
	struct __false_type {};

	template<typename 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; 
	};

	// 特化版本
	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;  
	};

	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;   
	};

	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;  
	};

	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;   
	};

	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;   
	};
	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;   
	};
	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;   
	};
	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;   
	};
	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;   
	};

	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;   
	};
	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;   
	};
	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;   
	};

	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;   
	};

	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;   
	};
	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;   
	};
}

#endif

构造和析构

my_construct.h

#ifndef MY_CONSTRUCT_H
#define MY_CONSTRUCT_H

#include"my_iterator.h"
#include"my_type_traits.h"

namespace Srh
{

// 包装定位new placement new
template<typename T1, typename T2>
inline void construct(T1* p, const T2& val)
{
	new (p) T1(val);
}

// 无参的
template<typename T>
inline void construct(T* p)
{
	new (p) T();
}

// 析构对象
template<typename T>
inline void destroy(T* p)
{
	p->~T();
}

/*
// 析构范围内的对象
template<typename _FI>
inline void destroy(_FI _F, _FI _L)
{
	for (; _F != _L; ++F)
	{
		destroy(&*_F);
		//(*_F)表示迭代器所指之物， 
		// (&*_F)表示迭代器所指之物的地址  
	}
}
*/

// 如果析构函数无关紧要，那么就不需要上面这样麻烦
// 那么利用上面已知的true/false来判断
template<typename _FI>
inline void __destroy_aux(_FI _F, _FI _L, Srh::__true_type)
{}

template<typename _FI>
inline void __destroy_aux(_FI _F, _FI _L, Srh::__false_type)
{
	for (; _F != _L; ++_F)
	{
		destroy(&*_F);
	}
}

template<typename _FI, typename T>
inline void __destroy(_FI _F, _FI _L, T*)
{
	//cout << typeid(T).name() << endl;
	//Srh::__type_traits<T>();
	// 得知T所指之物的值类型
	// 再根据类型萃取 获取 值类型的析构函数是 true还是false
	typedef typename Srh::__type_traits<T>::has_trivial_destructor dest;
	__destroy_aux(_F, _L, dest());
}

template<typename _FI>
inline void destroy(_FI _F, _FI _L)
{
	// 调用下面的__destroy,获取_F迭代器所指之物的类型
	__destroy(_F, _L, Srh::value_type(_F));
}

}
#endif

空间配置器

my_alloc.h

#ifndef MY_ALLOC_H
#define MY_ALLOC_H

#include<iostream>
using namespace std;

namespace Srh
{

#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:
	// 处理内存不足问题
	static void* oom_malloc(size_t n)
	{
		void* result = nullptr;
		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;
			}
		}
	}

	static void* oom_realloc(void* p, size_t new_sz)
	{
		void* result = nullptr;
		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 void(*__malloc_alloc_oom_handler)();
	static PFUN __malloc_alloc_oom_handler;

public:
	static void* allocate(size_t n)   
	{
		void* result = malloc(n);	// malloc
		if (nullptr == result)
		{
			// 无法满足需求，采用oom_malloc
			result = oom_malloc(n);
		}
		return result;
	}
	static void deallocate(void* p, size_t n)   
	{
		free(p);	// free
	}

	static void* reallocate(void* p, size_t old_sz, size_t new_sz)	 
	{
		void* result = realloc(p, new_sz);	// realloc
		if (nullptr == result)
		{
			// 无法满足需求，采用oom_realloc
			result = oom_realloc(p, new_sz);
		}
		return result;
	}

	//static void (*set_malloc_handler(void (*f))();
	static PFUN set_malloc_handler(PFUN p)
	{
		PFUN old = __malloc_alloc_oom_handler;
		__malloc_alloc_oom_handler = p;
		return old;
	}

};

/*
template<int inst>
void(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = nullptr;
*/
template<int inst>
typename __malloc_alloc_template<inst>::PFUN
__malloc_alloc_template<inst>::__malloc_alloc_oom_handler = nullptr;

// 将参数inst置为0
using malloc_alloc = __malloc_alloc_template<0>;


// 第二级配置器
enum { __ALIGN = 8 };	// 小型区块的上调边界
enum { __MAX_BYTES = 128 };	// 小型区块的上限
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };	// free_lists个数

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 size_t ROUND_UP(size_t bytes) // 1~8 / 9~16...
	{
		return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
	}
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (bytes + __ALIGN - 1) / __ALIGN - 1;
	}

	static char* start_free;	// 内存池起始位置
	static char* end_free;		// 内存池结束位置
	static size_t heap_size; // total

	// 配置一大块空间，可以容纳nobjs个size大小的区块
	// 如果配置nobjs个区块有所不便，nobjs会做出相应改变
	static char* chunk_alloc(size_t size, int& nobjs)
	{
		char* result = nullptr;
		// 需要空间的总大小
		size_t total_bytes = size * nobjs;
		// 内存池剩余空间
		size_t bytes_left = end_free - start_free;

		// 如果内存池剩余空间满足需要空间
		if (bytes_left >= total_bytes)
		{
			result = start_free;
			start_free = start_free + total_bytes;
			return result;
		}
		else if (bytes_left >= size)
		{
			// 如果剩余空间只够1个以上的块（但小于总需求）
			nobjs = bytes_left / size;
			result = start_free;
			start_free = start_free + total_bytes;
			return result;
		}
		else
		{
			// 如果连一块空间都不够
			size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
			
			// 将剩下的一点点空间再利用
			if (bytes_left > 0)
			{
				// 将剩余空间配置给合适的free_list
				obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);
				((obj*)start_free)->free_list_link = *my_free_list;
				*my_free_list = (obj*)start_free;
			}

			// 配置heap空间，补充内存池
			start_free = (char*)malloc(bytes_to_get);
			if (nullptr == start_free)
			{
				obj* volatile* my_free_list = nullptr;
				obj* p = nullptr;
				for (int i = size; i <= __MAX_BYTES; i += __ALIGN)
				{
					my_free_list = free_list + FREELIST_INDEX(i);
					p = *my_free_list;
					if (nullptr != p)
					{
						*my_free_list = p->free_list_link;
						start_free = (char*)p;
						end_free = start_free + i;
						return chunk_alloc(size, nobjs);
					}
				}
				end_free = 0;
				start_free = (char*)malloc_alloc::allocate(bytes_to_get);
			}

			// 修正内存池的结束位置和总大小
			end_free = start_free + bytes_to_get;
			heap_size += bytes_to_get;
			// 递归调用自己，修正nobjs
			return chunk_alloc(size, nobjs);
		}
	}

	// 返回一个大小为size的对象，
	// 并可能加入大小为size的其他区块到free_list中
	static void* refill(size_t size)
	{
		int nobjs = 20;
		char* chunk = chunk_alloc(size, nobjs);
		if (1 == nobjs) return chunk;

		obj* volatile* my_free_list = nullptr;
		obj* result = (obj*)chunk;
		obj* current_obj = nullptr;
		obj* next_obj = nullptr;
		int i = 0;
		
		my_free_list = free_list + FREELIST_INDEX(size);
		*my_free_list = next_obj = (obj*)(chunk + size);
		for (i = 1; ; ++i)
		{
			current_obj = next_obj;
			next_obj = (obj*)((char*)next_obj + size);
			if (i == nobjs - 1)
			{
				current_obj->free_list_link = nullptr;
				break;
			}
			current_obj->free_list_link = next_obj;
		}
		return result;
	}

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)
		{
			void* r = refill(ROUND_UP(size));
			return r;
		}
		*my_free_list = result->free_list_link;
		return result;
	}

	static void deallocate(void* p, size_t n)
	{
		if (n > (size_t)__MAX_BYTES)
		{
			return malloc_alloc::deallocate(p, n);
		}

		obj* q = (obj*)p;
		obj* volatile* my_free_list = nullptr;
		// 寻找相应的free_list
		my_free_list = free_list + FREELIST_INDEX(n);
		// 头插法，回收区块
		q->free_list_link = *my_free_list;
		*my_free_list = q;
	}

	static void* reallocate(void* p, size_t old_sz, size_t new_sz)
	{
		if (old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES)
		{
			return malloc_alloc::reallocate(p, old_sz, new_sz);
		}
		if (ROUND_UP(old_sz) == ROUND_UP(new_sz))
		{
			return p;
		}

		size_t sz = old_sz < new_sz ? old_sz : new_sz;
		void* s = allocate(new_sz);
		memmove(s, p, sz);
		deallocate(p, old_sz);
		return s;
	}


};

// 对各个成员初始化
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;

//
//
// SGI STL
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0, 0> alloc;
#endif

template<typename T, typename Alloc>
class simple_alloc
{
public:
	// 申请
	static T* allocate(size_t n) // n个T类型的
	{
		return Alloc::allocate(sizeof(T) * n);
	}
	static T* allocate()
	{
		return Alloc::allocate(sizeof(T));
	}

	// 删除函数
	void deallocate(T* p, size_t n)
	{
		if (nullptr == p) return;
		Alloc::deallocate(p, size(T) * n);
	}
	void deallocate(T* p)
	{
		if (nullptr == p) return;
		Alloc::deallocate(p, sizeof(T));
	}
};

}
#endif

猜你喜欢

[js高手之路]html5 canvas动画教程 - 自己动手做一个类似windows的画图软件
Mongodb的安装
Vue - 超详细 “横向滚动“ 弹幕效果功能组件源码，类似视频与直播间的发言弹幕（支持自定义弹幕样式 / 开启暂停弹幕播放 / 清空弹幕 / 修改弹幕移动速度 / 发送插入自己的弹幕并高亮显示等）
【BZOJ2001】[HNOI2010]城市建设（CDQ分治，线段树分治）
【Harmony OS】【ARK UI】Date 基本操作
nginx 之高级模块
《深入理解大数据：大数据处理与编程实践》一一2.1　Hadoop系统安装方法简介
FPGA设计流程以及工具
本地Navicat远程连接Centos7服务器出现的错误汇总
Cesium-空间分析之通视分析(附源码下载)
shell 评估文件/目录状态
本地删除的文件怎么再从svn上下载
SwiftUI 内功之for循环从入门到精通（Swift loop教程含源码）
Linux最常用的基础命令
Windows 安装 Zookeeper （图文解说详细版）
字典排序permutation
【CF662C】Binary Table 按位处理
基于simulink的电气弹簧ES稳压控制模型仿真
百度做社交了？还捡起了几年前的“校内网”模式？
SpringSecurity整合JWT
《扩展 jQuery》——2.3　总结

相关主题

Redis源码分析
Android源码编译
源码：HashMap
linux 查看源码
Thread源码分析
Linux内核源码目录
mysql源码编译
jquery源码分析
jQuery源码解析
spring 源码
LinkedHashMap源码
php源码解读
Spring源码解读
Eureka源码

zl程序教程

当前栏目

STL：源码剖析(部分）—— 目录

文章目录

迭代器

迭代器剖析

my_iterator.h

类型萃取

类型萃取剖析

my_type_traits.h

构造和析构

源码剖析

my_construct.h

空间配置器

第一级配置器

第二级配置器

my_alloc.h

相关文章