STL source code analysis -- traits

More interesting content, please pay attention to WeChat official account: backend technology hut.

Traits is a special programming technique in C + +. It is one of the most direct use cases of template meta programming. Through traits, you can extract various attributes of template input parameter types. Next, we give examples of the most common traits in STL.

1 __type_traits: trivial judgment

__ type_traits is used to determine whether the type is trival.

1.1 why should trivial type be determined

If a type is trivial, it can be initialized statically. Memcpy can be used to copy data directly instead of the copy constructor. Its lifetime begins when its object store is defined without waiting for the constructor to complete. When executing ctor, copy, move, assign and ctor, the most efficient method can be adopted: instead of automatically generating ctor, copy, assign and ctor by the compiler, malloc, free and memcpy are replaced.

Take chestnuts for example:_ Destroy is used to destroy all objects in the container iterator interval [_first, _last).
The call chain is as follows:

_Destroy
  -> __destroy
    -> __destroy_aux

In terms of implementation,

_ destory first uses__ VALUE_TYPE gets the pointer type pointing to the object in the container and passes its instance into the container as an input parameter__ Destruction.
In__ In destruction, use__ type_ traits<_ Tp>::has_ trivial_ Destructor determines whether the object type in the container is trival, and calls__ destroy_aux.
__ destroy_aux function according to_ Whether Tp implements two different versions for trivial. In the trivial version, nothing is done because the trivial type does not explicitly define a destructor. In a non trivial function, you must call_ Destructor of Tp.

We note that it is used here__ type_traits are used to identify_ Is Tp type trivial

template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
  for ( ; __first != __last; ++__first)
    destroy(&*__first);
}

template <class _ForwardIterator> 
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

template <class _ForwardIterator, class _Tp>
inline void 
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
  typedef typename __type_traits<_Tp>::has_trivial_destructor
          _Trivial_destructor;
  __destroy_aux(__first, __last, _Trivial_destructor());
}

template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
  __destroy(__first, __last, __VALUE_TYPE(__first));
}

1.2 definition of trivial type

Maybe your question is, what kind of type can be called trivial?

If a type meets at least one of the following conditions, it is called non trival；Otherwise, it is called trival
1. Constructors are explicitly defined(ctor), copy constructor (copy), move constructor (move)，Assignment Operators (assign), Or destructor(ctor)Any one of them.
2. Class has non POD Type member
3. Virtual function
4. Virtual base class

Here you may have more questions. What is the type of POD?

POD = Plain Old Data 
According to Wikipedia, POD Types include scalar types and POD Class type. POD In source code compatible with ANSI C It's very important when it comes to. POD Object and C The corresponding objects of language have some common characteristics, including initialization, replication, memory layout, addressing and so on.

Scalar types include:
1. arithmetic types (integer/floating-point/character/Boolean)
2. Enumeration type
3. Pointer type(Null pointer/Object pointer/Function pointer)
4. Pointer to member type(for example T C::* Pointing class C The type of is T Pointer to the data member of the)

POD Class types are aggregate classes(adopt struct/union polymerization)Or array, and does not have the following members:
1. Pointer to non static data member of member type
2. wrong POD Non static data member of type
3. Non static data member of reference type
4. Explicitly defined copy and assignment operators
5. Explicitly defined destructor
6. Private if it is an aggregate class and contains an explicitly defined constructor/Protected non static member function, base class, virtual function 
To sum up, the aggregate that does not meet the above 6 items/Array can be called POD Class type.

1.3 implementation of trival type determination

In the implementation, first define the general template class__ type_traits. All calculations here are type based, so use__ true_type and__ false_type indicates logical true / false type respectively.

As you can see from the code, by default_ The default constructor, copy constructor, assignment operator and destructor in Tp are not trivial_ Tp is also not a POD type.

template <class _Tp>
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;
};

struct __true_type {
};

struct __false_type {
};

Second, for all scalar types, a specialized template class is defined__ type_traits. Because of the scalar type, there is no default construct / copy construct / copy operator / destructor defined. The scalar type also belongs to POD type. Scalar types include:

bool
char
signed char
unsigned char
wchar_t
short
unsigned short
int
unsigned int
long
unsigned long
unsigned long long
float
double
long double
Tp*
char*
signed char*
unsigned char*,
const char*
const signed char*
const unsigned char*

2 _Is_integer: integer determination

_ Is_integer is used to determine whether the type is an integer type

2.1 why is integer determination necessary

For example: if the element type in the vector_ Tp is an integer type. In this case, if the integer type is not partitioned, the compiler cannot distinguish vector < int > A (10, 1); The first constructor or the second constructor in the following code should be used because_ InputIterator is just a template parameter, which can be a real iterator type or any other type.

In order not to make the compiler difficult, we need to decide during compilation_ Whether InputIterator is of integer type. It's used here_ Is_integer, which determines_ InputIterator type and returns__ true_type or__ false_type. Corresponding_ M_initialize_aux for_ Whether InputIterator is a shaper or not is also implemented in two versions. Finally, the vector structure maintains its own semantics in two different cases:

Semantic 1: specify the number and initial value of elements and construct vector
Semantic 2: specify the start iterator and end iterator, and construct the vector

  // Constructor 1
  vector(size_type __n, const _Tp& __value,
         const allocator_type& __a = allocator_type()) 
    : _Base(__n, __a)
    { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
    
  // Constructor 2
  // Check whether it's an integral type.  If so, it's not an iterator.
  template <class _InputIterator>
  vector(_InputIterator __first, _InputIterator __last,
         const allocator_type& __a = allocator_type()) : _Base(__a) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_initialize_aux(__first, __last, _Integral());
  }

2.2 implementation of integer determination

First, define the template, general function_ Is_integer. By default, all types are not integers.

template <class _Tp> struct _Is_integer {
  typedef __false_type _Integral;
};

Secondly, define the specialized template function_ Is_integer, for the following types_ Integral is__ true_type.

bool
char
signed char
unsigned char
wchar_t
short
unsigned short
int
unsigned int
long
unsigned long
long long
unsigned long long

PS: there are far more than the above two traits in STL, for example__ char_ Traits (see STL source code analysis -- string ),iterator_ Traits (see STL source code analysis -- iterator ),_ Alloc_ Traits (see STL source code analysis -- memory allocator )Here, the reader is left to analyze it by himself

More interesting content, please pay attention to WeChat official account: Wukong said

Programs Wiki