模板

模板是C++支持参数化多态的工具，使用模板可以使用户为类或者函数声明一种一般模式，使得类中的某些数据成员或者成员函数的参数、返回值取得任意类型。

模板是一种对类型进行参数化的工具；

通常有两种形式：

• 函数模板：函数模板针对仅参数类型不同的函数。

• 类模板：类模板针对仅数据成员和成员函数类型不同的类。

使用模板的目的就是能够让程序员编写与类型无关的代码。比如编写了一个交换两个整型int 类型的swap函数，这个函数就只能实现int 型，对double，字符这些类型无法实现，要实现这些类型的交换就要重新编写另一个swap函数。使用模板的目的就是要让这程序的实现与类型无关，比如一个swap模板函数，即可以实现int 型，又可以实现double型的交换。

函数模板

语法：

template <typename 形参名，class 形参名，......> 返回类型 函数名(参数列表)
{
    函数体
}

其中template和typename是关键字，typename可以用class关键字代替，在这里typename 和class没区别，<>括号中的参数叫模板形参，模板形参和函数形参很相像，模板形参不能为空。

一但声明了模板函数就可以在该函数中使用内置类型的地方都可以使用模板形参名。

模板形参需要调用该模板函数时提供的模板实参来初始化模板形参，一旦编译器确定了实际的模板实参类型就称他实例化了函数模板的一个实例。比如swap的模板函数形式为：

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

当调用这样的模板函数时类型T就会被被调用时的类型所代替，比如swap(a,b)其中a和b是int 型，这时模板函数swap中的形参T就会被int 所代替，模板函数就变为swap(int &a, int &b)。而当swap(c,d)其中c和d是double类型时，模板函数会被替换为swap(double &a, double &b)，这样就实现了函数的实现与类型无关的代码。

普通函数和模板函数

• 普通函数调用时可以发生自动类型转换(隐式类型转换)

• 函数模板调用时,如果利用自动类型推导,不会发生隐式类型转换

• 如果利用显示指定类型的方式,可以发生隐式类型转换

模板的通用性并不是万能的，例如：

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


/*
此时向数组中传入数组则会报错
*/

void Test()
{
    int a[3] = {1, 2, 3};
    int b[3] = {4, 5, 6};
    Swap(a, b);
}

因此，模板的重载可以为这些特定的数据类型提供具体化的模板

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

//针对于数组类型，提供一个具体的模板函数
template <>
void Swap(int (&c)[3], int (&d)[3])
{
    int temp[3];
    for (int i = 0; i < 3; i++)
    {
        temp[i] = c[i];
        c[i] = d[i];
        d[i] = temp[i];
    }
}

void Test()
{
    int a[3] = {1, 2, 3};
    int b[3] = {4, 5, 6};
    Swap(a, b); //此时则无问题
}

类模板

类模板作用：

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

语法：

template <typename T>
类

或

template <class T>
类

例如：

template <class TName, class TAge>
class Person
{
Public:
    Person(TName n, TAge a)
    {
        this->name = n;
        this->age = a;
    }
    TName name;
    TAge age;
};

类模板和函数模板

类模板与函数模板区别主要有两点：

• 类模板没有自动类型推导的使用方式

void Test()
{
    //没有自动类型推导，实例化时必须附带上指定的数据类型
    Person<string, int> p("TestName", 10);
}

• 类模板在模板参数列表中可以有默认参数

//为Age指定默认的数据类型
template <class TName, class TAge = int>
class Person
{
Public:
    Person(TName n, TAge a)
    {
        this->name = n;
        this->age = a;
    }
    TName name;
    TAge age;
};

void Test()
{
    //此时因为Age具有了默认数据类型，可省略手动指定
    Person<string> p("TestName", 10);
}

类模板对象做函数参数

一共有三种传入方式：

• 指定传入的类型：直接显示对象的数据类型
• 参数模板化：将对象中的参数变为模板进行传递
• 整个类模板化：将这个对象类型模板化进行传递

