文档章节

【试着自己写一个STL 】Knife_STL —— algobase.h 2

闵启阳
 闵启阳
发布于 2014/01/02 20:47
字数 1668
阅读 26
收藏 0
点赞 0
评论 0
// We get the last iterator pair if these two is soooo match
template <typename InputIterator_a, typename InputIterator_b>
inline pair<InputIterator_a, InputIterator_b>
mismatch(InputIterator_a first_a, InputIterator_a last_a, 
			InputIterator_b first_b)
{
	while (first_a != last_a && *first_a == *first_b)
	{
		++first_a;
		++first_b;
	}

	return pair<InputIterator_a, InputIterator_b>(first_a, first_b);
}

template <typename InputIterator_a, typename InputIterator_b,
			 typename BinaryPredicate> // BinaryPredicate could be a functor
inline pair<InputIterator_a, InputIterator_b>
mismatch(InputIterator_a first_a, InputIterator_a last_a, 
			InputIterator_b first_b, BinaryPredicate binary_predicate)
{
	// The binary predicate should handle the content the iterator point to
	// so we should pass content the iterator point to rather than the iterator
	// to the binary predicate to handle
	while (first_a != last_a && binary_predicate(*first_a, *first_b))
	{
		++first_a;
		++first_b;
	}

	return pair<InputIterator_a, InputIterator_b>(first_a, first_b);
}

// 有时候我们并不需要得到mismatch的iterator组成的pair
// 这给我们一种两层封装的感觉,我们可能只要mismatch的value组成的pair
// 所以我直接封装了这样一个函数,满足需求
// 这个函数也有他的BinaryPredicate版本
template <typename InputIterator_a, typename InputIterator_b>
inline pair<typename iterator_traits<InputIterator_a>::value_type,
			typename iterator_traits<InputIterator_b>::value_type>
mismatch_content(InputIterator_a first_a, InputIterator_a last_a, 
					InputIterator_b first_b)
{
	while (first_a != last_a && *first_a == *first_b)
	{
		++first_a;
		++first_b;
	}

	return pair<typename iterator_traits<InputIterator_a>::value_type,
				typename iterator_traits<InputIterator_b>::value_type>
		   (*first_a, *first_b);
}

template <typename InputIterator_a, typename InputIterator_b, 
			typename BinaryPredicate>
inline pair<typename iterator_traits<InputIterator_a>::value_type,
			typename iterator_traits<InputIterator_b>::value_type>
mismatch_content(InputIterator_a first_a, InputIterator_a last_a, 
					InputIterator_b first_b, BinaryPredicate binary_predicate)
{
	while (first_a != last_a && binary_predicate(*first_a, *first_b))
	{
		++first_a;
		++first_b;
	}

	return pair<typename iterator_traits<InputIterator_a>::value_type,
				typename iterator_traits<InputIterator_b>::value_type>
		   (*first_a, *first_b);
}

// 遍历式的实现,当我们找到不符合的部分时,就直接退出,减少CPU占用
template <typename InputIterator_a, typename InputIterator_b>
inline bool
equal(InputIterator_a first_a, InputIterator_a last_a, 
			InputIterator_b first_b)
{
	while (first_a != last_a)
	{
		if (*first_a == *first_b)
		{
			++first_a;
			++first_b;
		}
		else
		{
			return false;
		}
	}

	return true;
}

template <typename InputIterator_a, typename InputIterator_b, 
			typename BinaryPredicate>
inline bool
equal(InputIterator_a first_a, InputIterator_a last_a, 
			InputIterator_b first_b, BinaryPredicate binary_predicate)
{
	while (first_a != last_a)
	{
		if (binary_predicate(*first_a, *first_b))
		{
			++first_a;
			++first_b;
		}
		else
		{
			return false;
		}
	}
	
	return true;
}

// I added this function for the reason the same as we added the function fill_n
template <typename InputIterator_a, typename _Size, typename InputIterator_b>
inline bool
equal_n(InputIterator_a first_a, _Size size, InputIterator_b first_b)
{
	while (size != _Size(0))
	{
		if (*first_a == *first_b)
		{
			--size;
			++first_a;
			++first_b;
		}
		else
		{
			return false;
		}
	}
	
	return true;
}

template <typename InputIterator_a, typename _Size, 
			typename InputIterator_b, typename BinaryPredicate>
