泛型(generic)允许在静态类型语言中使用一些以后才指定的类型,在实例化时作为参数指明这些类型,即类型参数化。在C++中,泛型又称为模板。STL则指标准模板库,是一个C++软件库

模板

  • C++另一种编程思想称为泛型编程,主要的技术是模板
  • C++提供两种模板机制:函数模板类模板

函数模板

建立通用函数,返回值类型和形参类型可以不具体指定,用一个虚拟的类型代表

类型参数化

语法:

template<typename T>
函数声明或定义

解释:

  • template 声明创建模板
  • typename 表示其后面的符号是一种数据类型,可以用class代替
  • T 一个符号,通常使用大写字母,代表通用数据类型

示例:

template<typename T>
void mySwap(T& a,T& b){
    T temp = a;
    a = b;
    b = temp;
}

void test01(){
    int a(10),b(20);
    //自动类型推导
    mySwap(a,b);
    //显式类型指定
    mySwap<int>(a,b);
}

自动类型推导的注意事项:

  1. 必须能够推导出数据类型

    template<typename T>
    void func(){
        cout<<"func函数调用"<<endl;
    }
    
    void test02(){
        func();  //错误
        func<int>();
    }
  2. 必须推导出一致的数据类型

    int a(10);char c('c');
    mySwap(a,c);  //错误

插入排序模板:

template<typename T>
void mySort(T* a,int n){

    for(int i=0;i<n;i++){
        int min = i;
        for(int j=i+1;j<n;j++)
            if(a[j]<a[min]) min=j;
        swap(a[min],a[i]);
    }
}

普通函数与函数模板的区别:

  • 普通函数调用时可以发生隐式类型转换
  • 函数模板调用时,如果是自动类型推导,则不会发生隐式类型转换
  • 如果是显式类型指定,则可以发生隐式类型转换

普通函数与函数模板的调用规则:

  1. 如果普通函数与函数模板都可以实现,优先调用普通函数
  2. 可以通过空模板参数列表来强制调用函数模板
  3. 函数模板也可以发生重载
  4. 如果函数模板可以产生更好的匹配,优先调用函数模板
void myPrint(int a,int b){
    cout<<"调用的普通函数"<<endl;
}

template<typename T>
void myPrint(T a,T b){
    cout<<"调用的模板"<<endl;
}

void test01() {
    int a(10),b(20);
    myPrint(a,b);      //调用普通函数
    myPrint<>(a,b);    //调用模板--空参数列表
    myPrint<int>(a,b); //调用模板

    char c('c'),d('d');
    myPrint(c,d);      //调用模板--更好的匹配
}

函数模板的具体化

//通用函数模板
template<typename T>
bool myCompare(T& a, T& b){
    //...
}
//具体化,具体化优先于通用模板
template<> bool myCompare(Person& p1, Person& p2){
    //...
}

类模板

建立一个通用类,类中的成员的数据类型可以不具体指定,用一个虚拟的类型代表

语法:

template<typename T>
类

举例:

template<class NameType, class AgeType>
class Person
{
public: 
    Person(NameType name, AgeType age){
        this->m_Name = name;
        this->m_Age = age;
    }
    
    NameType m_Name;
    AgeType m_age;
};

void test01(){
    Person<string, int> p1("张三",18);
}

类模板与函数模板的区别:

  1. 类模板没有自动类型推导
  2. 类模板的参数列表可以有默认参数类型

    template<class NameType, class AgeType = int>
    class Person
    {
    public: 
        Person(NameType name, AgeType age){
            this->m_Name = name;
            this->m_Age = age;
        }
        
        NameType m_Name;
        AgeType m_age;
    };
    
    void test01(){
        Person<string> p1("张三",18);
    }

类模板中成员函数的创建时机:

  • 普通类中的成员函数
  • 类模板中的成员函数在调用时创建
class Person1{
public:
    void showPerson1(){cout<<"showPerson1调用"<<endl;}
};

class Person2{
public:
    void showPerson2(){cout<<"showPerson2调用"<<endl;}
};

