昨晚網上搜了一下，沒有找到C++實現的代碼，于是自己寫了一個；
無心在這里copy/paste位圖排序的具體解釋，如果有知道得不詳細的，請訪問
Wikipedia。
??1?#ifndef?_BITMAP_HPP_INCLUDED
??2?#define?_BITMAP_HPP_INCLUDED
??3?
??4?#include?<cstring>?//for?memset
??5?
??6?
??7?namespace?feng
??8?{
??9?
?10?template<typename?Type>
?11?class?Bitmap_Sort
?12?{
?13?????????typedef?Type?template_type;
?14?????private:
?15?????????struct?_Bitmap_Impl;
?16?????????_Bitmap_Impl*?bi_;
?17?????public:
?18?????????Bitmap_Sort(?const?template_type&?lower?=?1,?const?template_type&?upper?=?100?)
?19?????????{
?20?????????bi_?=?lower?<?upper??
?21?????????????new?_Bitmap_Impl(lower,upper)?:?
?22?????????????new?_Bitmap_Impl(upper,lower);
?23?
?24?????????}
?25?????????~Bitmap_Sort()
?26?????????{
?27?????????delete?bi_;
?28?????????}
?29?
?30?????????void?process(?const?template_type&?v?)?const
?31?????????{
?32?????????????(*bi_).register_number(?v?);
?33?????????}
?34?
?35?????????template<typename?Input_Itor>
?36?????????void?process(?Input_Itor?begin,?Input_Itor?end?)?const
?37?????????{
?38?????????while?(?begin?!=?end?)
?39?????????????(*bi_).register_number(?*begin++?);
?40?????????//including?<algorithm>?is?not?of?necessity
?41?????????//for_each(?begin,?end,?&((*bi_).register_number)?);?
?42?????????}
?43?
?44?????????template<typename?Output_Itor>
?45?????????Output_Itor?produce(?Output_Itor?begin?)?const
?46?????????{
?47?????????for?(?Type?i?=?(*bi_).lower_;?i?<=?(*bi_).upper_;?++i?)
?48?????????????if?(?(*bi_).query_number(i)?)
?49?????????????*begin++?=?i;
?50?????????return?begin;
?51?????????}
?52?};
?53?
?54?
?55?template<typename?Type>
?56?struct?Bitmap_Sort<Type>?::?_Bitmap_Impl?
?57?{
?58?????????typedef?unsigned?long?word_type;
?59?????typedef?Type?template_type;
?60?
?61?????_Bitmap_Impl(?const?template_type&?lower=1,?const?template_type&?upper=100?)
?62?????????:?lower_(lower),upper_(upper)
?63?????{
?64?????????????const?template_type?length?=?upper?-?lower?+?1;
?65?????????const?word_type?size?=?(length >> bit_shift())?+?1;?
?66?????????
?67?????????buffer_?=??new?word_type[size];
?68?????????
?69?????????memset(buffer_,size,0);
?70?????}
?71?????~_Bitmap_Impl()
?72?????{?
?73?????????delete?[]?buffer_;?
?74?????}
?75?
?76?????bool?register_number(?const?template_type&?v?)?const
?77?????{
?78?????????bool?ans?=?false;
?79?????????if?(?v?<=?upper_?&&?v?>=?lower_?)
?80?????????{
?81?????????????const?template_type?shift?=?v?-?lower_;
?82?????????????const?word_type?arr_position?=?shift?>>?bit_shift();
?83?????????????const?word_type?relative_position?=?shift?&?(?(1?<<?bit_shift())?-?1?);
?84?????????????const?word_type?patch?=?1?<<?(?relative_position?+?1?);
?85?????????????buffer_[arr_position]?|=?patch;
?86?????????????ans?=?true;
?87?????????}
?88?????????return?ans;
?89?????}
?90?????bool?query_number(?const?template_type&?v?)?const
?91?????{
?92?????????bool?ans?=?false;
?93?????????//not?necessory,?commented
?94?????????//if?(?v?<=?upper_?&&?v?>=?lower_?)
?95?????????//{
?96?????????const?template_type?shift?=?v?-?lower_;
?97?????????const?word_type?arr_position?=?shift?>>?bit_shift();
?98?????????const?word_type?relative_position?=?shift?&?(?(1?<<?bit_shift())?-?1?);
?99?????????const?word_type?patch?=?1?<<?(?relative_position?+?1?);
100?????????if(?buffer_[arr_position]?&?patch?)
101?????????????ans?=?true;
102?????????//}
103?????????return?ans;
104?????}
105?
106?????const?word_type?bit_shift()?const
107?????{
108?????????return? 8 == sizeof(unsiged long) ? 6 : 5;
110?????}
111?????
112?????template_type?lower_;
113?????template_type?upper_;
114?????mutable?word_type*?buffer_;
115?};
116?
117?
118?}//namespace?feng
119?
120?#endif?//_BITMAP_HPP_INCLUDED
121?
122?
123?
一個測試用例：
#include?<bitmap.hpp>
#include?<iostream>
#include?<iterator>
using?namespace?std;
int?main()
{
????feng::Bitmap_Sort<unsigned?long>?bs(1,?10000000);
????//feng::Bitmap_Sort<unsigned?long>?bs(10000000,?1);
????bs.process((istream_iterator<unsigned?long>(cin)),?(istream_iterator<unsigned?long>()));
????bs.produce(ostream_iterator<unsigned?long>(cout,?"\n"));
????return?0;
}
posted on 2009-12-05 12:56
Wang Feng 閱讀(1665)
評論(1) 編輯 收藏 引用 所屬分類:
Numerical C++