丰满邻居无码一区,在线色女av,亚洲欧洲精品国产少妇

關(guān)于STL的話題已經(jīng)探討了好幾個篇了，今天來討論一下剩下的一些內(nèi)容吧

一個萬用的hash function

使用以Hash Table為底層的容器，比如unordered_map（hash_map），在使用個過程中，需要有計算hash code的方法來計算出元素在hashtable中的具體位置。
那么對于自定義類型來說，需要指定對應(yīng)的Hash Function，只有這樣才能在使用的過程，系統(tǒng)找到對應(yīng)元素應(yīng)該插入的位置，以便系統(tǒng)自動管理我們需要插入到容器中的各個元素。關(guān)于這個函數(shù)該如何定義，對于不同個自定義類型來說并不相同，也沒有辦法找到一個通用的方式，畢竟石頭類和動物類，他們各自的hash function多少會有些區(qū)別吧，具體的定義，還需要依靠開發(fā)這自己了。
那么，為什么后還會有關(guān)于個萬用的hash function呢？關(guān)于這個問題，先放下不說，咱們先來看看關(guān)于指定hash function的方式吧。

指定自定義的hash function的方法一

#include<functional>
class Customer{
      //........
};
//這是一個自定義的類，如果使用他作為hashtable為底層的容器時
//系統(tǒng)需要知道如何把他插入到hashtable中的具體位置去


//通過一個類，重載了操作符()的方式，形成了一個仿函數(shù)（函數(shù)對象）
class CustomerHash
{
public:
      std::size_t operator()(const Customer& c) const{
            return /*........*/;
      }
};

//使用
unordered_set<Customer, CustomerHash> customers;
//聲明容器變量時，指定的第二參數(shù)，就是對應(yīng)的Hash Function
//實際在第二參數(shù)中指定的是一個函數(shù)對象

指定自定義的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

指定自定義的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 function，但是到底能不能有一個萬能的hash function呢？不論自定義的的class，內(nèi)涵的成員是由什么組成，總歸都是有基本數(shù)據(jù)類型所組成（比如int、char、double等），而之前我們也提過，基本數(shù)據(jù)類型，STL是提供了一套Hash Function的實現(xiàn)代碼的。那么，能否依靠之前我們提到的方法將hash code相加來獲取該對象的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 會導致“bucket”中的元素過多，影響查詢的效率

其實在*** C++ TR1 ***的版本后，STL為我么提供了一套萬用的Hash Function。那么應(yīng)該如何使用呢？咱們就先來看看吧。

//使用萬能的Hash Function
class CustomerHash
{
public:
      std::size_t operator()(const Cunstomer& c) const {
            return hash_val(c.fname, c,Iname, c.no);  
            //在此，只需要調(diào)用hash_val函數(shù)，并把每個成員的值傳遞給他就行了
      }
}

咱們看過了這個萬用Hash Functon的使用，那么他其中的實現(xiàn)原理到底是什么呢？咱們來看看他的代碼吧。

#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;
}

上面的代碼其實寫的還是比較巧妙的，并且使用了一個C++的新特性，名字是variadic templates，也就是可以傳入多個模版。他的作用有點類似與可變參數(shù)的傳遞，但是對于可變參數(shù)來說，改變的是參數(shù)的個數(shù)，他們的類型都是相同的。可以通過頭文件<stdarg.h>中的va_list中的一些列函數(shù)來拿出傳入的每個變量。

而對于variadic templates來說，很重要的是，傳入函數(shù)中的每個參數(shù)都會具備一個模版，也就是說，可能每個參數(shù)的類型都會不同，那么應(yīng)該處理每個不同的參數(shù)需要一套對應(yīng)的解決方案

其實上面的代碼就是這套方案的解法，其實對于函數(shù)

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

來說可以看作為是一個泛化的版本，因為這里面的模版可以傳入任意數(shù)量的任意模版類型。
而函數(shù)

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

不難看出，他的模版變?yōu)榱?** 1 + n ***的模式也正是由于這樣的模式，他接收的參數(shù)的范圍是比第一個函數(shù)要少的，那么，也就是范圍其實先對減小，我們可以把它理解為偏特化的一個過程，也就是在泛化中，調(diào)用了偏特化的函數(shù)，每次調(diào)用其實都會減少模版的數(shù)量。
觀察之前源碼中的四個函數(shù)不難看出，有三個重載，而最后一個hash_val只接收一個模版，那么也就是最后的時候會被調(diào)用，也就是，通過函數(shù)重載和模版特化的過程來一層一層把模版參數(shù)的數(shù)量解開。
而最后四級都是調(diào)用hash_combine的函數(shù)來計算出hash code。

tuple

tuple是在C++ 2.0之后引進的一種存放元素的集合，通過這個集合，可以存放不同類型的數(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ù)的版本的特化版本
templat<> 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<int, float, string> t(6, 6.3, "xxxxx")` UML圖

tuple可以自動幫我們將多個參數(shù)實現(xiàn)繼承，通過這樣的繼承方式，來處理每個元素的不同的類型。每次繼承的都是模版的后半部分，逐漸將第一個模版參數(shù)解析出來。

tuple中的成員函數(shù)
head()可以返回第一個元素的值。
tail()可以返回父類成分起點，返回類型是父類的類型，但實際上是自己對象，而由于類型指定，實際返回的就是父類對象了。

TypeTraits

GNU 2.9版本
struct __true_type{};
struct __false_type{};
//泛化
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;
}

在GNU2.9版本中，其實typeTraits實際是依靠模版的泛化和特化的版本來讓不同的類型進入不同的代碼塊中的。代碼塊中實際也就是一些typedef，這些typedef，實際就標注了，是否有默認的構(gòu)造函數(shù)，拷貝構(gòu)造，賦值構(gòu)造，析構(gòu)函數(shù)等具體類型的情況。這個版本的type traits 來說，需要使用者自己特化一個自己類型的type traits ，實際來說實用性不高。

從C++2.0 開始，type traits的復(fù)雜程度大幅上升。

C++11 之后type_traits所提供的查詢的項目

對于C++11的改版后的最大的便利就是不需要在重新定義特化版本的type_traits，系統(tǒng)都能夠自動得到具體的屬性特征

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

type_traits的實現(xiàn)
- 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 {}

關(guān)于去除const和volatile都是通過模版的泛化和特化組合來實現(xiàn)的
同時，是否是void的類型，也是通過模版的泛化和特化的方式來區(qū)分出來不同的類型

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{};

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)的內(nèi)容，實際實現(xiàn)應(yīng)該是調(diào)用了編譯器的底層的函數(shù)

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>{};

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;

moveable元素對于容器影響

moveable是C++11之后推出的功能

對vector的影響

對于插入300萬個數(shù)據(jù)，vector會牽扯到多次擴容，所以在搬動數(shù)據(jù)的過程中，需要調(diào)用copy Constructer或move Constructer。
有圖上可以知道，有move Constructer的結(jié)果會更快。

對list的影響

對于沒有太多將數(shù)據(jù)搬移的list來說，有沒有move Constructer的效率差別不大

定義一個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);
        }
        reutrn *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
    vitrual ~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()));}
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

(Boolan) C++ STL與泛型編程

(Boolan) C++ STL與泛型編程

一個萬用的hash function

tuple

TypeTraits

cout

moveable元素對于容器影響

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

(Boolan) C++ STL與泛型編程

一個萬用的hash function

tuple

TypeTraits

cout

moveable元素對于容器影響

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av