Boolan網(wǎng)——C++微專業(yè)第十周學(xué)習(xí)筆記

(1)萬用的hash function
在使用以Hash Table作為底層容器的容器(例如unordered_map)時磷斧,為了能夠確定容器在Hash Table中的位置,就必須計算其Hash Code然遏。對于自定義的容器類型而言,就必須自定義相對應(yīng)的Hash Function。
<1>指定自定義的hash function的方法一:

#include<functional>
class Customer{
······
}

以上是一個自定義的類龄寞,將其作為HashTable的底層容器壁拉。利用Hash Function使系統(tǒng)清除怎樣把這個類放置在Hash Table的一個具體的位置上谬俄。

class CustomerHash
{
public:
    std::size_t operator()(const Customer& c) const{
          return /*........*/;
    }
};

在上述類中,重載了()操作符弃理,由此可以形成一個仿函數(shù)溃论。

unordered_set<Customer, CustomerHash> customers;        // CustomerHash就是相對應(yīng)的Hash Function

<2>指定自定義的hash function的方法二:

size_t customer_hash_func(const Customer& c)
{
return ······;
}
unorder_set<Customer, size(*) (const Cunstomer&)> customers(20痘昌, customer_hash_func);

這個方法實際是通過指定了一個函數(shù)指針的方式來通知容器钥勋,對于這個。自定義類到底應(yīng)該使用哪個hash function.
<3>指定自定義的hash function的方法三:以struct hash 偏特化形式實現(xiàn)hash function辆苔。

class MyString
{
 private:
    char* _data;
    size_t _len;
};
    
namespace std;
{
   template<>
   struct hash<MyStrinng>
   {
        size_t operatoe()(const MyString& s) const noexcept
        {
           return hash<string>()(string(s.get()));
        }
   }
}

對于使用將Hash Code簡單相加的方法是不合理的:

class CustomerHash
{
public:
      std::size_t operator()(const Customer& c) const{
            return std::hash<std::string>()(c.fname) 
                  + std::hash<std::string>()(c.Iname) 
                  + std::hash<long><c.no);
      }
}

雖然這個方法可以實現(xiàn)計算出Hash code笔诵,但是這樣計算的hash code的重復(fù)概率比較高;而重復(fù)的hash code 會導(dǎo)致“bucket”中的元素過多姑子,影響查詢的效率乎婿。

一個萬能的Hash Function:

class CustomerHash
{
public:
      std::size_t operator()(const Cunstomer& c) const {
            return hash_val(c.fname, c,Iname, c.no); 
      }
}

其詳細代碼:

#include<functional>
template<typename T>
inline void hash_combine(size_t& seed, const T& val){
         // 利用黃金分割比例
        seed = std::hash<T>(val) + 0x9e3779b9
              + (seed << 6) + (seed >> 2);
}

template<typename T>
inline void hash_val(size_t& seed, const T& val){
      hash_combine(seed, val);
}

template<typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Type&... args){
      hash_combine(seed, val);
      hash_val(seed, args...);
}

template<typename... Types>
inline size_t hash_val(const Types&... args){
      size_t seed = 0;
      hash_val(seed, args...);
      return seed;
}

在上述代碼中使用了variadic templates,傳入函數(shù)中的每個參數(shù)都會具備一個模版街佑,也就是說谢翎,可能每個參數(shù)的類型都會不同捍靠,那么應(yīng)該處理每個不同的參數(shù)需要一套對應(yīng)的解決方案。上述代碼就提供這樣一種對于不同類型通用的解決方案森逮。

template<typename... Types>
inline size_t hash_val(const Types&... args)

可以看作為是一個泛化的版本榨婆,因為這里面的模版可以傳入任意數(shù)量的任意模版類型。

template<typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Type&... args)

接收的參數(shù)的范圍是比第一個函數(shù)要少的褒侧,那么良风,也就是范圍其實先對減小,我們可以把它理解為偏特化的一個過程闷供,也就是在泛化中烟央,調(diào)用了偏特化的函數(shù),每次調(diào)用其實都會減少模版的數(shù)量歪脏。
針對于hash_val進行了三次重載疑俭,最后一個hash_val只接收一個模版,那么也就是最后的時候會被調(diào)用婿失,也就是钞艇,通過函數(shù)重載和模版特化的過程來一層一層把模版參數(shù)的數(shù)量解開。最后調(diào)用hash_combine的函數(shù)來計算出hash code豪硅。
hash_combine函數(shù)中的處理方式保證了最后的計算結(jié)果足夠Hash哩照。
(2)tuple
tuple可以存放不同類型的數(shù)據(jù)。

#include <iostream>     // std::cout
#include <tuple>        // std::tuple, std::get, std::tie, std::ignore

