文档章节

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

闵启阳
 闵启阳
发布于 2013/12/29 20:35
字数 1727
阅读 369
收藏 1
点赞 0
评论 0
#ifndef KNIFE_ALGOBASE_H
#define KNIFE_ALGOBASE_H

// 这个头文件看似是由一个个基础函数构成的算法库
// 但其实这些算法大部分都是基于iterator这个概念的,即
// 基于iterator的相关全局基础方法,使iterator在被使用
// 的时候更加得心应手;这些方法包括:
// iter_swap();
// distance(); advance();这几个在3.0版本后被改至iterator.h中了
// swap(), max(), min(); 这几个不是基于iterator的
// copy(); mismatch();

#include "config.h"
#include "iterator.h"
#include "knifeio.h"
#include "type_traits.h"
#include <string.h> // use memmove() in it

_STL_NAMESPACE_BEGIN

// The name 1 2 implicit a kind of squence, so we use name a b
// And indeed we do need a T pointer to init type T implicitly
// Cause we can NOT use function or other expression in init type T explicit
template <typename InputIterator_a, typename InputIterator_b, typename T>
inline void _iter_swap(InputIterator_a a, InputIterator_b b, T*)
{
	T tmp = *a;
	*a = *b;
	*b = tmp;
}

// When we need the thing that iterator point to we should use *a
// and when we need the pointer point to the thing
// we should use &(*a);
template <typename InputIterator_a, typename InputIterator_b>
inline void iter_swap(InputIterator_a a, InputIterator_b b)
{
	_iter_swap(a, b, &(*a));
}

template <typename T>
inline void swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

template <typename T>
inline const T& min(const T& a, const T& b)
{
	return (a < b) ? a : b;
}

template <typename T>
inline const T& max(const T& a, const T& b)
{
	return (b < a) ? a : b;
}

// SGI_STL_203的实现逻辑略微有点奇怪,他将comp(a, b)
// 与 b < a等同了,而且并没有使用这个函数的地方,所以
// 我在这里是做了修改的,comp(a, b)应该在a > b时返回true
// 在a < b时返回false
template <typename T, typename Compare>
inline const T& min(const T& a, const T& b, Compare comp)
{
	return comp(a, b) ? b : a;
}

template <typename T, typename Compare>
inline const T& max(const T& a, const T& b, Compare comp)
{
	return comp(a, b) ? a : b;
}

// 这是描述两个iterator之间的距离的函数
template <typename RandomAccessIterator, typename Distance>
inline void _distance(RandomAccessIterator a, RandomAccessIterator b, Distance& dis, 
						random_access_iterator_tag)
{
	dis += b - a;
	// 注意,这里是在原值基础上加上距离,并不是赋值
}

template <typename InputIterator, typename Distance>
inline void _distance(InputIterator a, InputIterator b, Distance& dis, 
						input_iterator_tag)
{
	while (a != b) { ++a; ++dis; }
	// 在前++和后++中,前++是优先实现的,所以优先使用前++
}

template <typename InputIterator, typename Distance>
inline void distance(InputIterator a, InputIterator b, Distance& distance)
{
	_distance(a, b, distance, iterator_category(a));	
}

// 由于iterator_category()返回的是临时对象
// 所以不能使用诸如random_access_iterator_tag&
// 这样的参数来区分不同的iterator,必须使用random_access_iterator_tag
template <typename RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator a, RandomAccessIterator b, random_access_iterator_tag)
{
	return b - a;
}

template <typename InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator a, InputIterator b, input_iterator_tag)
{
	typename iterator_traits<InputIterator>::difference_type dis(0);
	while (b != a)
	{
		++a;
		++dis;
	}
	return dis;
}

template <typename InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator a, InputIterator b)
{
	return _distance(a, b, iterator_category(a));
}

// Distance类型被要求支持两个--操作,能转换为bool型
template <typename InputIterator, typename Distance>
inline void _advance(InputIterator& i, Distance n, input_iterator_tag)
{
	// 在SGI_STL 2.03是这样的:while (n--) ++i;
	// 那么当n为负的时候这里是处理不了的,但用户并没有被通知
	// 略有不恰当;而且不能要求一个distance一定可以转换为bool
	// 不过我找不到代替的方法。。。。。。。
	if (n) { while (n--) ++i; }
	else { printf("You can not make a iterator -- while this iterator only have ++ in advance()"); }
}

// Distance类型被要求支持两个--操作和两个++操作,能转换为bool型
template <typename BidirectionalIterator, typename Distance>
inline void _advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
{
	if (n)
		while (n--) ++i;
	else
		while (n++) --i;
}

