posts - 12,  comments - 54,  trackbacks - 0
昨晚网上搜了一下,没有找到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 = 1const 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=1const 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(110000000);
    
//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 @ 2009-12-05 12:56 Wang Feng 阅读(1369) | 评论 (1)编辑 收藏
     摘要: 影射而已,当笑话看看就行:)  阅读全文
posted @ 2009-01-11 15:33 Wang Feng 阅读(333) | 评论 (2)编辑 收藏
     摘要: 非均匀采样的数据的功率谱估计方法以及其C++实现  阅读全文
posted @ 2009-01-02 21:20 Wang Feng| 编辑 收藏
     摘要: 中午的时候翻到2007年12月24号的kde编译笔记,不知不觉一年过去了,忽有所感,于是重新编译一次kde4,记之  阅读全文
posted @ 2008-12-18 17:53 Wang Feng 阅读(398) | 评论 (0)编辑 收藏
     摘要: 探讨了一类因为偷换概念而产生的悖论。  阅读全文
posted @ 2008-11-24 20:15 Wang Feng 阅读(1999) | 评论 (10)编辑 收藏
     摘要: 一段觉得比较漂亮的代码 nth_element  阅读全文
posted @ 2008-11-06 16:47 Wang Feng 阅读(5446) | 评论 (32)编辑 收藏
请在这里(http://sourceforge.net/projects/gaplusplus/)下载源代码。cppblog不支持tar.bz2格式的文档上传。

方才在csdn灌水时,发现有人给出这个blog上文章的链接,实在汗颜。
这边的blog荒废了好久,一直没有动手写下去;
前不久把代码重构了一下,放到sf去了;

如有建议或者疑问,欢迎来信(wanng.fenng[at]gmail.com)讨论。

posted @ 2008-10-28 10:20 Wang Feng 阅读(1742) | 评论 (1)编辑 收藏
     摘要: 遗传算法中,基因变异算法  阅读全文
posted @ 2008-06-22 16:20 Wang Feng 阅读(6933) | 评论 (0)编辑 收藏
     摘要: 遗传算法中交叉算法的简单介绍。可以理解为人类社会的婚姻过程。  阅读全文
posted @ 2008-06-18 15:56 Wang Feng 阅读(8551) | 评论 (1)编辑 收藏
     摘要: 遗传算法的数据结构定义,以及相关的几个基本算法,c++实现代码。  阅读全文
posted @ 2008-06-16 16:53 Wang Feng 阅读(2327) | 评论 (0)编辑 收藏
仅列出标题  下一页

<2018年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔分类

随笔档案

Link List

搜索

  •  

最新评论

阅读排行榜

评论排行榜