C++模板以及實(shí)現(xiàn)vector實(shí)例詳解

更新時(shí)間：2021年11月17日 10:00:41 作者：~怎么回事啊~

模板是為了實(shí)現(xiàn)泛型編程,所謂泛型編程,就是指編寫與類型無(wú)關(guān)的代碼,下面這篇文章主要給大家介紹了關(guān)于C++模板以及實(shí)現(xiàn)vector的相關(guān)資料,需要的朋友可以參考下

函數(shù)模板

函數(shù)模板：是不進(jìn)行編譯的，因?yàn)轭愋瓦€不知道

模板的實(shí)例化：函數(shù)調(diào)用點(diǎn)進(jìn)行實(shí)例化

模板函數(shù)：才是要被編譯器所編譯的

模板類型參數(shù)：typyname/class

模板非類型參數(shù)：模板非類型形參的詳細(xì)闡述

模板的實(shí)參推演:可以根據(jù)用戶傳入的實(shí)參的類型，來(lái)推導(dǎo)出模板類型參數(shù)的具體

模板的特例化（專用化）的實(shí)例化

模板函數(shù)、模板的特例化和非模板函數(shù)的重載關(guān)系：候選的函數(shù)中，優(yōu)先在精確匹配中選擇，優(yōu)先選擇普通函數(shù)，特例性更強(qiáng)的模版函數(shù)次之，然后是模版函數(shù)的特化版本，最后才是泛化版本。

模板代碼是不能聲明在.h，實(shí)現(xiàn)在.cpp，模板代碼調(diào)用之前，一定要看到模板定義的地方，這樣的話，模板才能夠正常的實(shí)例化，產(chǎn)生能夠被編譯器編譯的代碼。模板代碼都是放在頭文件中，然后在源文件中直接進(jìn)行#include

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
 
//函數(shù)模板
template<typename T> //定義一個(gè)模板參數(shù)列表
bool compare(T a, T b) {//compare 是一個(gè)函數(shù)模板
  std::cout << "template compare\n";
  return a > b;
}
/*
  在函數(shù)調(diào)用點(diǎn)，編譯器用用戶指定的類型，從原模板實(shí)例化一份函數(shù)代碼出來(lái)：
  模板函數(shù)：
bool compare<int>(int a, int b) {
  return a > b;
}
bool compare<double>(double a, double b) {
  return a > b;
}
*/
 
//模板特例化： 針對(duì)compare函數(shù)模板，提供const char * 類型的特例化版本
template<>
bool compare<const char *>(const char* a, const char * b) {
  std::cout << "const char * compare\n";
  return strcmp(a, b) > 0;
}
 
//非模板函數(shù)，普通函數(shù)
bool compare(const char* a, const char * b) {
  std::cout << "normal compare\n";
  return strcmp(a, b) > 0;
}
 
int main()
{
  std::cout << compare<int>(1, 2) << std::endl;
  std::cout << compare<double>(1, 2) << std::endl;
  std::cout << compare(1, 2) << std::endl;//模板的實(shí)參推演 可以根據(jù)用戶傳入的實(shí)參的類型，來(lái)推導(dǎo)模板類型參數(shù)
  //編譯器優(yōu)先把compare處理成函數(shù)名，沒有的話，才去找compare模板
  std::cout << compare("a", "b") << std::endl;//
  return 0;
}

類模板

實(shí)現(xiàn)一個(gè)順序棧

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
 
template<typename T>
class  SeqStack
{
public:
  //構(gòu)造和析構(gòu)函數(shù)名不加<T> 其他出現(xiàn)模板的地方都加上類型參數(shù)列表
  SeqStack(int size = 10)
    :pstack_(new T[size])
  ,top_(0)
  ,size_(size){
    //初始化生成的指令更少，效率更高。僅調(diào)用默認(rèn)構(gòu)造函數(shù)（如果存在類成員）。賦值需要調(diào)用默認(rèn)構(gòu)造函數(shù)和賦值運(yùn)算符
  }
  ~SeqStack() {
    if (pstack_) {
      delete[] pstack_;
      pstack_ = nullptr;
    }
  }
 
  SeqStack(const SeqStack<T>& stack)
    :top_(stack.top_),
    size_(stack.size_){
    pstack_ = new T[stack.size_];
    for (int i = 0; i < top_; ++i) {
      pstack_[i] = stack.pstack_[i];
    }
  }
  SeqStack<T>& operator=(const  SeqStack<T>&stack) {
    if (this == &stack) {
      return *this;
    }
 
    delete[] pstack_;
 
    top_ = stack.top_;
    size_ = stack.size_;
    pstack_ = new T[stack.size_];
    for (int i = 0; i < top_; ++i) {
      pstack_[i] = stack.pstack_[i];
    }
 
  }
 