int main()
{
    //通過構(gòu)造函數(shù)來創(chuàng)建tuple對象
    std::tuple<int, char> foo(10, 'x');

    //通過make_tuple來創(chuàng)建tuple對象懒浮,并且可以實現(xiàn)自動類型推到
    //實際的類型應(yīng)該為: tuple<string, double, int, char>
    auto bar = std::make_tuple("test", 3.1, 14, 'y');

    // 從tuple中獲取數(shù)據(jù)
    std::get<2>(bar) = 100;                                    // access element

    int myint; char mychar;
    //通過tie函數(shù)來從tuple中一次性獲取所有的數(shù)據(jù)
    std::tie(myint, mychar) = foo;                            // unpack elements

    //也可以通過std::ignore跳過部分不需要的元素飘弧,只取出需要的元素
    std::tie(std::ignore, std::ignore, myint, mychar) = bar;  // unpack (with ignore)

    mychar = std::get<3>(bar);

    //直接修改其中元素的值
    std::get<0>(foo) = std::get<2>(bar);
    std::get<1>(foo) = mychar;

    std::cout << "foo contains: ";
    std::cout << std::get<0>(foo) << ' ';
    std::cout << std::get<1>(foo) << '\n';

    typedef tuple<int, float, string> TupleType;
    //獲取tuple中的元素個數(shù)
    cout << tuple_size<TupleType>::value << endl;  //3
    //獲取元素類型
    tuple_element<1, TupleType>::type f1 = 1.0;  //float

    return 0;
}

tuple的實現(xiàn)原理(GNU4.8節(jié)選并簡化版本):

//只有一個模版參數(shù)的版本的特化版本
        template<typename Values> class tuple;
        //沒有模版參數(shù)的版本的特化版本
        template<> class tuple < > {};

        //每次都會繼承剔除掉第一個模版參數(shù)的class
        template<typename Head, typename... Tail>
        class tuple<Head, Tail...> : private tuple < Tail... >
        {
            typedef tuple<Tail...> inherited;
            public:
                tuple();
                tuple(Head v, Tail... vtail) :m_head(v), inherited(vtail...){}

                typename Head::type head() { return m_head; }
            protected:
                Head m_head;
        };

為了能夠處理每個不同類型的元素,tuple自動在多個參數(shù)之間構(gòu)建了繼承關(guān)系嵌溢。每次繼承的都是模版的后半部分,逐漸將第一個模版參數(shù)解析出來蹋岩。在tuple中赖草,head()可以返回第一個元素的值;tail()可以返回父類成分起點剪个,返回類型是父類的類型秧骑。
(3)TypeTraits
GNU 2.9版本:

//泛化
template<class type>
struct __type_traits{
    typedef __true_type this_dummy_member_must_be_first;
    typedef __false_type has_trivial_default_constructor;
    typedef __false_type has_trivial_copy_constructor;
    typedef __false_type has_trivial_assignment_operator;
    typedef __false_type has_trivial_destructor;
    typedef __false_type is_POD_type;  //POD = Plain Old Data,代表舊式的class 也就是struct
}扣囊;

//int的特化
template<>
struct __type_traits < int > {
    typedef __true_type has_trivial_default_constructor;
    typedef __true_type has_trivial_copy_constructor;
    typedef __true_type has_trivial_assignment_operator;
    typedef __true_type has_trivial_destructor;
    typedef __true_type is_POD_type;
}

//double的特化
template<>
struct __type_traits < double > {
    typedef __true_type has_trivial_default_constructor;
    typedef __true_type has_trivial_copy_constructor;
    typedef __true_type has_trivial_assignment_operator;
    typedef __true_type has_trivial_destructor;
    typedef __true_type is_POD_type;
}

在上述代碼中乎折,通過模板的泛化以及特化機制使得不同的類型進入不同的代碼邏輯中。
利用typedef標(biāo)志類型的特征:是否有默認的構(gòu)造函數(shù)侵歇,拷貝構(gòu)造骂澄,賦值構(gòu)造,析構(gòu)函數(shù)等惕虑。
對于自定義的類型坟冲,用戶需要自己定義相對應(yīng)的type traits磨镶。
從C++2.0 開始,type traits的復(fù)雜程度大幅上升健提。此時不需要再重新定義type traits琳猫。

{
    std::cout << "int: " << std::is_trivially_copy_constructible<int>::value << std::endl;
}

type_traits的實現(xiàn):
<1>is_void

//去除const
template<typename _Tp>
struct remove_const{
    typedef _Tp type;
};
template<typename _Tp>
struct remove_const < _Tp const > {
    typedef _Tp type;
};
//volatile
template<typename _Tp>
struct remove_volotile{
    typedef _Tp type;
};
template<typename _Tp>
struct remove_volotile < _Tp volatile > {
    typedef _Tp type;
};
//去除const和volatile
template<typename _Tp>
struct remove_cv{
    typedef remove_const<typename remove_volatile<_Tp>::type>::type type;
};