template <typename RandomAccessIterator, typename Distance>
inline void _advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
{
	// 原文是 i+=n;在这里有暗含i要支持+=这样的操作,是不合理的
	i = i + n;
}

// 请记住使用&!!!!
template <typename InputIterator, typename Distance>
inline void advance(InputIterator& i, Distance n)
{
	_advance(i, n, iterator_category(i));
}

template <typename InputIterator, typename OutputIterator>
inline OutputIterator 
_copy(InputIterator first, InputIterator last, OutputIterator res, input_iterator_tag)
{
	// We'd better not use while (first != last) *res++ = *first++;
	// This method will be supposed to be written in the situation
	// we know what will the ++(int)operation do, and while it is much more
	// not effcient than ++() we should use ++() first;
	// so we use ++() here;
	for (; first != last; ++first, ++res)
		*res = *first;
	return res;
}

template <typename RandomAccessIterator, typename OutputIterator, typename Distance>
inline OutputIterator 
_copy_distance(RandomAccessIterator first, RandomAccessIterator last, OutputIterator res, Distance*)
{
 	for (Distance d = last - first; d != 0; --d, ++res, ++first)
		*res = *first;
	return res;
}

template <typename RandomAccessIterator, typename OutputIterator>
inline OutputIterator 
_copy(RandomAccessIterator first, RandomAccessIterator last, OutputIterator res, random_access_iterator_tag)
{
	// 在这里我们已经知道了iterator的类型,所以不必传递random_access_iterator_tag
	_copy_distance(first, last, res, distance_type(first));
}

template <typename InputIterator, typename OutputIterator>
struct copy_dispatcher {
	OutputIterator operator()(InputIterator first, InputIterator last, OutputIterator result)
	{
		return _copy(first, last, result, iterator_category(first));
	}
};

template <typename T>
inline T*
_copy_ptr(const T* first, const T* last, T* result, __true_type)
{
	const ptrdiff_t diff = last - first;
	memmove(result, first, sizeof(T) * diff);
	return result + diff;
}

template <typename T>
inline T*
_copy_ptr(const T* first, const T* last, T* result, __false_type)
{
	_copy_distance(first, last, result, (ptrdiff_t*) (0));
}

template <typename T>
struct copy_dispatcher<T*, T*> {
	T* operator()(T* first, T* last, T* res)
	{
		return _copy_ptr(first, last, res, 
				typename __type_traits<T>::has_trivial_assignment_operator());
	}
};

template <typename T>
struct copy_dispatcher<const T*, T*> {
	T* operator()(const T* first, const T* last, T* res)
	{
		return _copy_ptr(first, last, res, 
				typename __type_traits<T>::has_trivial_assignment_operator());
	}
};

template <typename InputIterator, typename OutputIterator>
inline OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator res)
{
	return copy_dispatcher<InputIterator, OutputIterator>()(first, last, res);
}

inline char*
copy(const char* first, const char* last, char* result)
{
	const ptrdiff_t diff = last - first;
	memmove(result, first, diff);// Cause sizeof(char) is 1
	return result + diff;
}

inline wchar_t*
copy(const wchar_t* first, const wchar_t* last, wchar_t* result)
{
	const ptrdiff_t diff = last - first;
	memmove(result, first, sizeof(wchar_t) * diff);
	return result + diff;
}

// Easy , we copy the element to destination from the backward direction
template <typename BidirectionalIterator_a, typename BidirectionalIterator_b>
inline BidirectionalIterator_b
_copy_backward(BidirectionalIterator_a first, BidirectionalIterator_a last,
 				BidirectionalIterator_b res, input_iterator_tag)
{
	// we will copy the element from the form one 
	// of the res
	while (first != last) *--res = *--last; 
	return res;
}

template <typename BidirectionalIterator_a, typename BidirectionalIterator_b, typename Distance>
inline BidirectionalIterator_b
_copy_backward_distance(BidirectionalIterator_a first, BidirectionalIterator_a last,
							BidirectionalIterator_b res, Distance*)
{
	// Maybe !=() operation will come to much resources
	// so we'd better use a light type: distance
	Distance dis = last - first;
	while (dis != 0) { --dis; *--res = *--last; }
	return res;
}

template <typename BidirectionalIterator_a, typename BidirectionalIterator_b>
inline BidirectionalIterator_b
_copy_backward(BidirectionalIterator_a first, BidirectionalIterator_a last,
				BidirectionalIterator_b res, random_access_iterator_tag)
{
	_copy_backward_distance(first, last, res, distance_type(first));
}

