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_type和argument_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.