有序列表_风云来的博客-程序员宝宝

技术标签: c++  

 1、列表基类型

 列表基类负责内存管理,处理列表成员访问和修改。

参考代码: http://blog.csdn.net/chenjiayi_yun/article/details/17712039


2、支持排序的列表类型

特点:

1)排序的算法采用快速排序法

2)查找使用折半查找法。



模板的参数类型T必须是一个重载了==和<运算的类型。
模板的参数K表示进行查找时的键类型。
template <typename T, typename K>
class CCustomSortList
	: public lib::container::CBList<T>//自定义排序列表继承于列表基类(由列表基类管理列表成员内存)
{
public:
	typedef lib::container::CBList<T> Inherited;

private:
	bool m_boSorted;	//是否启用排序,默认值为true
public:
	CCustomSortList()
		:Inherited()  //显式调用基类的构造函数
	{
		m_boSorted = true; //默认是需要排序的
	}
	//判断列表是否启用了排序
	inline bool getSorted() const { return m_boSorted; }
	//设置列表是否启用排序
	inline VOID setSorted(const bool boSorted)
	{
		if ( m_boSorted != boSorted )
		{
			if ( boSorted )//如果设置排序,则对列表的元素都进行排序
				sort();
			m_boSorted = boSorted;
		}
	}
	/***
		通过key搜索列表中与Key相等的数据
		如果列表中找不到与key相等的数据,函数返回-1,否则返回值表示数据在
		列表中的索引。
		如果列表启用排序,则会通过基于key与数据对比的搜索算法快速查找,如
		果未启用排序,则循环逐个对比
	***/
	INT_PTR search(const K& key) const
	{
		if ( m_boSorted )
		{
			return getIndexByKey(key);
		}
		else//没有对列表元素排序的,就循环比较(从后往前)
		{
			INT_PTR i;
			T *DataList = *this;


			for ( i=Inherited::count()-1; i>-1; --i )
			{
				if (DataList[i].compareKey(key) == 0)
					return i;
			}


			return -1;
		}
	}
	/***
		通过key搜索列表中与Key相等或大于key的最小项
		如在已排序列表{ 1, 2, 7, 9 }中查找大于等于6的最小项,则查找到的项为7。
		如果列表中找不到则函数返回-1,否则返回值表示数据在列表中的索引。
		如果列表启用排序,则会通过基于key与数据对比的搜索算法快速查找。
		★★注意★★
		如果未启用排序,则循环逐个对比并且仅当数据完全匹配的时候才返回有效索
		引而不会查找最相近的项。
	***/
	INT_PTR searchMiniGreater(const K& key) const
	{
		if ( m_boSorted )
		{
			return getMiniGreaterIndexByKey(key);
		}
		else
		{
			INT_PTR i;
			T *DataList = *this;




			for ( i=Inherited::count()-1; i>-1; --i )
			{
				if (DataList[i].compareKey(key) == 0)
					return i;
			}


			return -1;
		}
	}
	/***
		覆盖插入的函数(排序列表不支持定位插入)
		如果列表启用排序,则不允许插入,在调用次函数时将返回-1,否则将调用父类的插入函数并返回index
	***/
	INT_PTR insert(const INT_PTR index, const T& data)
	{
		if ( m_boSorted )
		{
			Assert(false);//排序列表不允许插入
			return -1;
		}
		return Inherited::insert(index, data);
	}
	/***
		覆盖添加函数
		如果列表启用排序,则会计算新添加的元素应当插入的位置并插入到列表中
		即:会为新添加的元素进行排序
		否则,添加到列表末尾
	***/
	INT_PTR add(const T& data)
	{
		if ( !m_boSorted )
			return Inherited::add(data);


		//如果启用排序,则搜索到应当插入到列表中的位置
		INT_PTR newIndex = 0;
		getIndex(data, &newIndex);
		if ( newIndex > -1 )
			Inherited::insert(newIndex, data);
        return newIndex;
	}
	/***
		覆盖按索引改变数据的函数
		如果列表启用排序,则操作会被忽略,否则将改变指定索引处的数据
	***/
	inline void set(const INT_PTR index, const T &item)
	{
		if ( !m_boSorted )
		{
			Assert( index > -1 && index < m_tCount );
			return Inherited::m_pData[index] = item;
		}
		Assert(false);//排序列表不允许修改项
	}
	/***
		覆盖获取数据在列表中的索引的函数
		如果列表启用排序,则会使用搜索函数基于算法查找,如果未启用排序,则从尾到头循环查找
	***/
	INT_PTR index(const T& data) const
	{
		if ( m_boSorted )
			return getIndex(data, NULL);
		else return Inherited::index(data);
	}
	/***
		覆盖添加新数组到列表的函数
		如果列表启用排序,在将列表的数据添加到自身后重新进行排序
	***/
	inline void addArray(T* data, INT_PTR length)
	{
		Inherited::addArray(data, length);
		if ( m_boSorted )
		{
			sort();
		}
	}
private:
	/***
		通过对比函数快速搜索data在列表中的索引。
		参数pInsertIndex用于输data数据可插入的位置的索引,此参数可以为空。
		如果列表中找不到与data相等的数据,函数返回-1,否则返回值表示数据在
		列表中的索引。
		无论返回值是多少,如果pInsertIndex非空,都会向其中填充data数据可插
		入的位置的索引。
	***/
	INT_PTR	getIndex(const T& data, INT_PTR *pInsertIndex) const
	{
		INT_PTR nLow = 0, nHigh = Inherited::count() - 1, nIndex = 0, nValue, nResult;
		T *ListData = *this;


		nResult = -1;
		while ( nLow <= nHigh )//折半查找(排序情况下)
		{
			nIndex = (nLow + nHigh) >> 1;//nLow + (nHigh - nLow)/2
			nValue = data.compare(ListData[nIndex]);
			if ( nValue != 0 )
			{
				if ( nValue < 0 )
					nHigh = nIndex - 1;
				else nLow = ++nIndex;
			}
			else 
			{
				nResult = nIndex;//找到值相同的,获取索引
				break;
			}
		}


		if ( pInsertIndex )//获取索引(nResult>=0 时,就是所找到的位置;否则是可插入的位置的索引)
			*pInsertIndex = nIndex;
		return nResult;
	}
	/***
		通过针对T的key从列表中搜索大于等于key值最小的数据在列表中的索引。
		如在已排序列表{ 1, 2, 7, 9 }中查找6的最接近项,则查找到的项为7。(只是适用于有序列表)
	***/
	INT_PTR	getMiniGreaterIndexByKey(const K key) const
	{
		INT_PTR nLow = 0, nHigh = Inherited::count() - 1, nGreaterIndex = -1, nIndex = 0, nValue;
		T *ListData = *this;

		while ( nLow <= nHigh )
		{
			nIndex = (nLow + nHigh) >> 1;//nLow + (nHigh - nLow)/2
			nValue = ListData[nIndex].compareKey( key );
			if ( nValue != 0 )
			{
				if ( nValue > 0 )
				{
					nHigh = nIndex - 1;
					nGreaterIndex = nIndex;
				}
				else nLow = ++nIndex;
			}
			else break;
		}
		return nGreaterIndex;
	}
	/***
		通过针对T的key从列表中搜索与key相等的数据
		如果列表中找不到与key相等的数据,函数返回-1,否则返回值表示数据在
		列表中的索引。(只是适用于key有序列表)
	***/
	INT_PTR getIndexByKey(const K key) const
	{
		INT_PTR nLow = 0, nHigh = Inherited::count() - 1, nIndex = 0, nValue, nResult;
		T *ListData = *this;

		nResult = -1;
		while ( nLow <= nHigh )
		{
			nIndex = (nLow + nHigh) >> 1;//nLow + (nHigh - nLow)/2
			nValue = ListData[nIndex].compareKey( key );
			if ( nValue != 0 )
			{
				if ( nValue > 0 )
					nHigh = nIndex - 1;
				else nLow = ++nIndex;
			}
			else 
			{
				nResult = nIndex;
				break;
			}
		}
		return nResult;
	}
	/***
		通过对比函数对列表中的某段数据进行快速排序的排序函数(优化了的快速排序)
	***/
	void quickSort(INT_PTR nLow, INT_PTR nHigh)
	{
		INT_PTR i, j, p;
		T *ListData = *this;
		T temp;

		do
		{
			i = nLow;
			j = nHigh;
			p = (nLow + nHigh) >> 1;//哨兵位置

			do//一趟可多次交换
			{
				while ( ListData[i].compare( ListData[p] ) < 0 ) i++;
				while ( ListData[j].compare( ListData[p] ) > 0 ) j--;
				if ( i <= j )//找到可换的元素,交换两个位置的元素
				{
					memcpy(&temp, &ListData[j], sizeof(T));//使用内存拷贝实现交换
					memcpy(&ListData[j], &ListData[i], sizeof(T));
					memcpy(&ListData[i], &temp, sizeof(T));
					if ( p == i )//换哨兵位置
						p = j;
					else if ( p == j )
						p = i;
					i++;
					j--;
				}
			}
			while ( i <= j );


			if ( nLow < j )
				quickSort( nLow, j );//递归排序前半部分的数列(后半部分仍在本函数继续处理)
			nLow = i;
		}
		while ( i < nHigh );
	}
	/***
		对整个列表中的数据重新排序
	***/
	inline void sort()
	{
		if (Inherited::count() > 1)
		{
			quickSort(0, Inherited::count()-1);//排序整个列表
		}
	}
};

