函數(shù)模板
函數(shù)模板：是不進行編譯的，因為類型還不知道
模板的實例化：函數(shù)調(diào)用點進行實例化
模板函數(shù)：才是要被編譯器所編譯的
模板類型參數(shù)：typyname/class
模板非類型參數(shù)：模板非類型形參的詳細闡述
模板的實參推演:可以根據(jù)用戶傳入的實參的類型，來推導(dǎo)出模板類型參數(shù)的具體
模板的特例化（專用化）的實例化
模板函數(shù)、模板的特例化和非模板函數(shù)的重載關(guān)系：候選的函數(shù)中，優(yōu)先在精確匹配中選擇，優(yōu)先選擇普通函數(shù)，特例性更強的模版函數(shù)次之，然后是模版函數(shù)的特化版本，最后才是泛化版本。
模板代碼是不能聲明在.h，實現(xiàn)在.cpp，模板代碼調(diào)用之前，一定要看到模板定義的地方，這樣的話，模板才能夠正常的實例化，產(chǎn)生能夠被編譯器編譯的代碼。模板代碼都是放在頭文件中，然后在源文件中直接進行#include
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
//函數(shù)模板
template<typename T> //定義一個模板參數(shù)列表
bool compare(T a, T b) {//compare 是一個函數(shù)模板
std::cout << "template compare\n";
return a > b;
}
/*
在函數(shù)調(diào)用點，編譯器用用戶指定的類型，從原模板實例化一份函數(shù)代碼出來：
模板函數(shù)：
bool compare<int>(int a, int b) {
return a > b;
}
bool compare<double>(double a, double b) {
return a > b;
}
*/
//模板特例化： 針對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;//模板的實參推演 可以根據(jù)用戶傳入的實參的類型，來推導(dǎo)模板類型參數(shù)
//編譯器優(yōu)先把compare處理成函數(shù)名，沒有的話，才去找compare模板
std::cout << compare("a", "b") << std::endl;//
return 0;
}
類模板
實現(xiàn)一個順序棧
#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)用默認構(gòu)造函數(shù)（如果存在類成員）。賦值需要調(diào)用默認構(gòu)造函數(shù)和賦值運算符
}
~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實現(xiàn)
vector 的本質(zhì)是一個數(shù)組，在vector 中需要有三個指針：
_first :指向數(shù)組的起始位置
_last:指向已經(jīng)存放的最后一個元素的下一個位置
_end:指向數(shù)組長度的末尾元素的下一個位置。
數(shù)組的容量=_end-_first
數(shù)組中存放的元素個數(shù)=_last-_first
數(shù)組是否為空:_first == _last
數(shù)組是否已滿：_last == _end
簡單的類模板實現(xiàn)代碼及測試：
#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() // 容器的二倍擴容
{
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;
}
問題：在我們實現(xiàn)的vector構(gòu)造函數(shù)中，使用new T[size] ：它做了兩件事情
（1）開辟內(nèi)存空間
（2）調(diào)用T類型的默認構(gòu)造函數(shù)構(gòu)造對象
其中第二步是一種浪費，因為我還沒在vector 添加元素，提前構(gòu)造一遍對象 然后在析構(gòu)時候是否純屬多余。
同時：在實現(xiàn)pop_back(）時，存在內(nèi)存泄漏
void pop_back() // 從容器末尾刪除元素
{
if (empty())
return;
--_last;
}
T
僅僅將_last指針 --，并沒有釋放Test申請的資源。需要調(diào)用對象的析構(gòu)函數(shù)
win msvc編譯器的實現(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)的實現(xiàn)，除了數(shù)據(jù)類型外，還有一個allocator,它將開辟空間和構(gòu)造對象分離開。
而這，也就是空間配置器做的工作；
容器的空間配置器
空間配置器主要有四個功能：
- 內(nèi)存開辟 allocate（底層調(diào)用malloc）；
- 內(nèi)存釋放 deallocate（底層調(diào)用free）；
- 對象構(gòu)造 construct（調(diào)用構(gòu)造函數(shù)）；
- 對象析構(gòu) destroy（調(diào)用析構(gòu)函數(shù)
// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫的allocator實現(xiàn)一樣 template<typename T> struct Allocator { T* allocate(size_t size) // 負責(zé)內(nèi)存開辟 { return (T*)malloc(sizeof(T) * size); } void deallocate(void* p) // 負責(zé)內(nèi)存釋放 { free(p); } void construct(T* p, const T& val) // 負責(zé)對象構(gòu)造 { new (p) T(val); // 定位new } void destroy(T* p) // 負責(zé)對象析構(gòu) { p->~T(); // ~T()代表了T類型的析構(gòu)函數(shù) } };
修改后的vector
#include <iostream>
// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫的allocator實現(xiàn)一樣
template<typename T>
class Allocator
{
public:
T* allocate(size_t size) // 負責(zé)內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void* p) // 負責(zé)內(nèi)存釋放
{
free(p);
}
void construct(T* p, const T& val) // 負責(zé)對象構(gòu)造
{
new (p) T(val); // 定位new
}
void destroy(T* p) // 負責(zé)對象析構(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)存開辟和對象構(gòu)造分開處理
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()
{
// 析構(gòu)容器有效的元素，然后釋放_first指針指向的堆內(nèi)存
for (T* p = _first; p != _last; ++p)
{
_allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進行析構(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ù)組的有效元素進行析構(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; // 定義容器的空間配置器對象
void expand() // 容器的二倍擴容
{
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實現(xiàn)的vector相同了
運算符重載與迭代器實現(xiàn)
/************************************************************************/
/*
迭代器一般實現(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);}
//運算符重載[]
T& operator[](int index) {
if (index < 0 || index >= size()) {
throw "OutofRangeException";
}
return _first[index];
}
最終vector的實現(xiàn)代碼
#include <iostream>
// 定義容器的空間配置器，和C++標(biāo)準(zhǔn)庫的allocator實現(xiàn)一樣
template<typename T>
class Allocator
{
public:
T* allocate(size_t size) // 負責(zé)內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void* p) // 負責(zé)內(nèi)存釋放
{
free(p);
}
void construct(T* p, const T& val) // 負責(zé)對象構(gòu)造
{
new (p) T(val); // 定位new
}
void destroy(T* p) // 負責(zé)對象析構(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)存開辟和對象構(gòu)造分開處理
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()
{
// 析構(gòu)容器有效的元素，然后釋放_first指針指向的堆內(nèi)存
for (T* p = _first; p != _last; ++p)
{
_allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進行析構(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ù)組的有效元素進行析構(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; }
//運算符重載[]
T& operator[](int index) {
if (index < 0 || index >= size()) {
throw "OutofRangeException";
}
return _first[index];
}
/************************************************************************/
/*
迭代器一般實現(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; // 定義容器的空間配置器對象
void expand() // 容器的二倍擴容
{
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;
}
總結(jié)
到此這篇關(guān)于C++模板以及實現(xiàn)vector的文章就介紹到這了,更多相關(guān)C++模板以及實現(xiàn)vector內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/LIJIWEI0611/article/details/121305877
