OOP 学习笔记（7）——模板与 STL 初步

wzf2000
2020年3月23日

OOP 学习笔记（7）——模板与 STL 初步

模板与 STL 初步

函数模板和类模板

模板引入

下列函数的实现往往是相似的，却需要定义多次：

void sort(int *data, int len);
void sort(float *data, int len);
void sort(ClassName *data, int len);

因此需要一劳永逸的方法，也就是模板。

函数模板

有些算法实现与类型无关（比如重载了 < 的类型的排序算法，见上），所以可以将函数的参数类型也定义为一种特殊的参数，也就得到了函数模板。

定义方法：

template <typename T>
ReturnType Function(Args);

特别注意，typename 也可用 class 代替。

注：typename 除了用于定义模板以外，还可用于强调后面是一个类型名，在类型名是 qualified dependent name 时，如果不用 typename 指定，容易被编译器解释成其它含义。

一个实例是：

template <typename T>
T sum(T a, T b)
{
    return a + b;
}

函数模板的原理

函数模板在调用时，编译器会根据实际参数的类型。实例化一个普通函数。

所以形式上调用一个函数模板和普通函数无区别，比如：

cout << sum(4, 3) << sum(1.34, 2.56);

但是需要调用类型满足函数的要求。

比如上例边不能这样使用：

cout << sum(4, 1.345); // 编译错误

但是可以手工指定调用类型来调用（会进行自动类型转换）：

sum<int>(4, 1.345);

也就是说，不指定类型时，调用函数模板不会进行自动类型转换，相反如果指定了类型，则与普通函数几乎无异。

类模板

在定义类时也可以将一些类型信息抽取出来，用模板参数来替换，从而使类更具有通用性。

这种类被称为类模板，如：

#include <iostream>
using namespace std;
template <typename T>
class A
{
    T data;
public:
    void print()
    {
        cout << data << endl;
    }
};
int main()
{
    A<int> a;
    a.print();
    return 0;
}

同样 typename 也可换为 class。

上面的例子也展示了如何实例化类模板，即 ClassName<Type>。

类模板中成员函数类外定义

若成员函数使用类外定义，则上述代码需改为：

#include <iostream>
using namespace std;
template <typename T>
class A
{
    T data;
public:
    void print();
};
template <typename T>
void A<T>::print()
{
    cout << data << endl;
}
int main()
{
    A<int> a;
    a.print();
    return 0;
}

类模板的模板参数

主要分为两类：

类型参数：使用 typename 或 class 标记。
非类型参数：整数，枚举，指针（指向对象或函数），引用（引用对象或引用函数）。整数型较为常用。下面是一个例子。

template <typename T, unsigned size>
class array
{
    T elems[size];
    //...
};

array<char, 10> array0;

这个例子中可以使用第二个参数控制成员 elems 数组的长度。

成员函数模板

普通类的成员函数，也可以定义为模板函数，比如：

class normal_class
{
    int value;
public:
    template <typename T>
    void set (T const &v)
    {
        value = int(v);
    } // 在类内定义
    template <typename T>
    T get();
};
template <typename T>
T normal_class::get()
{
    return T(value);
} // 在类外定义

普通类模板的成员函数，也可有额外的模板参数，比如：

template <typename T0>
class A
{
    T0 value;
public:
    template <typename T1>
    void set (T1 const &v)
    {
        value = T0(v);
    } // 在类内定义
    template <typename T1>
    T1 get();
};
template <typename T0>
template <typename T1>
T1 A<T0>::get()
{
    return T1(value);
} // 在类外定义

特别注意类外定义不能写为：

template <typename T0, typename T1>

多个参数的类模板：

template<typename T0, typename T1>
class A {};

多个参数的函数模板：

template<typename T0, typename T1>
void func(T0 a1, T1 a2) {}

模板使用中通常可以自动推导类型，必要时也可以指定：

int main()
{
    A<int> a;
    a.set(5);      //自动推导5为整数类型
    double t = a.get<double>();    //手动指定返回值类型
    return 0;
}
// t = 5.0

函数模板特化