template<class T>
class show{
public:
    T obj;

    void func1(){obj.showPerson1();}
    void func2(){obj.showPerson2();}
};
void test01(){
    show<Person1> s1;
    s1.func1();
    show<Person2> s2;
    s2.func2();
}

类模板对象做函数参数

  1. 指定传入的类型
  2. 参数模板化
  3. 整个类模板化
template<class T1, class T2 = int>
class Person{
public:
    Person(T1 name, T2 age){
        this->mName = name;
        this->mAge = age;
    }
    void showPerson(){
        cout<<"name:"<<this->mName<<" "<<"age:"<<this->mAge<<endl;
    }
public:
    T1 mName;
    T2 mAge;
};

void printPerson1(Person<string, int>&p){
    p.showPerson();
}
template<typename T1, typename T2>
void printPerson2(Person<T1, T2>&p){
    p.showPerson();
}
template<class T>
void printPerson3(T & p){
    p.showPerson();
}
void test01(){
    Person<string, int> p1("孙悟空", 100);
    printPerson1(p1);
    printPerson2(p1);
    printPerson3(p1);
}

类模板与继承

  • 当父类是类模板时,如果子类不是模板,就要指出父类中T的类型

class Son:public Base<数据类型>

  • 如果想灵活指出父类中T的类型,子类也需变为类模板

    template<class T1, class T2>
    class Son:public Base<T2>
    {
    public:
        T1 obj;
    };

类模板成员函数类外实现

//构造函数类外实现
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age){
    this->m_Name;
    this->m_Age;
}
//成员函数类外实现
template<class T1, class T2>
void Person<T1, T2>::showPerson(){
    cout<<this->m_Name<<" "<<this->m_Age<<endl;
}

类模板分文件编写

问题:

  • 类模板中成员函数的创建时机是在调用阶段,导致分文件编写时链接不到

解决:

  • 方式一:直接包含.cpp源文件
  • 方式二:将声明和实现写到同一个文件中,例如都写到一个.hpp文件中

    #pragma once
    #include <iostream>
    #include <string>
    using namespace std;
    
    template<class T1, class T2>
    class Person{
    //...
    }
    //类外实现的函数
    //...

类模板与友元

//2.类外实现
template<class T1, class T2> class Person;
//2.如果声明了函数模板,可以将实现写到后面,否则需要将实现体写到类的前面
//template<class T1, class T2> void printPerson2(Person<T1, T2> &p);
template<class T1, class T2>
void printPerson2(Person<T1, T2> &p){
    cout<<"类外实现--name:"<<p.m_Name<<" "<<"age:"<<p.m_Age<<endl;
}

template<class T1, class T2>
class Person{
    //1.全局函数配合友元 类内实现
    friend void printPerson(Person<T1, T2> &p){
        cout<<"类内实现--name:"<<p.m_Name<<" "<<"age:"<<p.m_Age<<endl;
    }

    //2.全局函数配合友元 类外实现
    //需要空参数列表
    friend void printPerson2<>(Person<T1, T2> &p);

public:
    Person(T1 name, T2 age){
        this->m_Name = name;
        this->m_Age = age;
    }
public:
    T1 m_Name;
    T2 m_Age;
};

STL

基本概念:

  • STL(Standard Template Library, 标准模板库)
  • STL从广义上分为:容器(container)、算法(algorithm)、迭代器(iterator)
  • 容器和算法之间通过迭代器进行无缝连接
  • STL几乎所有代码都采用了模板类或者模板函数

组件:

STL大体分为六大组件,分别是:容器算法迭代器仿函数适配器(配接器)、空间配置器

  1. 容器:各种数据结构,如vector、list、deque、set、map等,用来存放数据
  2. 算法:各种常用的算法,如sort、find、copy、for_each等
  3. 迭代器:扮演了容器与算法之间的胶合剂
  4. 仿函数:行为类似函数,可作为算法的某种策略
  5. 适配器:一种用来修饰容器或者仿函数或迭代器接口的东西
  6. 空间配置器:负责空间的配置与管理