template <class TName, class TAge>
class Person
{
public:
    Person(TName n, TAge a)
    {
        this->name = n;
        this->age = a;
    }
    TName name;
    TAge age;

    void ShowPerson()
    {
        cout << this->name << ": " << this->age << endl;
    }
};

//方法1：传入指定的类型
void PrintPerson_1(Person<string, int> &person)
{
    person.ShowPerson();
}

//方法2：参数模板化
template <class TName, class TAge>
void PrintPerson_2(Person<TName, TAge> &person)
{
    person.ShowPerson();
}

//方法2：整个类模板化
template <class TPerson>
void PrintPerson_3(TPerson &person)
{
    person.ShowPerson();
}

void Test()
{
    Person<string, int> p1("TestName_1", 10);
    Person<string, int> p2("TestName_2", 20);
    Person<string, int> p3("TestName_3", 30);
    PrintPerson_1(p1);
    PrintPerson_1(p2);
    PrintPerson_1(p3);
}

类模板与继承

当类模板碰到继承时,需要注意一下几点：

• 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中 T 的类型
• 如果不指定吗，编译器无法给子类分配内存
• 如果想灵活指定出父类中T的类型，子类也需变为类模板

template <class T>
class Base
{
    T age;
};

//class Son:public Base //错误,c++编译需要给子类分配内存,必须知道父类中T的类型才可以向下继承
class Son : public Base<int> //必须指定一个类型
{
    
};

类模板中成员函数的类外实现

/*******************类内定义************************/
template <class TName, class TAge>
class Person
{
public:
    Person(TName n, TAge a);
//    {
//        this->name = n;
//        this->age = a;
//    }
    TName name;
    TAge age;

    void ShowPerson();
//    {
//        cout << this->name << ": " << this->age << endl;
//    }
};

/*******************类外实现************************/

//构造函数的类外实现
template <class TName, class TAge>
Person<TName, TAge>::Person(TName n, TAge a)
{
    this->name = n;
    this->age = a;
}

//成员函数的类外实现
template <class TName, class TAge>
void Person<TName, TAge>::ShowPerson()
{
    cout << this->name << ": " << this->age << endl;
}

上述方式对于类模板分文件编写很重要，可将类放置于.h文件中，将类外实现放置于.cpp文件中。

类模板分文件编写

问题：

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

解决：

• 解决方式1：直接包含.cpp源文件

• 解决方式2：将声明和实现写到同一个文件中，并更改后缀名为.tpp（tpp是约定的名称，并不是强制）

/******Person.h文件中的内容******/
#pragma once
#include <iostream>
#include <string>
using namespace std;

template <class TName, class TAge>
class Person
{
public:
    Person(TName n, TAge a);

    TName name;
    TAge age;
    
    void ShowPerson();

};

/******Person.tpp文件中的内容******/
#include "Person.h"

template <class TName, class TAge>
Person<TName, TAge>::Person(TName n, TAge a)
{
    this->name = n;
    this->age = a;
}

template <class TName, class TAge>
void Person<TName, TAge>::ShowPerson()
{
    cout << this->name << ": " << this->age << endl;
}


/******main中的内容******/
#include <iostream>
#include <string>
using namespace std;
#include "./Class/Person.tpp"

void Test()
{
    Person<string, int>("Test", 25).ShowPerson();
}

int main()
{
    Test();
    return 0;
}

类模板与友元

全局函数类内实现：直接在类内声明友元即可

全局函数类外实现：需要提前让编译器知道全局函数的存在

以下为类内实现：

template <class TName, class TAge>
class Person
{
public:
    Person(TName n, TAge a);
    {
        this->name = n;
        this->age = a;
    }
    
    //全局函数类内实现
    friend void ShowPerson(Person<TName, TAge> p)
    {
       cout << "姓名:" << p.m_Name << "年龄:" << p.m_Age << endl;
    }
    
private:
    TName name;
    TAge age;

};

void Test()
{
    Person<string, int>person("Test", 25);
    ShowPerson(person);
}