3、排序列表应用

(1)列表中的数据项

封装对象的比较类型,提供对象的数据id的比较函数,为有序列表实现排序提供支持。
struct AvaliableDataIndex
{
	ChunkIndex *pIndex;
public:
	inline operator ChunkIndex* (){ return pIndex; }
	inline INT_PTR compare (const AvaliableDataIndex & another) const // 比较两个项的数据id
	{
		if (pIndex == another.pIndex) return 0;
		if (this->pIndex->chunk.nId < another.pIndex->chunk.nId) return -1; 
		else if (this->pIndex->chunk.nId > another.pIndex->chunk.nId) return 1; 
		//如果出现相同ID索引的情况,那么就是发生错误了!
		else { Assert(pIndex == another.pIndex); return 0; }; 
	}
	inline INT_PTR compareKey(const INT64 nID) const //比较项和具体的值
	{ 
		if (this->pIndex->chunk.nId < nID) return -1; 
		else if (this->pIndex->chunk.nId > nID) return 1; 
		else return 0; 
	}
};


(2)应用实例

typedef CCustomSortList<AvaliableDataIndex, INT64>DataList; //数据列表



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jiayichendddd/article/details/38984023

智能推荐

P1060 开心的金明 (背包问题)_大芝士球的博客-程序员宝宝