容器 (container)

用于存放数据的类模板

分类:

  1. 顺序容器:向量容器vector、双端队列deque、双向链表list
  2. 关联容器:单重集合set、多重集合multiset、单重映射表map、多重映射表multimap
  3. 容器适配器:栈stack、队列queue、优先级队列priority_queue

string

  • string是C++风格的字符串,本质是一个类
  • string类内部封装了char*,管理这个字符串,是一个char*型的容器
  • string类内部封装了很多成员方法,例如size,find,copy,delete,replace,insert

构造和赋值

构造:

  • string();

string(const char* s);

  • string(const string& str);
  • string(int n, char c);

赋值:

  • string& operator=(const char* s); //str1 = "Hello";
  • string& operator=(const string &s); //str2 = str1;
  • string& operator=(char c); //str3 = 'a';
  • string& assign(const char* s); //str4.assign("Hello");
  • string& assign(const char* s, int n); //str5.assign("Hello",2);
  • string& assign(const string &s);
  • string& assign(int n, char c);

大小比较:

  • int compare(const string &s) const;
  • int compare(const char *s) const;

返回值:

相等:0

大于:1

小于:-1

字符串拼接

  • string& operator+=(const char* str/const string& str/const char c);
  • string& append(const char *s);
  • string& append(const char *s, int n); //拼接s的前n个字符
  • string& append(const string &s);
  • string& append(const string &s, int pos, int n); //拼接s的pos位置后的n个位置

查找和替换

查找:

  • int find(const string& str, int pos = 0) const; //从pos位置开始,查找str第一次出现的位置
  • int find(const char* s, int pos = 0) const;
  • int find(const char* s, int pos, int n) const; //从pos位置开始查找s的第n个字符第一次出现的位置
  • int find(const char c, int pos = 0) const; //查找字符c第一次出现位置
  • rfind函数:从右向左查找,用法同上,默认起始位置是最后一个
string str1 = "abcdefg";
int pos = str1.find("df");
if(pos == -1)cout<<"未找到"<<endl;
else cout<<"找到字符串,位置是"<<pos<<endl;

替换:

  • string& replace(int pos, int n, const string& str); //替换从pos开始的n个字符为str
  • string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为s

字符存取:

  • char& operator[](int n);
  • char& at(int n);

字符数目:

size();

插入和删除

  • string& insert(int pos, const char* s);
  • string& insert(int pos, const string& str);
  • string& insert(int pos, int n, char c);
  • string& erase(int pos, int n = npos);

子串获取

  • string substr(int pos = 0, int n = npos) const;
string email = "[email protected]";
int pos = email.find("@");
string username = email.substr(0, pos);

vector

vector数据结构和数组类似,也称为单端数组

与普通数组的区别

  • vector可以动态扩展

动态扩展:

  • 并不是在原空间之后续接新空间,而是找更大的空间,然后将数据拷贝到新空间,释放原空间

vector容器的迭代器是支持随机访问的迭代器,可以像数组一样用[]访问数据

构造和赋值

构造函数:

  • vector<T> v; //默认构造函数
  • vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素复制给本身
  • vector(n, elem); //将n个elem复制给本身
  • vector(const vector &vec); //复制构造
vector<int> v1;
for(int i=0;i<10;i++)
    v1.push_back(i);

vector<int> v2(v1.begin(), v1.end());
vector<int> v3(10, 100);
vector<int> v4(v3);

赋值操作:

  • vector& operator=(const vector &vec)
  • assign(begin, end)
  • assign(n,elem)

遍历数据

算法: for_each

迭代器:vector<int>::iterator

void test01(){

    vector<int> v;
    v.push_back(10);v.push_back(20);v.push_back(30);

    //通过迭代器访问数据
    vector<int>::iterator itBegin = v.begin();  //起始迭代器 指向容器中第一个元素
    auto itEnd = v.end();  //使用auto定义迭代器 结束迭代器 指向最后一个元素的下一位

    //第一种遍历方式
    while(itBegin != itEnd){
        cout<< *itBegin <<endl;
        itBegin++;
    }
    
    //for循环
    for(vector<int>::iterator it = v.begin();it!=v.end();it++)
        cout<< *itBegin <<endl;
    
    //第二种遍历方式 使用基于范围的for循环
    for(int & it : v)
        cout<< it <<endl;
    
    //第三种遍历方式
    for_each(v.begin(), v.end(), myPrint);
}

