用于搜索的C++类--出自《编程珠玑》第二版的附录E

2024-06-23 15:32
文章标签 c++ 用于 搜索 编程 第二 附录 出自 珠玑

本文主要是介绍用于搜索的C++类--出自《编程珠玑》第二版的附录E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天记录的是《编程珠玑》第二版的附录E代码，本人经过完善之后，聊以自娱，记录一下。代码在VS2017上编译通过。

#include <set>
#include <random>
#include <iostream>class CIntSetSTL
{
public:CIntSetSTL(int max_elements, int max_values){}size_t size()const{return m_set.size();}void insert(int value){m_set.insert(value);}void report(int *p_values)const{int index = 0;for (auto value : m_set){p_values[index++] = value;}}
private:std::set<int> m_set;
};class CIntSetArray
{
public:CIntSetArray(int max_elements, int max_value){m_p_array = new int[max_elements + 1]();m_p_array[0] = max_value;m_element_num = 0;}~CIntSetArray(){delete[] m_p_array;}size_t size()const{return m_element_num;}void insert(int value){size_t index = 0;while (m_p_array[index] < value){++index;}if (m_p_array[index] == value){return;}for (size_t index_tmp = m_element_num; index_tmp >= index; --index_tmp){m_p_array[index_tmp + 1] = m_p_array[index_tmp];if (index_tmp == 0){break;}}m_p_array[index] = value;++m_element_num;}void report(int *p_values)const{for (size_t index = 0; index < m_element_num; ++index){p_values[index] = m_p_array[index];}}
private:int *m_p_array = nullptr;size_t m_element_num;
};class CIntSetList
{
public:CIntSetList(int max_elements, int max_value){m_p_list_head = m_p_list_sentinel = new SListNode(max_value, nullptr);m_element_num = 0;}~CIntSetList(){SListNode *p_node_tmp = nullptr;SListNode *p_node = m_p_list_head;while (p_node != m_p_list_sentinel){p_node_tmp = p_node->m_p_next_node;delete p_node;p_node = p_node_tmp;}delete m_p_list_sentinel;}size_t size()const{return m_element_num;}void insert(int value){m_p_list_head = rinsert(m_p_list_head, value);}void report(int *p_values)const{size_t index = 0;for (SListNode *p_node = m_p_list_head; p_node != m_p_list_sentinel; p_node = p_node->m_p_next_node){p_values[index++] = p_node->m_value;}}private:struct SListNode{SListNode(int value, SListNode *p_next_node){m_value = value;m_p_next_node = p_next_node;}int m_value = 0;SListNode *m_p_next_node = nullptr;};size_t m_element_num = 0;SListNode *m_p_list_head = nullptr;SListNode *m_p_list_sentinel = nullptr;SListNode *rinsert(SListNode *p_node, int value){if (p_node->m_value < value){p_node->m_p_next_node = rinsert(p_node->m_p_next_node, value);}else if(p_node->m_value > value){p_node = new SListNode(value, p_node);++m_element_num;}return p_node;}
};class CIntSetBST
{
public:CIntSetBST(int max_elements, int max_value){}~CIntSetBST(){deleteAllNode(m_p_root);}size_t size()const{return m_element_num;}void insert(int value){m_p_root = rinsert(m_p_root, value);}void report(int *p_values){m_p_array = p_values;m_array_num = 0;traverse(m_p_root);}
private:struct SBSTNode{SBSTNode(int value){m_value = value;}int m_value = 0;SBSTNode *m_p_left_node = nullptr;SBSTNode *m_p_right_node = nullptr;};size_t m_element_num = 0;int *m_p_array = nullptr;size_t m_array_num = 0;SBSTNode *m_p_root = nullptr;SBSTNode *rinsert(SBSTNode *p_node, int value){if (p_node == nullptr){p_node = new SBSTNode(value);++m_element_num;}else if (p_node->m_value > value){p_node->m_p_left_node = rinsert(p_node->m_p_left_node, value);}else if (p_node->m_value < value){p_node->m_p_right_node = rinsert(p_node->m_p_right_node, value);}return p_node;}void traverse(SBSTNode *p_node){if (p_node == nullptr){return;}traverse(p_node->m_p_left_node);m_p_array[m_array_num++] = p_node->m_value;traverse(p_node->m_p_right_node);}void deleteAllNode(SBSTNode *p_node){if (p_node == nullptr){return;}deleteAllNode(p_node->m_p_left_node);deleteAllNode(p_node->m_p_right_node);delete p_node;}
};class CIntSetBitVec
{
public:CIntSetBitVec(int max_elements, int max_value){m_max_value = max_value;m_p_array = new int[1 + max_value / BITSPERWORD];for (int index = 0; index < max_value; ++index){clr(index);}m_element_num = 0;}~CIntSetBitVec(){delete[] m_p_array;}size_t size()const{return m_element_num;}void insert(int value){if (test(value) != 0){return;}set(value);++m_element_num;}void report(int *p_values){size_t index_tmp = 0;for (int index = 0; index < m_max_value; ++index){if (test(index) != 0){p_values[index_tmp++] = index;}}}
private:enum{BITSPERWORD = 32,SHIFT = 5,MASK = 0x1F};size_t m_element_num = 0;int m_max_value = 0;int *m_p_array = nullptr;void set(int value){m_p_array[value >> SHIFT] |= (1 << (value & MASK));}void clr(int value){m_p_array[value >> SHIFT] &= ~(1 << (value & MASK));}int test(int value)const{return m_p_array[value >> SHIFT] & (1 << (value & MASK));}
};class CIntSetBins
{
public:CIntSetBins(int max_elements, int max_value){m_bins_num = max_elements;m_max_value = max_value;m_p_bins_array = new SBinNode *[m_bins_num];m_p_sentinel = new SBinNode(max_value, nullptr);for (int index = 0; index < m_bins_num; ++index){m_p_bins_array[index] = m_p_sentinel;}m_element_num = 0;}~CIntSetBins(){for (int index = 0; index < m_bins_num; ++index){SBinNode *p_node_tmp = nullptr;SBinNode *p_node = m_p_bins_array[index];while (p_node != m_p_sentinel){p_node_tmp = p_node->m_p_next_node;delete p_node;p_node = p_node_tmp;}}delete m_p_sentinel;}size_t size()const{return m_element_num;}void insert(int value){int index = value / (1 + m_max_value / m_bins_num);m_p_bins_array[index] = rinsert(m_p_bins_array[index], value);}void report(int *p_values)const{int index_tmp = 0;for (int index = 0; index < m_bins_num; ++index){for (SBinNode *p_node = m_p_bins_array[index]; p_node != m_p_sentinel; p_node = p_node->m_p_next_node){p_values[index_tmp++] = p_node->m_value;}}}
private:size_t m_element_num = 0;int m_bins_num = 0;int m_max_value = 0;struct SBinNode{SBinNode(int value, SBinNode *p_node){m_value = value;m_p_next_node = p_node;}int m_value = 0;SBinNode *m_p_next_node = nullptr;};SBinNode **m_p_bins_array = nullptr;SBinNode *m_p_sentinel = nullptr;SBinNode *rinsert(SBinNode *p_node, int value){if (p_node->m_value < value){p_node->m_p_next_node = rinsert(p_node->m_p_next_node, value);}else if (p_node->m_value > value){p_node = new SBinNode(value, p_node);++m_element_num;}return p_node;}
};enum
{ARRAY_NUM = 1000,ARRAT_MAX_VALUE = 10000
};void OutputArray(int *p_array, int array_length)
{if ((p_array == nullptr)|| (array_length <= 0)){return;}for (int index = 0; index < array_length; ++index){std::cout << p_array[index] << " ";}std::cout << std::endl;
}int main()
{int int_array[ARRAY_NUM] = { 0 };std::default_random_engine dre;std::uniform_int_distribution<> uid(0, ARRAT_MAX_VALUE - 1);{CIntSetSTL iss(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){iss.insert(uid(dre));}iss.size();iss.report(int_array);OutputArray(int_array, ARRAY_NUM);}{CIntSetArray isa(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){isa.insert(uid(dre));}isa.size();isa.report(int_array);OutputArray(int_array, ARRAY_NUM);}{CIntSetList isl(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){isl.insert(uid(dre));}isl.size();isl.report(int_array);OutputArray(int_array, ARRAY_NUM);}{CIntSetBST isb(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){isb.insert(uid(dre));}isb.size();isb.report(int_array);OutputArray(int_array, ARRAY_NUM);}{CIntSetBitVec isbv(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){isbv.insert(uid(dre));}isbv.size();isbv.report(int_array);OutputArray(int_array, ARRAY_NUM);}{CIntSetBins isbs(ARRAY_NUM, ARRAT_MAX_VALUE);for (size_t index = 0; index < ARRAY_NUM; ++index){isbs.insert(uid(dre));}isbs.size();isbs.report(int_array);OutputArray(int_array, ARRAY_NUM);}return 0;
}

 

这篇关于用于搜索的C++类--出自《编程珠玑》第二版的附录E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1087554。

相关文章

C++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2