(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())); }
}
}