数据存取:

  • at(int idx); //返回索引idx指向的数据
  • operator[]; //返回下标对应的元素
  • front(); //返回容器中第一个数据元素
  • back(); //返回容器中最后一个数据元素
//[]遍历数据
for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";
//at遍历数据
for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<" ";

容量和大小:

  • empty(); //返回一个bool值,判断容器是否为空
  • capacity(); //容器的容量,大于等于size()
  • size(); //返回容器中元素的个数
  • resize(int num); //重设长度,若变长以默认值填充,若变短从尾部删除
  • resize(int num, elem); //重设长度,若变长以elem值填充,若变短从尾部删除

插入和删除

注:提供的位置pos都是迭代器

函数原型作用
push_back(ele);尾插
pop_back();尾删
insert(pos, elem);在pos位置插入elem元素,返回新数据的位置
insert(pos, n, elem);在pos位置插入n个elem数据,无返回值
erase(begin, end);删除[begin,end)区间的数据,返回下一个数据的位置
erase(pos);删除pos位置的数据,返回下一个数据的位置
clear();清空容器内的所有数据

互换容器:

  • swap(vec); //将vec与本身的元素互换
v1.swap(v2);

用途:收缩内存空间

vector<int> v;
for(int i=0;i<100000;i++)
    v.push_back(i);

cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出10万和13万(大约)

v.resize(3);  //重设大小为3,容量不会减少
cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出3和13万(大约)

vector<int>(v).swap(v);//使用复制构造创建匿名对象,与v交换
//这里也可用v.shrink_to_fit();自动收缩
cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出3和3

预留空间:

减少vector在动态扩展容量时的扩展次数

函数原型:

  • reserve(int len); //预留len个元素长度,预留位置不初始化,元素不可访问

容器嵌套

vector<vector<int>> v;

for (vector<vector<int>>::iterator it = v.begin();it != v.end();it++)
    for(vector<int>::iterator vit = (*it).begin();vit != (*it).end();vit++)
        cout<<*vit<<" ";

deque

  • 双端数组,可以对头端进行插入删除操作

deque与vector的区别:

  • vector对头部的插入删除效率低,数据量越大,效率越低
  • 相对而言,deque对头部的插入删除速度比vector快
  • vector访问元素时的速度会比deque快,这和两者的内部实现有关

deque工作原理:

缓冲区存放数据,使用中控器维护每段缓冲区的地址,使得使用deque时就像一片连续的空间

  • deque容器的迭代器也是支持随机访问

构造和赋值

构造函数:

  • deque<T> deq
  • deque(begin, end);
  • deque(n, elem);
  • deque(const deque &deq);
deque<int> d;

for(int i=0;i<10;i++)
    d.push_back(i);

deque<int>d2(d.begin(),d.end());
deque<int>d3(10,100);
deque<int>d4(d3);

赋值操作与vector类似

  • deque& operator=(const deque &deq)
  • assign(begin, end)
  • assign(n,elem)

数据存取同vector

  • at(int idx); //返回索引idx指向的数据
  • operator[]; //返回下标对应的元素
  • front(); //返回容器中第一个数据元素
  • back(); //返回容器中最后一个数据元素

大小操作:

  • deque.empty();
  • deque.size();
  • deque.resize(num);
  • deque.resize(num, elem);

deque与vector不同,没有容量概念,所以没有capacity();函数

void printDeque(const deque<int>& d){
    for(deque<int>::const_iterator it = d.begin();it != d.end();it++)
        cout<<*it<<" ";
    cout<<endl;
}

插入和删除

注:提供的位置pos都是迭代器

