昨晚网上搜了一下，没有找到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 阅读(1639)
评论(1) 编辑 收藏 引用 所属分类:
Numerical C++