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

本文主要是介绍用于搜索的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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---