inline bool
equal(InputIterator_a first_a, _Size size, 
			InputIterator_b first_b, BinaryPredicate binary_predicate)
{
	while (size != _Size(0))
	{
		if (binary_predicate(*first_a, *first_b))
		{
			--size;
			++first_a;
			++first_b;
		}
		else
		{
			return false;
		}
	}
	
	return true;
}

// 来自有道字典:lexicographic -- 字典式的, 以字典序比较两个list
// 多用于比较两个字符串,所以有专门对于字符串的优化
// 在a < b时返回true
template <typename InputIterator_a, typename InputIterator_b>
inline bool
lexicographical_compare(InputIterator_a first_a, InputIterator_a last_a, 
						InputIterator_b first_b, InputIterator_b last_b)
{
	for (; first_a != last_a || first_b != last_b; ++first_a, ++first_b)
	{
		if (*first_b < *first_a) return true;
		if (*first_a < *first_b) return false;
	}

	// Note:: must be && here!!
	return first_a == last_a && first_b != last_b;
}

// STL有一个对于字符串的优化版本,这个版本借用C的函数实现
// 看来C的函数确实在char*处理方面效率很高,多多学习,以后可以用上
// 但是这里CHAR_MAX == SCHAR_MAX的部分实在不懂,为何要这样?
// 所以我这里只使用了unsigned char*的实现代替了char*的实现
// 好像还挺好用
inline bool
lexicographical_compare(const char* first_a, 
						const char* last_a, 
						const char* first_b, 
						const char* last_b)
{
	const size_t len_a = last_a - first_a;
	const size_t len_b = last_b - first_b;
	const int result = memcmp(first_a, first_b, min(len_a, len_b));
	return result != 0 ? result < 0 : len_a < len_b;
}

// inline bool
// lexicographical_compare(const char* first_a, 
// 						const char* last_a, 
// 						const char* first_b, 
// 						const char* last_b)
// {
// 	const size_t len_a = last_a - first_a;
// 	const size_t len_b = last_b - first_b;
// 	const int result = memcmp(first_a, first_b, min(len_a, len_b));
// 	knife::printf("Result: ", result);
// 	return result != 0 ? result < 0 : len_a < len_b;
// }

// inline bool 
// lexicographical_compare(const char* first1,
// 						const char* last1,
//                         const char* first2, 
//                         const char* last2)
// {
// #if CHAR_MAX == SCHAR_MAX
//   	return lexicographical_compare(	(const signed char*) first1,
//                                  	(const signed char*) last1,
//                                  	(const signed char*) first2,
//                                  	(const signed char*) last2);
// #else
//   	return lexicographical_compare(	(const unsigned char*) first1,
//                                  	(const unsigned char*) last1,
//                                  	(const unsigned char*) first2,
//                                  	(const unsigned char*) last2);
// #endif
// }

template <typename InputIterator_a, typename InputIterator_b, typename Compare>
inline bool
lexicographical_compare(InputIterator_a first_a, InputIterator_a last_a, 
						InputIterator_b first_b, InputIterator_b last_b, 
						Compare comp)
{
	for (; first_a != last_a || first_b != last_b; ++first_a, ++first_b)
	{
		if (comp(*first_a, *first_b)) return true;
		if (comp(*first_a, *first_b)) return false;
	}

	// Note:: must be && here!!
	return first_a == last_a && first_b != last_b;
}

// 我更改了一下实现的方法,个人认为比原版的好,这里贴出原版的
// 各位可以比较一下
template <typename InputIterator_a, typename InputIterator_b>
inline int
lexicographical_compare_3way(InputIterator_a first_a, InputIterator_a last_a, 
							 InputIterator_b first_b, InputIterator_b last_b)
{
	static int more = 1;
	static int less = -1;
	static int equal = 0;

	for (; first_a != last_a || first_b != last_b; ++first_a, ++first_b)
	{
		if (*first_a < *first_b) return less;
		if (*first_b < *first_a) return more;
	}

	return (first_a == last_a) ? ((first_b == last_b) ? equal : less) : more;
}

// 以下都属于原版
// template <class InputIterator1, class InputIterator2>
// int lexicographical_compare_3way(InputIterator1 first1, InputIterator1 last1,
//                                  InputIterator2 first2, InputIterator2 last2)
// {
//     while (first1 != last1 && first2 != last2) {
//         	if (*first1 < *first2) return -1;
//         	if (*first2 < *first1) return 1;
// 			++first1; ++first2;
//     }
//
//     if (first2 == last2) {
// 			return !(first1 == last1);
//     } else {
//         	return -1;
//     }
// }