template <typename BidirectionalIterator_a, typename BidirectionalIterator_b>
struct copy_backward_dispatcher {
	BidirectionalIterator_b operator()(BidirectionalIterator_a first, BidirectionalIterator_a last,
										BidirectionalIterator_b res)
	{
		return _copy_backward_backward(first, last, res, iterator_category(first));
	}
};

template <typename T>
inline T*
_copy_backward_ptr(const T* first, const T* last, T* res, __true_type)
{
	const ptrdiff_t diff = last - first;
	memmove(res - diff, first, sizeof(T) * diff);
	return res - diff;
}

template <typename T>
inline T*
_copy_backward_ptr(const T* first, const T* last, T* res, __false_type)
{
	return _copy_backward_distance(first, last, res, (ptrdiff_t*) (0));
}

template <typename T>
struct copy_backward_dispatcher<T*, T*> {
	T* operator()(T* first, T* last, T* res)
	{
		return _copy_backward_ptr(first, last, res, 
							typename __type_traits<T>::has_trivial_assignment_operator());
	}
};

template <typename T>
struct copy_backward_dispatcher<const T*, T*> {
	T* operator()(const T* first, const T* last, T* res)
	{
		return _copy_backward_ptr(first, last, res, 
							typename __type_traits<T>::has_trivial_assignment_operator());
	}
};

template <typename BidirectionalIterator_a, typename BidirectionalIterator_b>
inline BidirectionalIterator_b
copy_backward(BidirectionalIterator_a first, BidirectionalIterator_a last, BidirectionalIterator_b res)
{
	return copy_backward_dispatcher<BidirectionalIterator_a, BidirectionalIterator_b>()(first, last, res);
}


inline char*
copy_backward(const char* first, const char* last, char* result)
{
	const ptrdiff_t diff = last - first;
	memmove(result - diff, first, diff);// Cause sizeof(char) is 1
	return result - diff;
}

inline wchar_t*
copy_backward(const wchar_t* first, const wchar_t* last, wchar_t* result)
{
	const ptrdiff_t diff = last - first;
	memmove(result - diff, first, sizeof(wchar_t) * diff);
	return result - diff;
}

template <typename InputIterator, typename _Size, typename OutputIterator>
inline OutputIterator
_copy_n(InputIterator first, _Size size, OutputIterator res, 
		input_iterator_tag)
{
	while (size != 0) { --size; ++res; ++first; *res = *first;}
	return res;
}

template <typename RandomAccessIterator, typename _Size, typename OutputIterator>
inline OutputIterator
_copy_n(RandomAccessIterator first, _Size size, OutputIterator res, 
		random_access_iterator_tag)
{
	return copy(first, first + size, res);
}

// THis function is work for the situation that we 
// do not know last iterator, we just know the size
template <typename InputIterator, typename _Size, typename OutputIterator>
inline OutputIterator
copy_n(InputIterator first, _Size size, OutputIterator res)
{
	return _copy_n(first, size, res, iterator_category(first));
}

template <typename InputIterator, typename Value>
inline void 
fill(InputIterator first, InputIterator last, const Value& val)
{
	while (first != last) {  *first = val; ++first; }
}

template <typename InputIterator, typename _Size, typename Value>
inline void
fill_n(InputIterator first, _Size n, const Value& val)
{
	while (n != 0) {  *first = val; --n; ++first; }
}


_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程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

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

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

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

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

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

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

oschina ⋅ 04/10 ⋅ 0

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

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

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

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

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

小辰带你看世界 ⋅ 03/23 ⋅ 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程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

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

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 18分钟前 ⋅ 0

Java学习路径及练手项目合集

Java学习路径及练手项目合集

颖伙虫 ⋅ 34分钟前 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

MVC——统一报文格式的异常处理响应

在我们写controller层的时候,常常会有这样的困惑,如果需要返回一个数据是,可能为了统一回去构造一个类似下列的数据格式: { status:true, msg:"保存成功!", data:[]} 而且在写...

alexzhu592 ⋅ 昨天 ⋅ 0

android -------- 打开本地浏览器或指定浏览器加载,打电话,打开第三方app

开发中常常有打开本地浏览器加载url或者指定浏览器加载, 还有打开第三方app, 如 打开高德地图 百度地图等 在Android程序中我们可以通过发送隐式Intent来启动系统默认的浏览器。 如果手机本身...

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部