Hello everyone!
Last time, Senior Liu Qiang led us to learn about
the content related to C++ templates
Learning Experience | C++ Templates
Click to review the wonderful content of the last issue
I believe everyone has benefited greatly from it
The editor is no exception
This time, the senior will bring us knowledge about
type traits.
Now, let’s briefly explain
The main content of this article
1. What are type traits
2. Template specialization
3. Code implementation of type traits (application of template specialization)
In C++, we usually extract types through typeid (a function), but it can only obtain the type and cannot be used to declare variables, hence the concept of type traits emerged to accomplish this function.
POD Type Traits
Plain old data — basic types refer to types that are compatible with C in C++, which can be processed in the same way as C language.
In simple terms, it helps us differentiate the types we want to separate, such as built-in types and custom types; for example, when expanding a sequential list and encountering copy issues, if it is a built-in type, we can use memcpy, but if it is a custom type, it will be problematic;
For example, the following code:
template<typename T>
void Seqlist<T>:: CheckCapacity()// Function to expand the sequential list;
{
if(_size == capacity)
{
int NewCapacity = capacity*2 + 3;
T* tmp = new T[NewCapacity];
memcpy(tmp,_pdata,capacity*sizeof(T));// Assuming the original sequential list space is represented by _pdata;
delete _pdata;
_pdata = tmp;
capacity = NewCapacity;// Remember to update the capacity;
}
}If the template parameter is a built-in type, applying it to the sequence is not a problem, but what if the template parameter is of string type? You can try it out.
This blog will post the complete code after type traits
Now, a knowledge point needs to be inserted here
The storage issue of string type strings in memory We know that in the library the string object has two members _buf and _ptr; what are these two members used for? _buf has a default space of 16 bytes, when the string length is less than 16, it is generally stored in _buf, and when the string length is longer, we generally use _ptr, which is a pointer that can point to the space of this string, thus allowing our string class to use these four bytes of space to store the address of the string; however, we used memcpy function to perform the copy
memcpy is a memory copy, it directly copies memory, thus _ptr undergoes a copy, and then the original _ptr is released; is there a problem? After memcpy, both _ptr point to the same memory space; without a reference counter, if you release one _ptr, it will naturally lead to problems! This is equivalent to a shallow copy issue! Now we need to solve this problem, thus we have the following writing:
template<typename T>
void Seqlist<T>:: CheckCapacity()// Function to expand the sequential list;
{
if(_size == capacity)
{
int NewCapacity = capacity*2 + 3;
T* tmp = new T[NewCapacity];
//memcpy(tmp,_pdata,capacity*sizeof(T));// Assuming the original sequential list space is represented by _pdata;
for(int i = 0; i<_size; i++)
{
tmp[i] = _pdata[i];// Note, here we are using the assignment operator;
}
delete _pdata;
_pdata = tmp;
capacity = NewCapacity;// Remember to update the capacity;
}
}Upon seeing the code above, students may wonder what the difference is?
Looking closely, when we use a loop to solve this problem, the internal loop is _tmp[i]= _pdata[i]; here we are calling the member assignment operator, if it is a member of the string class, we will call the assignment operator of the string class; and our library’s string class has already solved this problem, if you have implemented the string class, you must remember, so I will not simulate the implementation of the string class here;
At this point, do you feel a bit off-topic? Not yet, now you see that we used a for loop to solve the copy problem for custom types, but if the template parameter is a built-in type, wouldn’t memcpy be more efficient?
Next, we need to solve the problem: if the passed template parameter is a built-in type, call memcpy; if the passed parameter is a custom type, call the loop?
Here we need to introduce the content of our templates—– specialization of class templates
What is class template specialization
Special handling of template parameters based on templates, divided into full specialization and partial specialization
For example:
// Full specialization
template<typename T>
class Seqlist<int>
{
public:
void PopBack();
void PopFront();
};
// Member functions after specialization do not need template parameters
void Seqlist<int>::PopBack()
{}
// Partial specialization
template<typename T,typename T>
class Date<T,int> // Similar usage to full specialization
{};Partial specialization does not necessarily specialize just one parameter,
but is a specialized version designed based on further conditional restrictions on template parameters
For example:
template<typename T,typename T>
class Date<T*, T*>
{};
template<typename T, typename T>
class Date<T&,T>
{};Having roughly understood what template specialization is, many students may be confused about what this specialization does?
This brings us back to the initial question, how to distinguish between built-in types and custom types while solving the sequential list expansion problem mentioned earlier
Now we will use type traits to implement the expansion of the sequential list:
// Template implementation of the sequential list;
#include<iostream>
#include<string>
#include<cassert>
using namespace std;
struct __TrueType
{
bool Get ()
{
return true ;
}
};
struct __FalseType
{
bool Get ()
{
return false ;
}
};
// Custom types are generally not specialized
template <class _T>
struct TypeTraits
{
typedef __FalseType __IsPODType;
};
// Below is the specialization for several common built-in types, of course, there are many built-in types, I am just giving a few common ones;
template<>
struct TypeTraits< bool>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< char>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< short>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< int>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< long>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< unsigned long long>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< float>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< double>
{
typedef __TrueType __IsPODType;
};
// Next is how to use it
template<typename T>
void Seqlist<T>:: CheckCapacity()// Function to expand the sequential list;
{
if(_size == capacity)
{
int NewCapacity = capacity*2 + 3;
T* tmp = new T[NewCapacity];
if(TypeTraits<T>::__IsPODType.get())// Determine return value
{
memcpy(tmp,_pdata,capacity*sizeof(T));
}// Assuming the original sequential list space is represented by _pdata;
else
{
for(int i = 0; i<_size; i++)
{
tmp[i] = _pdata[i];// Note, here we are using the assignment operator;
}
}
delete _pdata;
_pdata = tmp;
capacity = NewCapacity;// Remember to update the capacity;
}
}Thus, we have solved the previous problem
Finally, here is the complete code!
#include<iostream>
#include<string>
#include<cassert>
using namespace std;
struct __TrueType
{
bool Get ()
{
return true ;
}
};
struct __FalseType
{
bool Get ()
{
return false ;
}
};
// Custom types are generally not specialized
template <class _T>
struct TypeTraits
{
typedef __FalseType __IsPODType;
};
// Below is the specialization for several common built-in types, of course, there are many built-in types, I am just giving a few common ones;
template<>
struct TypeTraits< bool>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< char>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< short>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< int>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< long>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< unsigned long long>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< float>
{
typedef __TrueType __IsPODType;
};
template<>
struct TypeTraits< double>
{
typedef __TrueType __IsPODType;
};
template<typename T>
class SeqList
{
public:
SeqList ()
:_pdata(NULL)
,_size(0)
,_capacity(3)
{
_pdata = new T[3];
}
~SeqList ()
{
if(_pdata != NULL)
{
delete[] _pdata;
_size = 0;
_capacity = 0;
}
}
template<typename T>
friend ostream& operator<<(ostream& os, const SeqList<T>& s);
void Display()
{
for(int i = 0; i<_size; i++)
{
cout<<_pdata[i]<<" ";
}
cout<<endl;
}
void PushBack(const T& data);
void PushFront(const T& data);
void PopBack();
void PopFront();
void Sort();
int Find(const T& P);
void Intsert(const int& pos,const T& data);
void Remove(const T& data);
void RemoveAll(const T& data);
T& operator[](int size)
{
assert(size<_size);
assert(size>=0);
return _pdata[size];
}
private :
void CheckCapacity()// Function to expand the sequential list;
{
if(_size == capacity)
{
int NewCapacity = capacity*2 + 3;
T* tmp = new T[NewCapacity];
if(TypeTraits<T>::__IsPODType.get())// Determine return value
{
memcpy(tmp,_pdata,capacity*sizeof(T));
}// Assuming the original sequential list space is represented by _pdata;
else
{
for(int i = 0; i<_size; i++)
{
tmp[i] = _pdata[i];// Note, here we are using the assignment operator;
}
}
delete _pdata;
_pdata = tmp;
capacity = NewCapacity;// Remember to update the capacity;
}
}
T* _pdata;
int _size;
int _capacity;
};
template<typename T>
ostream& operator<<(ostream& os, const SeqList <T>& s )
{
int i = 0;
for(i = 0; i< s._size ;i++)
{
os<<s._pdata [i]<<" ";
}
return os;
}
template<typename T>
int SeqList<T>::Find(const T& data)
{
int i = 0;
for(i= 0 ; i < _sz; i++)
{
if(_pdata[i] == data)// Note here the equal sign, be careful not to write it as an assignment;
return i;
}
return -1;
}
template<typename T>
void SeqList<T>:: PushBack(const T& data)
{
CheckCapacity ();
_pdata[_size] = data;
_size++;
}
template<class T>
void SeqList<T>::PushFront(const T& data)
{
CheckCapacity();
int length = _size;
while(length)
{
_pdata[length]=_pdata[length-1];
length--;
}
_pdata[0] = data;
_size++;
}
template<typename T>
void SeqList<T>::PopBack ()
{
if(_size>=1)
{
_size-=1;
}
}
template<typename T>
void SeqList<T>::PopFront()
{
int len = 0;
while(len<_size-1)
{
_pdata[len] = _pdata[len+1];
len++;
}
_size--;
}
template<typename T>
void SeqList<T>::Intsert(const int& pos, const T& data)
{
CheckCapacity ();
int index = Find(pos);
if(index>=0)
{
int length = _size;
while(length > index)
{
_pdata[length]=_pdata[length-1];
length--;
}
_pdata[index] = data;
_size++;
}
}
template<typename T>
void SeqList<T>::Remove(const T& data)
{
int index = Find(data);
if(index>=0)
{
while(index<_size-1)
{
_pdata[index] = _pdata[index+1];
index++;
}
}
_size--;
}
template<typename T>
void SeqList<T>::RemoveAll (const T& data)
{
while(Find(data)>=0)
{
Remove(data);
}
}
template<typename T>
void SeqList<T>::Sort ()
{
for(int i = 0; i<_size-1; i++)
{
for(int j = 0; j < _size-i-1; j++)
{
if(_pdata[j]<_pdata[j+1])
{
T tmp = _pdata [j];
_pdata [j] = _pdata [j+1];
_pdata [j+1] = tmp;
}
}
}
}
void test()
{
SeqList<string> s;
SeqList<int> s1;
s1.PushBack(2);
s1.PushBack(5);
s1.PushBack(4);
s1.PushBack(6);
s.PushBack ("aaaaaaaaaaaaaa");
s.PushBack ("dsadsas");
s.PushBack ("ssssssssssss");
s.PushBack ("sdasadadafffffffffffffffffffffffffffffffffff");
s.PushBack ("sdasdas");
s1.Sort ();
//s1.Display ();
cout<<s1<<endl;
}
int main()
{
test();
system("pause");
return 0;
}
Review of previous wonderful issues
Learning Experience | C++ Templates
How to Learn C Language Well
English Learning | Cure Your English Difficulties
“Imposter Boss” Takes You into the World of Sequences
Text: Liu Qiang
Editor: Jiang Keyu, Liu Baohui
Advisors: Li Ying, Yu Jie