template <typename InputIterator_a, typename InputIterator_b, typename Compare>
inline int
lexicographical_compare_3way(InputIterator_a first_a, InputIterator_a last_a, 
							 InputIterator_b first_b, InputIterator_b last_b, 
							 Compare comp)
{
	static int more = 1;
	static int less = -1;
	static int equal = 0;

	for (; first_a != last_a || first_b != last_b; ++first_a, ++first_b)
	{
		if (comp(*first_a, *first_b)) return less;
		if (comp(*first_b, *first_a)) return more;
	}

	return (first_a == last_a) ? ((first_b == last_b) ? equal : less) : more;
}

// 这里有一个例外:如"apple"和"appleapple"比较返回的就是-5
// 这里有点没搞懂他设计的想法,难道不是a比b小的时候返回-1吗?
// 他的想法貌似是对两个字符串比较时,我们还需要得出一些额外的值
// 用以告诉user更多信息,但为什么不在template的部分也这么做呢?
// 偏偏要在特化部分这么做
inline int 
lexicographical_compare_3way(const char* first_a, const char* last_a,
							 const char* first_b, const char* last_b)
{
	const size_t len_a = last_a - first_a;
	const size_t len_b = last_b - first_b;
	const int result = memcmp(first_a, first_b, min(len_a, len_b));
	knife::printf(len_a, len_b);
	return result == 0 ? len_a - len_b : result;
}
// 后面的问题很lexicographical_compare一样,就不举例了

// SGI的作者真是直接额,不知道的就直接叫pointer
// 对于我这种命名强迫症患者真是解脱
template <typename T>
inline void destroy(T* pointer)
{
	pointer->~T();
}

// placement new for initialize A_Type in 
// the place where the A_Type* pointer point
// 这个placement new 非常的暴力,如果你传个临时变量
// 的地址过来,他也会执行的,这个函数会在你只重载了
// void* operator new(size_t)的时候报错,因为没有
// void* operator new(size_t, B_Type*)的版本
// 看来世上的事不能总是保证正确,虽然我们已经尽力了
template <typename A_Type, typename B_Type>
inline void construct(A_Type* buffer, const B_Type& value)
{
	new (buffer) A_Type(value);
}

template <typename ForwardIterator>
inline void __destroy_aux_aux(ForwardIterator first, ForwardIterator last, forward_iterator_tag)
{
	for (; first != last; ++first) destroy(&*first);
}

template <typename RandomAccessIterator, typename Distance>
inline void __destroy_aux_aux_d(RandomAccessIterator first, RandomAccessIterator last, Distance*)
{
	for (Distance d = last - first; d != Distance(0); --d, ++first) destroy(&*first);
}

// 相对于原文我又做了一次封装,相信大家不介意的吧
template <typename RandomAccessIterator>
inline void __destroy_aux_aux(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
	__destroy_aux_aux_d(first, last, distance_type(first));
}

template <typename ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
	__destroy_aux_aux(first, last, iterator_category(first));
}

// trivial destructor即无用的destructor,所以可以不调用
template <typename ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __true_type) {}

// 为啥要叫_destroy_aux?!!!!,aux是辅助的意思
// 为了得到iterator所指的类型,我们不得不做一次这样的包装
template <typename ForwardIterator, typename Content>
inline void _destroy(ForwardIterator first, ForwardIterator last, const Content&)
{
	_destroy_aux(first, last, __type_traits<Content>::has_trivial_destructor());
}

template <typename ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last)
{
	_destroy(first, last, value_type(first));
}

// char类型当然有trivial_destructor,但大家貌似经常对char*做这样的操作
// 为了优化,就直接写了这样一个特化版本,这是C++ GP里面非常重要常用的方法
// 学习了!
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

_STL_NAMESPACE_END

#endif


© 著作权归作者所有

共有 人打赏支持
闵启阳
粉丝 2
博文 11
码字总数 5345
作品 0
南京
程序员
C语言/C++永远都不会过时的编程语言

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/30 ⋅ 0

C语言/C++编程学习强势之处的体现

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/12 ⋅ 0