template<typename>
struct __is_void_helper : public false_type{};

template<>
struct __is_void_helper<void> :public true_type{};

//is_void
template<typename _Tp>
struct is_void:public __is_void_helper<typename remove_cv<_Tp>::type>::type {}

<2>is_integral

typename<typename>
struct __is_integral_helper:public false_type{};

typename<>
struct __is_integral_helper<bool>:public true_type{};

typename<>
struct __is_integral_helper<char>:public true_type{};

typename<>
struct __is_integral_helper<signed char>:public true_type{};

typename<>
struct __is_integral_helper<unsigned char>:public true_type{};

template<>
struct __is_integral_helper<int>:public true_type{};

template<>
struct __is_integral_helper<unsigned int>:public true_type{};

template<>
struct __is_integral_helper<long>:public true_type{};

template<>
struct __is_integral_helper<unsigned long>:public true_type{};

template<>
struct __is_integral_helper<long long> :public true_type{};

template<>
struct __is_integral_helper<unsigned long long>:public true_type{};

//is_integral
template<typename _Tp>
struct __is_integral:public __is_integral_helper<typename remove_cv<_Tp>::type>::type{};

<3>is_class, is_union, is_enum, is_pod

//is_enum
template<typename _Tp>
struct is_enum:public integral_constant < bool, __is_enum(_Tp) > {};

//is_union
template<typename _Tp>
struct is_union:public integral_constant < bool, __is_union(_Tp) > {};

//is_class
template<typename _Tp>
struct is_class:public integral_constant < bool, __is_class(_Tp) > {};

//is_pod
//Could use is_standard_layout && is_trivial instead of the builtin.
template<typename _Tp>
struct is_pod:public integral_constant<bool, __is_pod(_Tp)>();

__is_xxx(_Tp)不存在與標(biāo)準(zhǔn)庫中,應(yīng)該是編譯器的底層機制私痹。
<4>is_move_assignable

template<typename _Tp, bool = __is_referenceable<_Tp>::value>
struct __is_move_assignable_impl;

template<typename _Tp>
struct __is_move_assignable_impl<_Tp, false> :public false_type{};

template<typename _Tp>
struct __is_move_assignable_impl<_Tp, true> :public is_assignable < _Tp&, _Tp&& > {};

template<typename _Tp>
struct __is_referenceable :public __or_<is_object<_Tp>, is_reference<_Tp>>::type

template<typename _Res, typename... _Args>
struct __is_referenceable<_Res(_Args...)> :public true_type{};

template<typename _Res, typename... _Args>
struct __is_referenceable<_Res(_Args......)> :public true_type{};

//is_move_assignable
template<typename _Tp>
struct is_move_assignable :public __is_move_assignable_impl < _Tp > {};

(4)cout

class ostream : virual public ios
{
public:
    ostream& operator << (char c);
    ostream& operator << (unsigned char c){ return (*this) << (char)c; };
    ostream& operator << (signed char c){ return (*this) << (char)c; };
    //cout根據(jù)操作符重載的方式來使得cout可以接受許多的類型
};

class _IO_ostream_withassign : public ostream
{
public:
    _IO_ostream_withassign& operator= (ostream&);
    _IO_ostream_withassign& operator=(_IO_ostream_withassign& rhs){
        return oprator = (static_cast<ostream&> (rhs);
    }
}

extern _IO_ostream_withassign cout;

(5)moveable元素對于容器影響
<1>對vector的影響


在進行數(shù)據(jù)插入是脐嫂,vector會進行多次容積增長,其中要調(diào)用copy Constructer或move Constructer紊遵。有move Constructer的結(jié)果會更快账千。
<2>對list的影響


在list的數(shù)據(jù)插入過程中不存在過多的數(shù)據(jù)搬移,所以有沒有move Constructer對效率差別不大癞蚕。
同樣對于deque蕊爵、multiset、ubordered_multiset的效率影響也不大桦山。

定義一個moveable class:

class MyString{
public:
    static size_t DCtor;    //累計調(diào)用默認ctor的次數(shù)
    static size_t Ctor;     //累計ctor的調(diào)用次數(shù)
    static size_t CCtor;    //累計copy-ctor的調(diào)用次數(shù)
    static size_t CAsgn;  //累計copy-asgn的調(diào)用次數(shù)
    static size_t MCtor;  //累計move-ctor的調(diào)用次數(shù)
    static size_t MAsgn;  //累計move-asgn的調(diào)用次數(shù)
    static size_t Dtor; //累計dtor的調(diào)用次數(shù)

private:
    char* _data;
    size_t _len;
    void _init_data(const char* s){
        _data = new char[_len + 1];
         memcpy(_data, s, _len);
        _data[_len] = '0';
    }
public:
    //default ctor;
    MyString() :_data(NULL), _len(0){ ++DCtor; }
    //ctor
    MyString(const char* p) : _len(strlen(p)){
        ++Ctor;
        _init_data(p);
    }