  void push(const T& val) {
    if (full()) {
      resize();
    }
    pstack_[top_] = val;
    top_++;
  }
  void pop() {
    if (empty()) {
      return;
    }
    top_--;
  }
  T top() const {
    if (empty()) {
      throw "stack is empty";
    }
    return pstack_[top_-1];
  }
  bool full() const {
    return top_ == size_;
  }
  bool empty() const {
    return top_ == 0;
  }
protected:
 
 
private:
  void resize() {
    T * p = new T[size_ * 2];
    for (int i = 0; i < top_; ++i) {
      p[i] = pstack_[i];
    }
 
    size_ *= 2;
    delete pstack_;
    pstack_ = p;
  }
 
  T * pstack_;
  int top_;
  int size_;
};
 
int main()
{
  SeqStack<int> stack;
  for (int i = 0; i < 8; ++i) {
    stack.push(i);
  }
 
  while (!stack.empty())
  {
    std::cout << stack.top() << " ";
    stack.pop();
  }
  return 0;
}

Vector實(shí)現(xiàn)

vector 的本質(zhì)是一個(gè)數(shù)組，在vector 中需要有三個(gè)指針：

_first :指向數(shù)組的起始位置

_last:指向已經(jīng)存放的最后一個(gè)元素的下一個(gè)位置

_end:指向數(shù)組長(zhǎng)度的末尾元素的下一個(gè)位置。

數(shù)組的容量=_end-_first

數(shù)組中存放的元素個(gè)數(shù)=_last-_first

數(shù)組是否為空:_first == _last

數(shù)組是否已滿：_last == _end

簡(jiǎn)單的類模板實(shí)現(xiàn)代碼及測(cè)試：

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
 
template<typename T>
class vector
{
public:
  vector(int size = 10)
  {
    _first = new T[size];
    _last = _first;
    _end = _first + size;
  }
  ~vector()
  {
    delete[]_first;
    _first = _end = _last = nullptr;
  }
  vector(const vector<T>& rhs)
  {
    int size = rhs._end - rhs._first;
    _first = new T[size];
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _first[i] = rhs._first[i];
    }
    _last = _first + len;
    _end = _first + size;
  }
  vector<T>& operator=(const vector<T>& rhs)
  {
    if (this == &rhs)
      return *this;
 
    delete[]_first;
 
 
    int size = rhs._end - rhs._first;
    _first = new T[size];
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _first[i] = rhs._first[i];
    }
    _last = _first + len;
    _end = _first + size;
    return *this;
  }
  void push_back(const T& val) // 向容器末尾添加元素
  {
    if (full())
      expand();
    *_last++ = val;
  }
  void pop_back() // 從容器末尾刪除元素
  {
    if (empty())
      return;
    --_last;
  }
  T back()const // 返回容器末尾的元素的值
  {
    return *(_last - 1);
  }
  bool full()const { return _last == _end; }
  bool empty()const { return _first == _last; }
  int size()const { return _last - _first; }
private:
  T* _first; // 指向數(shù)組起始的位置
  T* _last;  // 指向數(shù)組中有效元素的后繼位置
  T* _end;   // 指向數(shù)組空間的后繼位置
 
  void expand() // 容器的二倍擴(kuò)容
  {
    int size = _end - _first;
    T *ptmp = new T[2 * size];
    for (int i = 0; i < size; ++i)
    {
      ptmp[i] = _first[i];
    }
    delete[]_first;
    _first = ptmp;
    _last = _first + size;
    _end = _first + 2 * size;
  }
};
 
 
class Test
{
public:
  Test() { std::cout << "Test()" << std::endl; }
  Test& operator=(const Test&t) { std::cout << "operator=" << std::endl; return *this; }
  ~Test() { std::cout << "~Test()" << std::endl; }
  Test(const Test&) { std::cout << "Test(const Test&)" << std::endl; }
};
 
 
int main()
{
  Test t1, t2;
  std::cout << "vector<Test> vec" << std::endl;
  vector<Test> vec;
  std::cout << "vector<Test> vec; push_back" << std::endl;
 
  vec.push_back(t1);
  vec.push_back(t2);
 
  std::cout << "vector<Test> vec; pop_back" << std::endl;
  vec.pop_back();
  return 0;
}