C语言编程新手入门基础知识学习:程序注释

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/15 ⋅ 0

C语言/C++编程学习未来之路

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/30 ⋅ 0

什么是 C 和 C ++ 标准库?

简要介绍编写C/C ++应用程序的领域,标准库的作用以及它是如何在各种操作系统中实现的。 我已经接触C++一段时间了,一开始就让我感到疑惑的是其内部结构:我所使用的内核函数和类从何而来? ...

oschina ⋅ 04/10 ⋅ 0

C语言/C++程序员编程学习代码训练—精讲

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/23 ⋅ 0

C语言编程学习:把相同或近乎相同的代码形成函数和宏

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/16 ⋅ 0

大神有话说之c++,还在迷茫的朋友可以来看一下

C++ 是一种中级语言,它是由 Bjarne Stroustrup 于 1979 年在贝尔实验室开始设计开发的。C++ 进一步扩充和完善了 C 语言,是一种面向对象的程序设计语言。C++ 可运行于多种平台上,如 Window...

悟空_b201 ⋅ 05/30 ⋅ 0

C语言/C++程序员编程学习自信心曲线图

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/10 ⋅ 0

C语言/C++程序员编程学习:版权和版本

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从零开始搭建Risc-v Rocket环境---(1)

为了搭建Rocke环境,我买了一个2T的移动硬盘,安装的ubuntu-16.04 LTS版。没有java8,gcc是5.4.0 joe@joe-Inspiron-7460:~$ java -version程序 'java' 已包含在下列软件包中: * default-...

whoisliang ⋅ 30分钟前 ⋅ 0

大数据学习路线(自己制定的,从零开始学习大数据)

大数据已经火了很久了,一直想了解它学习它结果没时间,过年后终于有时间了,了解了一些资料,结合我自己的情况,初步整理了一个学习路线,有问题的希望大神指点。 学习路线 Linux(shell,高并...

董黎明 ⋅ 36分钟前 ⋅ 0

systemd编写服务

一、开机启动 对于那些支持 Systemd 的软件,安装的时候,会自动在/usr/lib/systemd/system目录添加一个配置文件。 如果你想让该软件开机启动,就执行下面的命令(以httpd.service为例)。 ...

勇敢的飞石 ⋅ 38分钟前 ⋅ 0

mysql 基本sql

CREATE TABLE `BBB_build_info` ( `community_id` varchar(50) NOT NULL COMMENT '小区ID', `layer` int(11) NOT NULL COMMENT '地址层数', `id` int(11) NOT NULL COMMENT '地址id', `full_......

zaolonglei ⋅ 46分钟前 ⋅ 0

安装chrome的vue插件

参看文档:https://www.cnblogs.com/yulingjia/p/7904138.html

xiaoge2016 ⋅ 49分钟前 ⋅ 0

用SQL命令查看Mysql数据库大小

要想知道每个数据库的大小的话,步骤如下: 1、进入information_schema 数据库(存放了其他的数据库的信息) use information_schema; 2、查询所有数据的大小: select concat(round(sum(da...

源哥L ⋅ 今天 ⋅ 0

两个小实验简单介绍@Scope("prototype")

实验一 首先有如下代码(其中@RestController的作用相当于@Controller+@Responsebody,可忽略) @RestController//@Scope("prototype")public class TestController { @RequestMap...

kalnkaya ⋅ 今天 ⋅ 0

php-fpm的pool&php-fpm慢执行日志&open_basedir&php-fpm进程管理

12.21 php-fpm的pool pool是PHP-fpm的资源池,如果多个站点共用一个pool,则可能造成资源池中的资源耗尽,最终访问网站时出现502。 为了解决上述问题,我们可以配置多个pool,不同的站点使用...

影夜Linux ⋅ 今天 ⋅ 0

微服务 WildFly Swarm 管理

Expose Application Metrics and Information 要公开关于我们的微服务的有用信息,我们需要做的就是将监视器模块添加到我们的pom.xml中: 这将使在管理和监视功能得到实现。从监控角度来看,...

woshixin ⋅ 今天 ⋅ 0

java连接 mongo伪集群部署遇到的坑

部署mongo伪集群 #创建mongo数据存放文件地址mkdir -p /usr/local/config1/datamkdir -p /usr/local/config2/data mkdir -p /usr/local/config3/data mkdir -p /usr/local/config1/l......

努力爬坑人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部