目录P1060 开心的金明题目描述思路:未优化     优化优化前和优化后效果比对:P1060 开心的金明 题目描述金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限...

mesh repair_崔世勋的博客-程序员宝宝

摘要处理坏损的3D模型是一个非常费时的问题。这里用于automatic mesh repair的流水线包括三步:生成八叉树,表面重建和光线投射。光线投射用于移除隐藏的物体,流水线还包括一个预处理步骤用于移除相交的三角形,及一个后处理步骤用于错误检测。这里的算法是和一种容量法(volumetric method),它生成的八叉树中包含了输入模型中的数据,在生成输出之前,八叉树中的数据为了去除...

Leetcode 10 正则表达式匹配_爱喝奶茶的Ethan的博客-程序员宝宝

Leetcode 10 正则表达式匹配给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。def isMatch(self, s: str, p: str) -&gt; bool: #考虑边界条件 if not p: return not s #考虑第一个匹配点 first_match = (len(s) &gt; 0) and p[0] in {s[0], '.'} # 先

html中swiper组件的使用_wqww_1的博客-程序员宝宝_html swiper

静态的&lt;!DOCTYPE html&gt;&lt;html&gt; &lt;head&gt; &lt;meta charset="utf-8"&gt; &lt;title&gt;&lt;/title&gt; &lt;!-- &lt;link href="https://cdn.bootcdn.net/ajax/libs/Swiper/6.8.1/swiper-bundle.css" rel="stylesheet"&gt; --&gt; &lt;!-- &lt;script sr