以下为类外实现：

//顺序很重要，需要提前让编译器知道Person类的存在
template <class TName, class TAge>
class Person;

//放在Person之前，让Person知道此函数的存在
template <class TName, class TAge>
void ShowPerson(Person<TName, TAge> p)
{
   cout << "姓名:" << p.m_Name << "年龄:" << p.m_Age << endl;
}

template <class TName, class TAge>
class Person
{
public:
    Person(TName n, TAge a);
    {
        this->name = n;
        this->age = a;
    }
    
    //全局函数类外实现
    friend void ShowPerson(Person<TName, TAge> p);
    
private:
    TName name;
    TAge age;

};

void Test()
{
    Person<string, int>person("Test", 25);
    ShowPerson(person);
}

初识STL

• STL（Standard Template Library，标准模板库）

• STL从广义上分为：容器(container)、算法(algorithm)、迭代器(iterator)

• 容器和算法之间通过迭代器进行无缝连接。

• STL几乎所有的代码都采用了模板类或者模板函数

STL六大组件

STL大体分为六大组件，分别是：容器、算法、迭代器、函数对象、适配器、空间配置器

• 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据。

• 算法：各种常用的算法，如sort、find、copy、for_each等

• 迭代器：扮演了容器与算法之间的胶合剂。

• 函数对象：行为类似函数，可作为算法的某种策略。

• 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

• 空间配置器：负责空间的配置与管理。

容器

容器是用来存储数据的序列，它们提供了不同的存储方式和访问模式。

STL 中的容器可以分为三类：

1、序列容器：存储元素的序列，允许双向遍历。

• std::vector：动态数组，支持快速随机访问。
• std::deque：双端队列，支持快速插入和删除。
• std::list：链表，支持快速插入和删除，但不支持随机访问。

2、关联容器：存储键值对，每个元素都有一个键（key）和一个值（value），并且通过键来组织元素。

• std::set：集合，不允许重复元素。
• std::multiset：多重集合，允许多个元素具有相同的键。
• std::map：映射，每个键映射到一个值。
• std::multimap：多重映射，存储了键值对（pair），其中键是唯一的，但值可以重复，允许一个键映射到多个值。

3、无序容器（C++11 引入）：哈希表，支持快速的查找、插入和删除。

• std::unordered_set：无序集合。
• std::unordered_multiset：无序多重集合。
• std::unordered_map：无序映射。
• std::unordered_multimap：无序多重映射。

算法

C++ 标准库中的 <algorithm> 头文件提供了一组用于操作容器（如数组、向量、列表等）的算法。这些算法包括排序、搜索、复制、比较等，它们是编写高效、可重用代码的重要工具。

<algorithm> 头文件定义了一组模板函数，这些函数可以应用于任何类型的容器，只要容器支持迭代器。这些算法通常接受两个或更多的迭代器作为参数，表示操作的起始和结束位置。

语法

大多数 <algorithm> 中的函数都遵循以下基本语法：

algorithm_name(container.begin(), container.end(), ...);

这里的 container 是一个容器对象，begin() 和 end() 是容器的成员函数，返回指向容器开始和结束的迭代器。

排序算法

函数：sort

定义：对容器中的元素进行排序。

语法：

sort(container.begin(), container.end(), compare_function);

其中 compare_function 是一个可选的比较函数，用于自定义排序方式。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

1 2 5 5 6 9 

std::partial_sort: 对部分区间排序，前 n 个元素为有序。

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

std::stable_sort: 稳定排序，保留相等元素的相对顺序。

std::stable_sort(vec.begin(), vec.end());

搜索算法

函数：find

定义：在容器中查找与给定值匹配的第一个元素。

语法：

auto it = find(container.begin(), container.end(), value);

如果找到，it 将指向匹配的元素；如果没有找到，it 将等于 container.end()。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = std::find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Value not found." << std::endl;
    }

    return 0;
}

输出结果：

Found: 3

std::binary_search: 对有序区间进行二分查找。