函数原型作用
push_back(elem);尾插
push_front(elem);头插
pop_back();尾删
pop_front();头删
insert(pos, elem);在pos位置插入elem元素,返回新数据的位置
insert(pos, n, elem);在pos位置插入n个elem数据,无返回值
insert(pos, begin, end);在pos位置插入[begin, end)区间的数据,无返回值
erase(begin, end);删除[begin,end)区间的数据,返回下一个数据的位置
erase(pos);删除pos位置的数据,返回下一个数据的位置
clear();清空容器内的所有数据

数据排序

头文件:<algorithm>

  • sort(iterator begin, iterator end)

stack

栈是一种先进后出 (FILO, First In Last Out)的数据结构,它只有一个出口

只有顶端的元素才能被使用,因此栈不允许有遍历行为

常用接口

构造函数:

  • stack<T> stk;
  • stack (const stack &stk);

赋值操作:

  • stack& operator=(const stack &stk);

数据存取:

  • push(elem);
  • pop();
  • top();

大小操作:

  • empty();
  • size();

queue

队列是一种先进先出 (FIFO, First In First Out)的数据结构,它有两个出口

队列容器允许从一端新增元素,从另一端移除元素

栈不可遍历

常用接口

构造函数:

  • queue<T> que;
  • queue (const queue &que);

赋值操作:

  • queue& operator=(const queue &que);

数据存取:

  • push(elem);
  • pop();
  • back();
  • top();

大小操作:

  • empty();
  • size();

list

STL中的链表是双向循环链表

优点:在任意位置插入或删除元素的速度较快

缺点:容器的遍历速度没有数组快

由于链表的存储方式并不是连续的内存空间,因此list中的迭代器只支持前移和后移,属于双向迭代器

构造和赋值

构造函数:

  • list<T> ls;
  • list(begin, end);
  • list(n, elem);
  • list(const list &ls);

赋值和交换:

  • assign(begin, end);
  • assign(n, elem);
  • list& operator=(const list &ls);
  • swap(ls);

大小操作:

  • size();
  • empty();
  • resize(num);
  • resize(num, elem);

数据存取:

  • front();
  • back();

插入和删除

注:提供的位置pos都是迭代器

函数原型作用
push_back(elem);尾插
push_front(elem);头插
pop_back();尾删
pop_front();头删
insert(pos, elem);在pos位置插入elem元素,返回新数据的位置
insert(pos, n, elem);在pos位置插入n个elem数据,无返回值
insert(pos, begin, end);在pos位置插入[begin, end)区间的数据,无返回值
erase(begin, end);删除[begin,end)区间的数据,返回下一个数据的位置
erase(pos);删除pos位置的数据,返回下一个数据的位置
clear();清空容器内的所有数据
remove(elem);删除容器中所有与elem值匹配的元素

反转和排序

  • reverse(); //反转
  • sort(); //排序

注意:不支持随机访问迭代器的容器,不可以用标准算法

sort(l.begin(), l.end()); //错误,应该使用内部提供的算法l.sort();

降序排列:

bool myCompare(int v1, int v2){
    return v1 > v2;
}
void test01{
    L1.sort(myCompare);
}

set / multiset

  • set/multiset属于关联式容器,底层结构是用二叉树实现的
  • 元素会在插入时自动排序

构造和赋值

构造:

  • set<T> st;
  • set(const set &st);

赋值:

  • set& operator=(const set &st);

大小和交换:

  • size();
  • empty();
  • swap(st);

插入和删除:

  • insert(elem);
  • clear();
  • erase(pos);
  • erase(begin, end);
  • erase(elem);

查找和统计

  • find(elem); //返回值是迭代器,找不到则返回s.end()
  • count(elem); //返回elem的个数
set<int>::iterator pos = s1.find(30);
if(pos != s1.end()) cout<<*pos<<endl;

set和multiset的区别

  • set不允许插入重复的元素
  • multiset允许重复的元素

set的插入操作会返回一个对组(迭代器, bool值)

set<int> s;

pair<set<int>::iterator, bool> ret = s.insert(10);

if(ret.second) cout<<"插入成功"<<endl;