有时候，并不是每种类型都有完全统一的函数实现方法，所以对于一些类型，需要对模板进行特殊化处理，称之为模板特化。

对函数模板，若有多个模板参数，则特化时必须提供所有参数的特例类型，不能部分特化。但可以用重载来替代部分特化。

如下面这个函数模板：

template <typename T> T sum(T a, T b)

可以在函数名后用 <> 括号括起具体类型：

template<> char* sum<char*>(char* a, char* b)

也可由编译器自动推导出具体类型，函数名为普通形式：

template<> char* sum(char* a, char* b)

一个非部分特化而是重载的例子：

template<class T, class A>
T sum(const A& val1, const A& val2)
{
    cout << "using template" << endl;
    return T(val1 + val2);
}

template<class A>
int sum(const A& val1, const A& val2)
{
    cout << “overload" << endl;
    return int(val1 + val2);
} //不是部分特化，而是重载函数
int main() {
    float y = sum<float, float>(1.4, 2.4);
    cout << y << endl;
    int x = sum(1, 2);
    cout << x << endl;
}

运行结果为：

using template
3.8
overload
3

类模板特化

对于类模板，允许部分特化，即部分限制模板的通用性。

如通用模板为：

template<typename T1, typename T2>
class A { /*...*/ };

则可以部分特化为：

template<typename T1>
class A<T1, int> { /*...*/ };

也可全部特化为：

template<>
class A<int, int> { /*...*/ };

此处不举例。

模板原理

对模板的处理是在编译器进行的，每当编译器发现对模板的一种参数的使用，就生成对应参数的一份代码。

这意味着所有模板参数必须在编译器确定，不可以使用变量。

int n = 5;
myClass<n> a; //错误
const int n = 5;
myClass<n> b; //正确

同时这也带来了问题：模板库必须在头文件实现，不可以分开编译。

原因：

如果使用源代码分开编译，则编译模板库的源代码时，编译器并不知道这一模板库有哪些模板实例。
而编译模板实例时，又没有模板库的源代码来作生成。
因此会发生链接错误，没有生成对应模板参数的源代码。
当然如果只有单文件编译，可以在本文件中使用模板。

模板与多态

模板使用泛型标记，使用同一段代码关联不同但相似的特定行为，可以获得不同的结果，因此也是多态的一种体现。

但是模板的关联发生在编译期间，所以依然是静多态。

命名空间

引入命名空间的原因

为了避免在大规模程序的设计中，以及在程序员使用各类 C++ 库时，标识符的命名发生冲突，标准 C++ 引入了关键字 namespace（命名空间），可以更好地控制标识符的作用域。

标准 C++ 库（不包括标准 C 库）中所包含的所有内容（包括常量、变量、结构、类和函数等）都被定义在命名空间 std（standard 标准）中。

比如包括：

cout、cin
vector、set、map、sort()

命名空间的基本使用

定义：

namespace A
{
    int x, y;
    void func()
    {
        std::cout << "This is a function!" << std::endl;
    }
    // ...
} // 注意不需要加 ';'

使用命名空间：

A::x = 3;
A::y = 6;
A::func();

可以使用 using 声明简化命名空间使用：

使用整个命名空间：所有成员均可使用。
```
using namespace A;
x = 3;
y = 6
```
C++
使用部分成员：所选成员可直接使用。
```
using A::x;
x = 3;
A::y = 6;
```
C++
但任何情况下，都不应该出现命名冲突。

STL 初步

STL 简介

标准模板库（Standard Template Library，缩写为 STL），是一个 C++ 软件库，大量影响了 C++ 标准程序库但并非是其的一部分。

其中包含 $4$ 个组件，即算法、容器、函数、迭代器。

STL 基于模板编写，其关键理念是，将“在数据上执行的操作”与“要执行操作的数据”分离。

随着 C++ 标准的发展，STL 也不断扩充。

具体发展可以自己查询了解。

STL 容器

容器是包含、放置数据的工具，通常为数据结构。

包括：

简单容器（simple container），如 pair，tuple。
序列容器（sequence container），如 vector，list。
关系容器（associative container），如 map，set。