    //copy ctor
    MyString(const  MyString& str) : _len(str._len){
        ++CCtor;
        _init_data(str._data);
    }

    //move ctor, with noexcept
    MyString(MyString&& str) noexcept : _data(str._data), _len(str._len){
        ++MCtor;
        str._len = 0;
        str._data = NULL;  //避免delete(in dtor)
    }

    //cope assignment 
    MyString& operator= (const MyString& str){
        ++CAsgn;
        if (this != &str){
            if (_data) delete _data;
            _len = str._len;
            _init_data(str._data);
        }
        return *this;
    }

    //move assignment
    MyString& operator=(MyString&& str) noexcept{
        ++MAsgn;
        if (this != &str){
            if (_data) delete _data;
            _len = str._len;
            _data = str._data;  //move
            str._len = 0;
            str._data = NULL;
        }
        return *this;
    }

    //dtor
    virtual ~MyString(){
        ++Dtor;
        if (_data) delete _data;
    }

    bool operator< (const MyString& rhs) const{
        return std::string(this->_data) < std::string(rhs._data);
    }

    bool operator==(const MyString& rhs) const{
        return std::string(this->_data) == std::string(rhs._data);
    }
    char* get() const { return _data; }

};

size_t MyString::DCtor = 0;
size_t MyString::Ctor = 0;
size_t MyString::CCtor = 0;
size_t MyString::CAsgn = 0;
size_t MyString::MCtor = 0;
size_t MyString::MAsgn = 0;
size_t MyString::Dtor = 0;

namespace std{
    template<>
    struct hash < MyString > {
        size_t operator()(const MyString& s)const noexcept{ return hash<string>()(string(s.get())); }
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末攒射,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子恒水,更是在濱河造成了極大的恐慌会放,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,657評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件钉凌,死亡現(xiàn)場離奇詭異咧最,居然都是意外死亡,警方通過查閱死者的電腦和手機御雕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評論 3 394
  • 文/潘曉璐 我一進店門矢沿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人酸纲,你說我怎么就攤上這事捣鲸。” “怎么了闽坡?”我有些...
    開封第一講書人閱讀 164,057評論 0 354
  • 文/不壞的土叔 我叫張陵栽惶,是天一觀的道長。 經(jīng)常有香客問我疾嗅,道長外厂,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,509評論 1 293
  • 正文 為了忘掉前任代承,我火速辦了婚禮汁蝶,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘论悴。我一直安慰自己穿仪,他們只是感情好席爽,可當(dāng)我...
    茶點故事閱讀 67,562評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著啊片,像睡著了一般只锻。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上紫谷,一...
    開封第一講書人閱讀 51,443評論 1 302
  • 那天齐饮,我揣著相機與錄音,去河邊找鬼笤昨。 笑死祖驱,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的瞒窒。 我是一名探鬼主播捺僻,決...
    沈念sama閱讀 40,251評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼崇裁!你這毒婦竟也來了匕坯?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,129評論 0 276
  • 序言:老撾萬榮一對情侶失蹤拔稳,失蹤者是張志新(化名)和其女友劉穎葛峻,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體巴比,經(jīng)...
    沈念sama閱讀 45,561評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡术奖,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,779評論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了轻绞。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片采记。...
    茶點故事閱讀 39,902評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖政勃,靈堂內(nèi)的尸體忽然破棺而出唧龄,到底是詐尸還是另有隱情,我是刑警寧澤稼病,帶...
    沈念sama閱讀 35,621評論 5 345
  • 正文 年R本政府宣布选侨,位于F島的核電站掖鱼,受9級特大地震影響然走,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜戏挡,卻給世界環(huán)境...
    茶點故事閱讀 41,220評論 3 328
  • 文/蒙蒙 一芍瑞、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧褐墅,春花似錦拆檬、人聲如沸洪己。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽答捕。三九已至,卻和暖如春屑那,著一層夾襖步出監(jiān)牢的瞬間拱镐,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評論 1 269
  • 我被黑心中介騙來泰國打工持际, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留沃琅,地道東北人。 一個月前我還...
    沈念sama閱讀 48,025評論 2 370
  • 正文 我出身青樓蜘欲,卻偏偏與公主長得像益眉,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子姥份,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,843評論 2 354

推薦閱讀更多精彩內(nèi)容