std::sort(vec.begin(), vec.end());  // 先排序
bool found = std::binary_search(vec.begin(), vec.end(), 4);

std::find_if: 查找第一个满足特定条件的元素。

auto it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 3; });

复制算法

函数：copy

定义：将一个范围内的元素复制到另一个容器或数组。

语法：

copy(source_begin, source_end, destination_begin);

示例：

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    int destination[5];
    std::copy(source.begin(), source.end(), destination);

    for (int i = 0; i < 5; ++i) {
        std::cout << destination[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

1 2 3 4 5 

比较算法

函数：equal

定义：比较两个容器或两个范围内的元素是否相等。

语法：

bool result = equal(first1, last1, first2);

或

bool result = equal(first1, last1, first2, compare_function);

示例：

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {1, 2, 3, 4, 5};

    bool are_equal = std::equal(v1.begin(), v1.end(), v2.begin());
    std::cout << (are_equal ? "Vectors are equal." : "Vectors are not equal.") << std::endl;

    return 0;
}

输出结果：

Vectors are equal.

修改算法

std::reverse: 反转区间内的元素顺序。

std::reverse(vec.begin(), vec.end());

std::fill: 将指定区间内的所有元素赋值为某个值。

std::fill(vec.begin(), vec.end(), 0);  // 所有元素设为 0

std::replace: 将区间内的某个值替换为另一个值。

std::replace(vec.begin(), vec.end(), 1, 99);  // 将所有 1 替换为 99

std::copy: 将区间内的元素复制到另一个区间。

std::vector<int> vec2(6);
std::copy(vec.begin(), vec.end(), vec2.begin());

排列算法

std::next_permutation: 生成字典序的下一个排列，如果没有下一个排列则返回 false。

std::vector<int> vec = {1, 2, 3};
do {
    for (int n : vec) std::cout << n << " ";
    std::cout << std::endl;
} while (std::next_permutation(vec.begin(), vec.end()));

std::prev_permutation: 生成字典序的上一个排列。

std::prev_permutation(vec.begin(), vec.end());

归并算法

std::merge: 将两个有序区间合并到一个有序区间。

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result(6);
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

std::inplace_merge: 在单个区间中合并两个有序子区间。

std::inplace_merge(vec.begin(), middle, vec.end());

集合算法

std::set_union: 计算两个有序集合的并集。

std::vector<int> result(10);
auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_intersection: 计算两个有序集合的交集。

auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_difference: 计算集合的差集。

auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

其他有用算法

std::accumulate（需要 <numeric> 库）：计算范围内元素的累计和。

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::for_each: 对区间内的每个元素执行操作。

std::for_each(vec.begin(), vec.end(), [](int& x) { x += 1; });

std::min_element 和 std::max_element: 查找区间内的最小值和最大值。

auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());

<algorithm> 是 C++ 标准库中一个非常强大的工具，它提供了大量通用的算法，可以极大地简化编程。

迭代器

常用的为双向迭代器和随机访问迭代器

Vector容器

在 C++ 中，vector 是最常用的 STL 容器之一。

vector 本质上是一个可自动扩容的动态数组，与传统数组相比，vector 不需要手动管理内存，可以根据元素数量自动扩容。

由于 vector 具有：

• 连续内存存储
• 随机访问速度快
• STL 生态完整
• 缓存友好（Cache Friendly）

因此，在现代 C++ 开发中，大部分顺序数据存储场景都会优先考虑 vector。

vector 的核心特点

• 动态大小：vector 可以自动扩容和缩容。
• 连续内存：元素在内存中连续存储，访问效率非常高。
• 随机访问：支持通过下标快速访问元素，时间复杂度为 O(1)。
• 自动内存管理：不需要手动 malloc/free。
• 支持迭代器：可以方便地与 STL 算法配合使用。

为什么 vector 很快？

vector 的元素在内存中是连续排列的：

[1][2][3][4][5]

这种布局对 CPU Cache 非常友好。