問題：在我們實(shí)現(xiàn)的vector構(gòu)造函數(shù)中，使用new T[size] ：它做了兩件事情

（1）開辟內(nèi)存空間

（2）調(diào)用T類型的默認(rèn)構(gòu)造函數(shù)構(gòu)造對(duì)象

其中第二步是一種浪費(fèi)，因?yàn)槲疫€沒在vector 添加元素，提前構(gòu)造一遍對(duì)象然后在析構(gòu)時(shí)候是否純屬多余。

同時(shí)：在實(shí)現(xiàn)pop_back(）時(shí)，存在內(nèi)存泄漏

  void pop_back() // 從容器末尾刪除元素
  {
    if (empty())
      return;
    --_last;
  }

僅僅將_last指針 --，并沒有釋放Test申請(qǐng)的資源。需要調(diào)用對(duì)象的析構(gòu)函數(shù)

win msvc編譯器的實(shí)現(xiàn)：

 
		// CLASS TEMPLATE vector
template<class _Ty,
	class _Alloc = allocator<_Ty>>
	class vector
		: public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>
	{	// varying size array of values
private:
	using _Mybase = _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>;
	using _Alty = typename _Mybase::_Alty;
	using _Alty_traits = typename _Mybase::_Alty_traits;
......

系統(tǒng)的實(shí)現(xiàn)，除了數(shù)據(jù)類型外，還有一個(gè)allocator,它將開辟空間和構(gòu)造對(duì)象分離開。

而這，也就是空間配置器做的工作；

容器的空間配置器

空間配置器主要有四個(gè)功能：

內(nèi)存開辟 allocate（底層調(diào)用malloc）；
內(nèi)存釋放 deallocate（底層調(diào)用free）；
對(duì)象構(gòu)造 construct（調(diào)用構(gòu)造函數(shù)）；
對(duì)象析構(gòu) destroy（調(diào)用析構(gòu)函數(shù)

// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫(kù)的allocator實(shí)現(xiàn)一樣
template<typename T>
struct Allocator
{
	T* allocate(size_t size) // 負(fù)責(zé)內(nèi)存開辟
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void* p) // 負(fù)責(zé)內(nèi)存釋放
	{
		free(p);
	}
	void construct(T* p, const T& val) // 負(fù)責(zé)對(duì)象構(gòu)造
	{
		new (p) T(val); // 定位new
	}
	void destroy(T* p) // 負(fù)責(zé)對(duì)象析構(gòu)
	{
		p->~T(); // ~T()代表了T類型的析構(gòu)函數(shù)
	}
};

修改后的vector

 
#include <iostream>
// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫(kù)的allocator實(shí)現(xiàn)一樣
template<typename T>
class Allocator
{
public:
  T* allocate(size_t size) // 負(fù)責(zé)內(nèi)存開辟
  {
    return (T*)malloc(sizeof(T) * size);
  }
  void deallocate(void* p) // 負(fù)責(zé)內(nèi)存釋放
  {
    free(p);
  }
  void construct(T* p, const T& val) // 負(fù)責(zé)對(duì)象構(gòu)造
  {
    new (p) T(val); // 定位new
  }
  void destroy(T* p) // 負(fù)責(zé)對(duì)象析構(gòu)
  {
    p->~T(); // ~T()代表了T類型的析構(gòu)函數(shù)
  }
};
 
 
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
  vector(int size = 10)
  {
    // 需要把內(nèi)存開辟和對(duì)象構(gòu)造分開處理
    _first = _allocator.allocate(size);
    _last = _first;
    _end = _first + size;
  }
  ~vector()
  {
    // 析構(gòu)容器有效的元素，然后釋放_(tái)first指針指向的堆內(nèi)存
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進(jìn)行析構(gòu)操作
    }
    _allocator.deallocate(_first); // 釋放堆上的數(shù)組內(nèi)存
    _first = _last = _end = nullptr;
  }
  vector(const vector<T>& rhs)
  {
    int size = rhs._end - rhs._first;
    _first = _allocator.allocate(size);
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _allocator.construct(_first + i, rhs._first[i]);
    }
    _last = _first + len;
    _end = _first + size;
  }
  vector<T>& operator=(const vector<T>& rhs)
  {
    if (this == &rhs)
      return *this;
 
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進(jìn)行析構(gòu)操作
    }
    _allocator.deallocate(_first);
 
    int size = rhs._end - rhs._first;
    _first = _allocator.allocate(size);
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _allocator.construct(_first + i, rhs._first[i]);
    }
    _last = _first + len;
    _end = _first + size;
    return *this;
  }
  void push_back(const T& val) // 向容器末尾添加元素
  {
    if (full())
      expand();
 
    _allocator.construct(_last, val);
    _last++;
  }
  void pop_back() // 從容器末尾刪除元素
  {
    if (empty())
      return;
 
    // 不僅要把_last指針--，還需要析構(gòu)刪除的元素
    --_last;
    _allocator.destroy(_last);
  }
  T back()const // 返回容器末尾的元素的值
  {
    return *(_last - 1);
  }
  bool full()const { return _last == _end; }
  bool empty()const { return _first == _last; }
  int size()const { return _last - _first; }
