用于搜索的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++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
Go语言数据库编程GORM 的基本使用详解

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2