multiset的插入操作会返回一个迭代器

注:对组的创建:

  • pair<type, type> p (value1, value2);
  • pair<type, type> p = make_pair(value1, value2);

指定排序规则

set存放内置数据类型:

class MyCompare{
public:
    bool operator()(int v1, int v2){
        return v1 > v2;
    }
};

void test01(){
    set<int, MyCompare> s1;
    s1.insert(10);
    s1.insert(20);
    
    for(set<int, MyCompare>::iterator it = s1.begin(); it != s1.end(); it++)
        cout<<*it;
}

set存放自定义数据类型:

class Person
{
public:
    Person(string name,int age){
        this->m_Name=name;
        this->m_Age=age;
    }

    string m_Name;
    int m_Age;
};

class PersonCompare{
public:
    bool operator()(const Person& p1,const Person& p2){
        return p1.m_Age > p2.m_Age;
    }
};


void test02(){

    Person p1("张飞",18),
    p2("刘备",20),
    p3("关羽",19);

    set<Person,PersonCompare> s;
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);

    for(const auto & it : s) cout<<it.m_Name;
}

map / multimap

  • map中的元素是键值对pair(key:value)
  • 元素根据key自动排序
  • map/multimap属于关联式容器,底层结构是用二叉树实现

map与multimap的区别:

键是否唯一

构造和赋值:

  • map<T1, T2> mp;
  • map(const map &mp);

赋值:

  • map& operator=(const map &mp);

插入和删除:

  • insert

    • insert(pair<__keyType, __valueType>(__key, __value));
    • insert(make_pair(__key,__value));
    • insert(map<__keyType, __valueType>::value_type(__key, __value));
    • m[__key] = __value;
  • clear();
  • erase(pos);
  • erase(begin, end);
  • erase(key);

大小和交换:

  • size();
  • empty();
  • swap(st);

查找和统计:

  • find(key); //返回值是迭代器,找不到返回set.end()
  • count(key); //返回key的个数

函数对象 (仿函数)

函数对象

概念:

函数对象是一个,类中重载了函数调用操作符,也叫仿函数

特点:

  • 函数对象在使用时,可以像普通函数一样,可以有参数、有返回值
  • 函数对象超出普通对象的概念,函数对象可以有自己的状态
  • 函数对象可以作为参数传递

谓词

概念:

  • 返回bool类型的仿函数称为谓词
  • 如果operator()接受一个参数,那么叫做一元谓词
  • 如果operator()接受两个参数,那么叫做二元谓词

一元谓词:

class GreaterThan5{
public:
    bool operator()(int v){
        return v > 5;
    }
};

void test03(){
    vector<int> v;
    v.reserve(10);
    for(int i=0;i<10;i++){
        v.push_back(i);
    }

    auto it = find_if(v.begin(),v.end(),GreaterThan5());
    if(it == v.end())cout<<"未找到";
    else cout<<"找到:"<<*it;
}

二元谓词:

class myCompare{
public:
    bool operator()(int v1, int v2){
        return v1 > v2;
    }
};

void test04(){
    vector<int> v;
    v.reserve(10);
    for(int i=0;i<10;i++){
        v.push_back(i);
    }

    sort(v.begin(), v.end(), myCompare());

    for(auto i : v)cout<<i;
}

内建函数对象

  • STL内建了一些函数对象
  • 使用内建函数对象,需要引入头文件<functional>

算术仿函数

  • template<class T> T plus<T>
  • template<class T> T minus<T>
  • template<class T> T multiplies<T>
  • template<class T> T divides<T>
  • template<class T> T modulus<T>
  • template<class T> T negate<T>

关系仿函数

  • template<class T> bool equal_to<T>
  • template<class T> bool not_equal_to<T>
  • template<class T> bool greater<T>
  • template<class T> bool greater_equal<T>
  • template<class T> bool less<T>
  • template<class T> bool less_equal<T>

逻辑仿函数

  • template<class T> bool logical_and<T>
  • template<class T> bool logical_or<T>
  • template<class T> bool logical_not<T>