private:
  T* _first; // 指向數(shù)組起始的位置
  T* _last;  // 指向數(shù)組中有效元素的后繼位置
  T* _end;   // 指向數(shù)組空間的后繼位置
  Alloc _allocator; // 定義容器的空間配置器對(duì)象
 
  void expand() // 容器的二倍擴(kuò)容
  {
    int size = _end - _first;
    T* ptmp = _allocator.allocate(2 * size);
    for (int i = 0; i < size; ++i)
    {
      _allocator.construct(ptmp + i, _first[i]);
    }
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p);
    }
    _allocator.deallocate(_first);
    _first = ptmp;
    _last = _first + size;
    _end = _first + 2 * size;
  }
};
 
 
class Test
{
public:
  Test() { std::cout << "Test()" << std::endl; }
  Test& operator=(const Test&t) { std::cout << "operator=" << std::endl; return *this; }
  ~Test() { std::cout << "~Test()" << std::endl; }
  Test(const Test&) { std::cout << "Test(const Test&)" << std::endl; }
};
 
 
int main()
{
  Test t1, t2;
  std::cout << "vector<Test> vec" << std::endl;
  vector<Test> vec;
  std::cout << "vector<Test> vec; push_back" << std::endl;
 
  vec.push_back(t1);
  vec.push_back(t2);
 
  std::cout << "vector<Test> vec; pop_back" << std::endl;
  vec.pop_back();
 
  std::cout << "end" << std::endl;
  return 0;
}

現(xiàn)在的效果就和msvc實(shí)現(xiàn)的vector相同了

運(yùn)算符重載與迭代器實(shí)現(xiàn)

  /************************************************************************/
  /* 
  迭代器一般實(shí)現(xiàn)成容器的嵌套類型
  */
  /************************************************************************/
  class iterator
  {
  public:
    iterator(T*p=nullptr) :_ptr(p) {}
    iterator(const iterator& iter) :_ptr(iter._ptr) {}
    //前置++
    iterator& operator++() {
      _ptr++;
      return *this;
    }
 
    //后置++
    iterator operator++(int) {
      iterator tmp(*this);
      _ptr++;
      return tmp;
    }
 
    //解引用
    T& operator*() {
      return *_ptr;
    }
 
    // !=
    bool operator!=(const iterator& iter)const {
      return _ptr != iter._ptr;
    }
 
  private:
    T * _ptr;
  };
 
  //迭代器方法
  iterator begin() { return iterator(_first); }
  iterator end() { return iterator(_last);}
 
  //運(yùn)算符重載[]
  T& operator[](int index) {
    if (index < 0 || index >= size()) {
      throw "OutofRangeException";
    }
 
    return _first[index];
  }