LeetCode:剑指 Offer 53 - I. 在排序数组中查找数字 I————简单_Kinght_123的博客-程序员宝宝

目录题目解题思路1Code运行结果解题思路2Code运行结果题目剑指 Offer 53 - I. 在排序数组中查找数字 I统计一个数字在排序数组中出现的次数。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: 0 限制:0 &lt;= 数组长度 &lt;= 50000解题思路1直接用Python自带的count函数。Codeclass

String Problem HDU - 3374 (最大最小表示法+kmp求模式次数)__kikyou-的博客-程序员宝宝

题目链接题目大意:给你一个字符串,求它所有同构串(末尾元素移1个到开头算一次同构)中,字典序最大以及最小的串出现的位置。位置由题目定义:如给出 SKYLONGSKYLONG 1KYLONGS 2YLONGSK 3LONGSKY 4ONGSKYL 5NGSKYLO 6GSKYLON 7很显然是一道最大最小表示法模板题。思路就是先预处理字符串str,str=str+str;然后求出最大最小字符串起始点,分别用kmp算法求出其在str中的出现次数就好了(此时的str要去掉末尾字符,否则第一个

随便推点

Security:Elastic Security 入门_Elastic 中国社区官方博客的博客-程序员宝宝

Elastic 安全是在 Elastic Stack 上构建对所有人的统一保护。Elastic Security 使分析人员能够预防,检测和响应威胁。 这个免费开放的解决方案可提供SIEM,端点安全,威胁搜寻,云监视等功能。Elastic Security 由一下的两个部分组成:在上面 Security app 指的就是在 Kibana 中的 SIEM 应用,而 Endpoint 指的就是一个安装于你系统之上的一个端点代理。通过这两个部件的组合,它可以帮安全专家解决 SIEM, 端点安全,威胁搜寻.

网络数据包收发流程(一):从驱动到协议栈_yuanhubilie的博客-程序员宝宝

早就想整理网络数据包收发流程了,一直太懒没动笔。今天下决心写了一、硬件环境intel82546:PHY与MAC集成在一起的PCI网卡芯片,很强大bcm5461:   PHY芯片,与之对应的MAC是TSECTSEC:      Three Speed Ethernet Controller,三速以太网控制器,PowerPc 架构CPU里面的MAC模块         

【多线程】吐血整理Java多线程_信徒favor的博客-程序员宝宝

多线程什么是线程安全?线程安全也不是指线程的安全,而是指内存的安全。这和操作系统有关。目前主流的操作系统都是多任务的,即多个线程同时运行。为了保证安全,每个进程只能访问分配给自己的内存空间,而不能访问别的进程,这是由操作系统保障的。线程安全指的是,在堆内存中的数据由于可以被任何线程访问到,在没有限制的情况下存在被意外修改的风险《Java并发编程》中说道,一个对象是否应该是线程安全的取决于它是否会被多个线程访问。线程安全这个性质,取决于程序中如何使用对象,而不是对象完成了什么。保证对象的线程安全性需

gp数据仓库的知识_it_liangsir的博客-程序员宝宝_gp 数仓

https://www.cnblogs.com/summer108/category/1296011.html

[洛谷]P1892 [BOI2003]团伙 (#并查集)_Apro1066的博客-程序员宝宝

题目描述1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他们要么是朋友,要么是敌人。而且有一点是肯定的,就是:我朋友的朋友是我的朋友;我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息,问你最多有多少个强盗团伙。输入格式输入文件gangs.in的第一行是一个整数N(2&lt;=N&lt;=1000),表示强盗的个...

java 项目 订单编号生成规则及代码_执檀月夜游的博客-程序员宝宝_java订单号生成规则

简单实用的java项目生成 日期时间 + 六位升序流水号 参考范例代码。一看就懂。