STL 容器：`pair`

头文件为 <utility>。

最简单的容器，由两个单独数据组成。

template <class T1, class T2>
struct pair
{
    T1 first;
    T2 second;
    // 若干其它函数
};

通过 first、second 两个成员变量获取数据。

std::pair<int, int> t;
t.first = 4, t.second = 5;

创建一个 pair 可以使用函数 make_pair() 函数：

auto t = std::make_pair("abc", 7.8);
// 可以自动推导成员类型

支持小于、等于等比较运算符。

先按 first 比较，后按 second 比较。
要求成员类型支持比较（实现了比较运算符重载）。

STL 容器：`tuple`

头文件为 <tuple>。

C++ 11 新增，pair 的扩展，由若干成员组成的元组类型。

template <class ... Types> class tuple;

注：此处是不确定数量模板参数的模板使用方法。

通过 std::get() 函数获取数据：

v0 = std::get<0>(tuple1);
v1 = std::get<1>(tuple1);

其下标需要在编译时确定：不能设定运行时可变的长度，不可当做数组。

创建可以使用 make_tuple() 函数：

auto t = std::make_tuple("abc", 7.8, 123, '3');

配合 tie() 函数也可以这样使用：

std::tie(x, y, z) = std::make_tuple("abc", 7.8, 123);

等价于：

x = "abc";
y = 7.8;
z = 123;

除此之外还可以使用 forward_as_tuple() 函数，会返回右值引用的元组：

#include <iostream>
#include <tuple>
#include <string>

void print_pack (std::tuple<std::string&&,int&&> pack)
{
    std::cout << std::get<0>(pack) << ", " << std::get<1>(pack) << '\n';
}

int main()
{
    std::string str ("John");
    print_pack (std::forward_as_tuple(str+" Smith",25));
    print_pack (std::forward_as_tuple(str+" Daniels",22));
    return 0;
}

tuple 可以用于函数多返回值的传递：

#include <tuple>
std::tuple<int, double> f(int x)
{
    return make_tuple(x, double(x)/2);
}
int main()
{
    int xval;
    double half_x;
    std::tie(xval, half_x) = f(7);
    return 0;
}

作为 tuple 的特例，pair 可用于两个返回值的传递。

除此之外，pair 在 map 中大量使用。

STL 容器：`vector`

头文件为 <vector>。

vector 是会自动扩展容量的数组，以循序（Sequential）的方式维护变量集合。

template <class T, class Allocator = std::allocator<T> >
class vector;

STL 中最基本的序列容器，提供有效、安全的数组以替代 C 语言中原生数组。

允许直接以下标访问（高效）。

创建：

std::vector<int> x;

获取当前数组长度：

x.size();

清空：

x.clear();

在末尾添加或删除（高速）：

x.push_back(1);
x.pop_back();

在中间添加或删除（使用迭代器，低速）：

x.insert(x.begin() + 1, 5);
x.erase(x.begin() + 1);

注：

C++11 后建议使用 emplace_back() 和 emplace() 代替 push_back()，其可以直接利用参数调用类的对应构造函数。

迭代器

一种检查容器内元素并遍历元素的数据类型。

提供一种方法顺序访问一个聚合对象中的各个元素，而又不需暴露该对象的内部表示。

为遍历不同的聚合结构（需要拥有相同基类）提供一个统一的接口。

使用上类似指针。

迭代器：以 `vector` 为例

定义：

template<class T, class Allocator = std::allocator<T>> 
class vector
{
    class iterator
    {
        //...
    }
};

定义迭代器：

std::vector<int>::iterator iter;

定义了一个名为 iter 的变量，它的数据类型是由 vector<int> 定义的 iterator 类型。

begin() 函数：x.begin()，返回 vector 中的第一个元素的迭代器。

end() 函数：x.end()，返回 vector 中最后一个元素之后的位置的迭代器。

begin() 和 end() 函数构成所有元素的左闭右开区间。

下一个元素：++iter;。

上一个元素：--iter;。