最終vector的實(shí)現(xiàn)代碼

 
#include <iostream>
// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫(kù)的allocator實(shí)現(xiàn)一樣
template<typename T>
class Allocator
{
public:
  T* allocate(size_t size) // 負(fù)責(zé)內(nèi)存開辟
  {
    return (T*)malloc(sizeof(T) * size);
  }
  void deallocate(void* p) // 負(fù)責(zé)內(nèi)存釋放
  {
    free(p);
  }
  void construct(T* p, const T& val) // 負(fù)責(zé)對(duì)象構(gòu)造
  {
    new (p) T(val); // 定位new
  }
  void destroy(T* p) // 負(fù)責(zé)對(duì)象析構(gòu)
  {
    p->~T(); // ~T()代表了T類型的析構(gòu)函數(shù)
  }
};
 
 
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
  vector(int size = 10)
  {
    // 需要把內(nèi)存開辟和對(duì)象構(gòu)造分開處理
    _first = _allocator.allocate(size);
    _last = _first;
    _end = _first + size;
  }
  ~vector()
  {
    // 析構(gòu)容器有效的元素，然后釋放_(tái)first指針指向的堆內(nèi)存
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進(jìn)行析構(gòu)操作
    }
    _allocator.deallocate(_first); // 釋放堆上的數(shù)組內(nèi)存
    _first = _last = _end = nullptr;
  }
  vector(const vector<T>& rhs)
  {
    int size = rhs._end - rhs._first;
    _first = _allocator.allocate(size);
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _allocator.construct(_first + i, rhs._first[i]);
    }
    _last = _first + len;
    _end = _first + size;
  }
  vector<T>& operator=(const vector<T>& rhs)
  {
    if (this == &rhs)
      return *this;
 
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進(jìn)行析構(gòu)操作
    }
    _allocator.deallocate(_first);
 
    int size = rhs._end - rhs._first;
    _first = _allocator.allocate(size);
    int len = rhs._last - rhs._first;
    for (int i = 0; i < len; ++i)
    {
      _allocator.construct(_first + i, rhs._first[i]);
    }
    _last = _first + len;
    _end = _first + size;
    return *this;
  }
  void push_back(const T& val) // 向容器末尾添加元素
  {
    if (full())
      expand();
 
    _allocator.construct(_last, val);
    _last++;
  }
  void pop_back() // 從容器末尾刪除元素
  {
    if (empty())
      return;
 
    // 不僅要把_last指針--，還需要析構(gòu)刪除的元素
    --_last;
    _allocator.destroy(_last);
  }
  T back()const // 返回容器末尾的元素的值
  {
    return *(_last - 1);
  }
  bool full()const { return _last == _end; }
  bool empty()const { return _first == _last; }
  int size()const { return _last - _first; }
 
  //運(yùn)算符重載[]
  T& operator[](int index) {
    if (index < 0 || index >= size()) {
      throw "OutofRangeException";
    }
 
    return _first[index];
  }
 
  /************************************************************************/
  /* 
  迭代器一般實(shí)現(xiàn)成容器的嵌套類型
  */
  /************************************************************************/
  class iterator
  {
  public:
    iterator(T*p=nullptr) :_ptr(p) {}
    iterator(const iterator& iter) :_ptr(iter._ptr) {}
    //前置++
    iterator& operator++() {
      _ptr++;
      return *this;
    }
 
    //后置++
    iterator operator++(int) {
      iterator tmp(*this);
      _ptr++;
      return tmp;
    }
 
    //解引用
    T& operator*() {
      return *_ptr;
    }
 
    // !=
    bool operator!=(const iterator& iter)const {
      return _ptr != iter._ptr;
    }
 
  private:
    T * _ptr;
  };
 
  //迭代器方法
  iterator begin() { return iterator(_first); }
  iterator end() { return iterator(_last);}
private:
  T* _first; // 指向數(shù)組起始的位置
  T* _last;  // 指向數(shù)組中有效元素的后繼位置
  T* _end;   // 指向數(shù)組空間的后繼位置
  Alloc _allocator; // 定義容器的空間配置器對(duì)象
 
  void expand() // 容器的二倍擴(kuò)容
  {
    int size = _end - _first;
    T* ptmp = _allocator.allocate(2 * size);
    for (int i = 0; i < size; ++i)
    {
      _allocator.construct(ptmp + i, _first[i]);
    }
    for (T* p = _first; p != _last; ++p)
    {
      _allocator.destroy(p);
    }
    _allocator.deallocate(_first);
    _first = ptmp;
    _last = _first + size;
    _end = _first + 2 * size;
  }
};
 
 
class Test
{
public:
  Test() { std::cout << "Test()" << std::endl; }
  Test& operator=(const Test&t) { std::cout << "operator=" << std::endl; return *this; }
  ~Test() { std::cout << "~Test()" << std::endl; }
  Test(const Test&) { std::cout << "Test(const Test&)" << std::endl; }
};
 
 
int main()
{
  Test t1, t2;
  std::cout << "vector<Test> vec" << std::endl;
  vector<Test> vec;
  std::cout << "vector<Test> vec; push_back" << std::endl;
 
  vec.push_back(t1);
  vec.push_back(t2);
 
  std::cout << "vector<Test> vec; pop_back" << std::endl;
  vec.pop_back();
 
  std::cout << "end" << std::endl;
 
  vector<Test>::iterator it = vec.begin();
  for (; it != vec.end(); ++it) {
    std::cout << "iterator" << " ";
  }
 
  return 0;
}