CPU 在读取第一个元素时，通常会提前把后面的数据一起加载到缓存中，因此遍历 vector 的速度通常非常快。

这也是为什么很多情况下：vector 比 list 更快

即使 list 在理论上的删除复杂度更低。

使用 vector

使用 vector 前，需要包含头文件：

#include <vector>

常用成员函数

以下是 <vector> 中的一些常用成员函数：

创建 vector

创建一个空 vector：

std::vector<int>vec;

指定初始大小：

std::vector<int>vec(5);

以上代码会创建 5 个元素，默认值为 0。

指定初始值：

std::vector<int>vec(5, 10);

创建结果：

[10, 10, 10, 10, 10]

使用初始化列表：

std::vector<int>vec = {1, 2, 3, 4};

添加元素

使用 push_back() 向尾部添加元素：

vec.push_back(100);

vector 尾部追加元素的平均时间复杂度为：O(1)

访问元素

使用下标访问：

int x = vec[0];

使用 at()：

int y = vec.at(1);

使用begin和end访问：

int y = vec.begin();//指向容器中第一个元素
int y = vec.end();//指向容器中第最后个元素的下一个位置

获取大小

vec.size();

返回当前元素数量。

size 和 capacity 的区别

这是 vector 最重要的概念之一。

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

输出可能为：

2
4

• size：当前元素数量。
• capacity：当前已分配的内存容量。

capacity 通常大于等于 size。

这是因为 vector 会提前申请更多空间，以减少频繁扩容。

vector 扩容机制

当 vector 空间不足时，会发生扩容：

1. 申请更大的内存
2. 复制旧元素
3. 释放旧内存

这个过程代价较高。

例如：

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

可能发生多次内存重新分配。

reserve() 预分配空间

为了避免频繁扩容，可以提前分配内存：

std::vector<int>vec;

vec.reserve(1000000);

这样可以减少：

• 内存重新分配
• 元素复制
• 性能损耗

这是工程开发中非常重要的优化技巧。

遍历 vector

使用下标

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

使用迭代器

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

范围 for 循环

for (int element : vec) {
    std::cout << element << " ";
}

删除元素

删除第三个元素：

vec.erase(vec.begin() + 2);

例如：

1 2 3 4 5

删除 2 后：

1 3 4 5

其中：

3 4 5

都需要移动位置。

因此：erase() 的时间复杂度为 O(n)

vector 不适合的场景

• 频繁头部插入
• 频繁中间删除
• 超大对象频繁扩容

例如：

vec.insert(vec.begin(), 100);

这是一个较慢的操作。

迭代器失效

vector 扩容后，原来的内存地址可能失效。

例如：

std::vector<int>vec = {1, 2, 3};

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

这里的 it 可能已经失效。

因为 push_back() 可能导致重新分配内存。

这是 vector 最常见的坑之一。

clear() 的注意事项

vec.clear();

clear() 只会清空元素：

• size 变为 0
• capacity 可能仍然保留

也就是说：

clear() 不一定释放内存

如果希望释放内存：

std::vector<int>().swap(vec);

或者：

vec.shrink_to_fit();

push_back 和 emplace_back

现代 C++ 更推荐使用：

emplace_back()

例如：

vec.push_back(Person("Tom", 20));

可能产生临时对象。

而：

vec.emplace_back("Tom", 20);

会直接在 vector 内部原地构造对象。

通常效率更高。

vector 与数组的区别

vector 常见操作复杂度

使用示例

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int>scores = {85, 90, 78, 92};
    scores.push_back(88);
    std::cout << "所有成绩: ";
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;
    int total = std::accumulate(scores.begin(), scores.end(), 0);
    double average = total * 1.0 / scores.size();
    std::cout << "平均成绩: " << average << std::endl;
    scores.erase(scores.begin() + 2);
    std::cout << "删除后成绩: ";
    for (int score : scores) {
        std::cout << score << " ";
    }

    std::cout << std::endl;

    return 0;
}

输出结果：

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88