下 $n$ 个元素：iter += n;。

上 $n$ 个元素：iter -= n;。

访问元素值——解引用运算符 *：*iter = 5;。

解引用运算符返回的是左值引用。

迭代器移动：与整数作加法，iter += 5;。

元素位置差：迭代器相减，int dist = iter1 - iter2;。

其本质都是重定义运算符。

遍历 vector：

for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) // use *it

C++11 中常使用 auto 简化代码：

for (auto it = vec.begin(); it != vec.end(); ++it) // use *it

当然也可以使用按范围遍历：

for (auto x : vec) // use x

迭代器：失效

当迭代器不再指向本应指向的元素时，称此迭代器失效。

vector 中：

调用 insert() 或 erase() 后，所修改位置之后的所有迭代器失效。（原先的内存空间存储的元素被改变）

std::vector<int> vec = {1,2,3,4,5};
auto first = vec.begin();
auto second = vec.begin() + 1;
auto third = vec.begin() + 2;
auto ret = vec.erase(second);
// first 指向 1，second 和 third 失效
// ret 指向 3

调用 push_back() 等修改 vector 大小的方法时，可能会使所有迭代器失效。（长度达到一定程度之后，可能会造成数组的整体移动，导致所有的内存地址发生改变）

迭代器是否会失效，和实现容器的数据结构有关。

在文档中，容器的修改操作有一项 Iterator validity，表示该操作是否会引发迭代器失效。

一个绝对安全的准则：在修改过容器后，不使用之前的迭代器。

若一定要使用，查文档确定迭代器是否依然有效。

STL 容器：`vector` 原理

vector 是会自动扩展容量的数组。

除了 size，另外保存 capacity 即最大容量限制。

如果 size 达到了 capacity，则另外申请一片 capacity * 2 的空间，并整体迁移 vector 内容。

其时间复杂度为均摊 $O(1)$ 。

整体迁移过程使得所有迭代器失效。

由此可以理解上面长度改变可能导致的失效。

STL 容器：`list`

list 是链表容器（底层实现是双向链表）。

其不支持下标等随机访问，但支持高速地在任意位置插入或删除数据。

其访问主要依赖迭代器，且除了指向删除的元素的迭代器外，任何操作不会导致迭代器失效。

具体命令可以自己查文档。

STL 容器：`set`

不重复元素构成的无序集合。

template <class Key, class Compare = std::less<Key>, class Allocator = std::Allocator<Key> >
class set;

内部按大小顺序排列，比较器由函数对象 Compare 完成。

注：其底层实现为红黑树（一种二叉平衡树），所以大多数操作的时间复杂度均为 $O(\log n)$ 。

定义：

std::set<int> s;

插入：

s.insert(1);

查询：

s.find(1); // 返回迭代器

删除：

s.erase(s.find(1)); // 导致迭代器失效

统计：

s.count(1); // 1 的个数，总是 0 或 1

注：由于 set 中相同元素只能存在一个，如果需要可重复元素的数据结构，可以使用 multiset，相应的成员函数也较为类似，可以自己尝试或查询文档。

STL 容器：`map`

map 是一个关联数组，每个元素由两个数据项组成，map 将一个数据项映射到另一个数据项中。

其定义为：

template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T> >
class map;

map 的值类型为 pair<Key, T>。

map 中的元素 Key 互不相同，需要 Key 存在比较器。

可以通过下标访问（即便 Key 不是整数）：

std::map<std::string,int> s;
s["oop"] = 1;

下标访问时如果元素不存在，则创建对应元素。

也可以使用 insert() 函数进行插入：

s.insert(std::make_pair(std::string("oop"), 1));

查询：find() 函数，仅需要提供 Key 值，返回迭代器。

统计：count() 函数，仅需要提供 Key 值，返回 $0$ 或 $1$ 。

删除：erase() 函数，使用迭代器，导致被删除元素的迭代器失效。

以上部分与 set 类似。

map 常用于过大的稀疏数组或以字符串为下标的数组。

注：map 的底层实现也是红黑树。

oop 教程

201 次浏览

No Comments