• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 12,  comments - 54,  trackbacks - 0
            昨晚網(wǎng)上搜了一下,沒有找到C++實現(xiàn)的代碼,于是自己寫了一個;
            無心在這里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 閱讀(1666) 評論(1)  編輯 收藏 引用 所屬分類: Numerical C++

            FeedBack:
            # re: 位圖排序
            2009-12-08 12:39 | 阿福
            位圖索引在數(shù)據(jù)庫中還是很常見的。
            而且位圖索引是不能排序的吧?
            只是方便找出大量重復的某類值而已。  回復  更多評論
              

            <2008年10月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(4)

            隨筆分類

            隨筆檔案

            Link List

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            99久久久久| 久久久精品午夜免费不卡| 亚洲国产精品久久久久婷婷软件 | 久久久久亚洲国产| 久久夜色精品国产www| 久久国产成人午夜aⅴ影院| 狠狠精品久久久无码中文字幕 | 99久久免费国产精品特黄| 亚洲欧洲精品成人久久奇米网| 久久精品无码免费不卡| 亚洲精品tv久久久久久久久久| 久久久久久国产a免费观看不卡 | 久久免费视频1| 久久久无码精品亚洲日韩蜜臀浪潮| 亚洲va久久久噜噜噜久久| 粉嫩小泬无遮挡久久久久久| 国产精品一久久香蕉国产线看| 国产精品久久久久影视不卡| 66精品综合久久久久久久| 久久影视国产亚洲| 97久久国产综合精品女不卡| 久久精品蜜芽亚洲国产AV| 2020最新久久久视精品爱| 亚洲va久久久久| 精品久久久久久久| 欧美亚洲国产精品久久久久| 久久精品无码专区免费东京热 | 狠狠色婷婷综合天天久久丁香| 香港aa三级久久三级| 亚洲国产婷婷香蕉久久久久久| 浪潮AV色综合久久天堂| 91精品国产91久久久久久青草| 久久夜色精品国产亚洲| 久久99热精品| 亚洲欧美伊人久久综合一区二区 | 欧美亚洲国产精品久久蜜芽| 国产精品久久婷婷六月丁香| 国产福利电影一区二区三区久久久久成人精品综合| 国产精品久久久久乳精品爆| 乱亲女H秽乱长久久久| 欧美国产精品久久高清|