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

2024-06-23 15:32

本文主要是介绍用于搜索的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++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提