国产欧美精品一区,久久久女女女女999久久,亚洲国产精品999

位图索引排序

Wang Feng — Sat, 05 Dec 2009 04:56:00 GMT

昨晚�|�上搜了一下，没有扑ֈ�C++实现的代码，于是自己写了一个；
无心在这里copy/paste位图排序的具体解释，如果有知道得不详�l�的�Q�请讉K��Wikipedia�?br />

  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  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 bs(10000000, 1);

    bs.process((istream_iterator<unsigned long>(cin)), (istream_iterator<unsigned long>()));

    bs.produce(ostream_iterator<unsigned long>(cout, "\n"));

    return 0;
}

Wang Feng 2009-12-05 12:56 发表评论

Wang Feng — Sun, 11 Jan 2009 07:33:00 GMT

摘要: 影射而已�Q�当�W�话看看��p��Q�）阅读全文

Wang Feng 2009-01-11 15:33 发表评论

非均匀取样数据的功率谱估计�Ҏ��

Wang Feng — Fri, 02 Jan 2009 13:20:00 GMT

摘要: 非均匀采样的数据的功率�׃��计方法以及其C++实现阅读全文

Wang Feng 2009-01-02 21:20 发表评论

kde4 svn �~�译�W�记

Wang Feng — Thu, 18 Dec 2008 09:53:00 GMT

摘要: 中午的时候翻�?007�q?2�?4��L��kde�~�译�W�记�Q�不知不觉一�q�过��M��Q�忽有所感，于是重新�~�译一�ơkde4�Q�记�?nbsp; 阅读全文

Wang Feng 2008-12-18 17:53 发表评论

Wang Feng — Mon, 24 Nov 2008 12:15:00 GMT

摘要: 探讨了一�c�d��为偷换概念而��生的悖论�?nbsp; 阅读全文

Wang Feng 2008-11-24 20:15 发表评论

Wang Feng — Thu, 06 Nov 2008 08:47:00 GMT

摘要: 一�D�觉得比较漂亮的代码 nth_element 阅读全文

Wang Feng 2008-11-06 16:47 发表评论

��遗传算法的库放到sf��M��

Wang Feng — Tue, 28 Oct 2008 02:20:00 GMT

请在�q�里(http://sourceforge.net/projects/gaplusplus/)下蝲源代码。cppblog不支持tar.bz2格式的文档上传�?br>
�Ҏ��在csdn灌水�Ӟ��发现有�h�l�出�q�个blog上文章的链接�Q�实在汗颜�?br>�q�边的blog荒废了好久，一直没有动手写下去�Q?br>前不久把代码重构了一下，攑ֈ�sf��M��Q?br>
如有��或者疑问，�Ƣ迎来信(wanng.fenng[at]gmail.com)讨论�?br>

Wang Feng 2008-10-28 10:20 发表评论