關于STL的話題已經(jīng)探討了好幾個篇了磷蛹，今天來討論一下剩下的一些內(nèi)容吧
一個萬用的hash function
使用以Hash Table為底層的容器，比如unordered_map（hash_map）逛腿，在使用個過程中，需要有計算hash code的方法來計算出元素在hashtable中的具體位置。
那么對于自定義類型來說葵孤，需要指定對應的Hash Function鼻由，只有這樣才能在使用的過程暇榴，系統(tǒng)找到對應元素應該插入的位置，以便系統(tǒng)自動管理我們需要插入到容器中的各個元素蕉世。關于這個函數(shù)該如何定義蔼紧，對于不同個自定義類型來說并不相同，也沒有辦法找到一個通用的方式狠轻，畢竟石頭類和動物類奸例，他們各自的hash function多少會有些區(qū)別吧，具體的定義哈误，還需要依靠開發(fā)這自己了哩至。
那么躏嚎，為什么后還會有關于個萬用的hash function呢？關于這個問題菩貌，先放下不說卢佣，咱們先來看看關于指定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ù)嘹叫，就是對應的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ù)指針的方式來通知容器诈乒，對于這個自定義類到底應該使用哪個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的重復概率比較高泡挺，因為只是簡單的相累加嘛辈讶。而重復的hash code 會導致“bucket”中的元素過多，影響查詢的效率
其實在*** C++ TR1 ***的版本后娄猫，STL為我么提供了一套萬用的Hash Function贱除。那么應該如何使用呢？咱們就先來看看吧媳溺。
//使用萬能的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ù)的類型都會不同昵观，那么應該處理每個不同的參數(shù)需要一套對應的解決方案
其實上面的代碼就是這套方案的解法，其實對于函數(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)自動類型推到
//實際的類型應該為: 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可以自動幫我們將多個參數(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的復雜程度大幅上升鳄厌。
對于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 {}
關于去除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)應該是調(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()));}
}
}
