STL与泛型编程 week 5 (Boolan)

一个万用的Hash Function

目标: 为Customer写一个CustomerHash, 使我们在用Customer的unodered_set时得以提供自定义的hash functor.

struct Customer {
  string fname; // first name
  string lname; // last name
  long no;
};
class CustomerHash {
 public:
  std::size_t operator()(const Customer &c) const {
    return ...;
  }
};
unordered_set<Customer, CustomerHash> custset;

CustomerHash的实现:

// STEP 4:
// from boost (functional/hash)
template <typename T>
inline void hash_combine (size_t &seed, const T &val)
{
  seed ^= hash<T>()(val) +
          0x9e3779b9 +
          (seed<<6) +
          (seed>>2);
}

// STEP 3:
// auxiliary generic functions to create a hash value using a seed
template <typename T>
inline void hash_val (size_t &seed, const T& val)
{
  hash_combine(seed, val);
}

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

// STEP 1:
// auxiliary generic function
template <typename... Types>
inline size_t hash_val (const Type&... args)
{
  size_t seed = 0;
  hash_val(seed, args...);
  return seed;
}

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

以struct hash特化形式实现Hash Function

课件上的一个简单例子

class MyString {
 private:
  char* _data;
  size_t _len;
// ... 
};

namespace std // 必须放在std内
{
template<>
struct hash<MyString> 为了unordered containers
{
  size_t operator()(const MyString &s) const noexcept
  { return hash<string>()(string(s.get())); }  // 借用hash<string>
};
}

关于hash的特话(摘自C++ Primer):

In addition to specializing function templates, we can also specialize class templates. As an example, we’ll define a specialization of the library hash template that we can use to store Sales_data objects in an unordered container. By default, the unordered containers use hash<key_type> to organize their elements. To use this default with our own data type, we must define a specialization of the hash template. A specialized hash class must define

  • An overloaded call operator that returns a size_t and takes an object of the container’s key type
  • Two type members, result_type and argument_type, which are the return and argument types, respectively, of the call operator
  • The default constructor and a copy-assignment operator (which can be implicitly defined).

The only complication in defining this hash specialization is that when we specialize a template, we must do so in the same namespace in which the original template is defined.

评论: C++ Primer的描述与课件基本一致, 不同点在于书中要求必须在hash的特化版本中定义result_typeargument_type. 详见另一个更复杂的例子(摘自C++ Primer):

// open the std namespace so we can specialize std::hash
namespace std {
template <>           // we're defining a specialization with
struct hash<Sales_data> // the template parameter of Sales_data
{
    // the type used to hash an unordered container 
    // must define these types
    typedef size_t result_type;
    typedef Sales_data argument_type; // by default, this type needs ==
    size_t operator()(const Sales_data& s) const;
    // our class uses synthesized copy control and default constructor
};
size_t hash<Sales_data>::operator()(const Sales_data& s) const
{
    return hash<string>()(s.bookNo) ^
           hash<unsigned>()(s.units_sold) ^
           hash<double>()(s.revenue);
}
} // close the std namespace; note: no semicolon after the close curly

tuple, 用例

// tuples
// create a four-element tuple
// - elements are initialized with default value 
// (0 for fundamental types)
tuple<string, int, int, complex<double>> t;
cout << "sizeof = " << sizeof(t) << endl;

// create and initialize a tuple explicitly
tuple<int, float, string> t1(41, 6.3, "nico");
// iterate over elements:
cout << "t1: " << get<0>(t1) << ' ' 
     << get<1>(t1)  << ' '
     << get<2>(t1)  << endl; 

关于tuple (摘自C++ Primer):

A tuple is a template that is similar to a pair. Each pair type has different types for its members, but every pair always has exactly two members. A tuple also has members whose types vary from one tuple type to another, but a tuple can have any number of members. Each distinct tuple type has a fixed number of members, but the number of members in one tuple type can differ from the number of members in another.
A tuple is most useful when we want to combine some data into a single object but do not want to bother to define a data structure to represent those data. The Table lists the operations that tuples support. The tuple type, along with its companion types and functions, are defined in the tuple header.

Operations on tuples

type traits (G2.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;  // Plain Old Data
};

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;  // Plain Old Data
};

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;  // Plain Old Data
};

__type_traits在SGI STL中的应用很广. 这里给出一个例子(摘自 STL源码剖析):
uninitialized_fill_n() 全局函数:

template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first,
         Size n, const T &x) {
  return __unitialized_fill_n(first, n, x, value_type(first));
}

该函数以x为蓝本, 自迭代器first开始构造n个元素. 为取得最大效率, 首先以value_type()萃取出迭代器first的value type, 再利用__type_traits 判断该类型是否为POD类别:

template <class ForwardIterator, class Size, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first,
         Size n, const T &x, T1*)
{
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(frist, n, x, is_POD());
}

以下就"是否为POD类别"采取最适当的措施:

// 如果不是POD型别, 就会派送(dispatch)到这里
template <class ForwardIterator, class Size, class T>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T &x, __false_type) {
  ForwardIterator cur = first;
  for (; n > 0; --n, ++cur) construct(&*cur x);
  return cur;
}

// 如果是POD型别, 就会派送(dispatch)到这里.
template <class ForwardIterator, class Size, class T>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T &x, __true_type) {
  return fill_n(first, n, x);  // 交由高阶函数执行
}

type traits (since C++11)

tt1.png
tt2.png

关于type traits (摘自 The C++ Programming Language):

In <type_traits> , the standard library provides type functions to determine properties of types and to generate new types from existing ones. These type functions are primarily used at compile time to support simple, and not so simple, metaprogramming.

type traits, 实现is_void

/// remove_const
template <typename _Tp>
  struct remove_const 
  { typedef _Tp type; };

template <typename _Tp>
  struct remove_const <_Tp const>
  { typedef _Tp type; };

/// remove_volatile
template <typename _Tp>
  struct remove_volatile 
  { typedef _Tp type; };

template <typename _Tp>
  struct remove_volatile <_Tp volatile>
  { typedef _Tp type; };

/// remove_cv
template <typename _Tp>
  struct remove_cv
  {
    typedef typename
    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
{};

type traits, 实现is_integral

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

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

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

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

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

Move Constructor & Move Assignment

move1.png
move2.png

摘自C++ Primer

Like the string class (and other library classes), our own classes can benefit from being able to be moved as well as copied. To enable move operations for our own types, we define a move constructor and a move-assignment operator. These members are similar to the corresponding copy operations, but they “steal” resources from their given object rather than copy them.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容