OOP 学习笔记(7)——模板与 STL 初步

OOP 学习笔记(7)——模板与 STL 初步

Contents

模板与 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;
}

类模板的模板参数

主要分为两类:

  • 类型参数:使用 typenameclass 标记。
  • 非类型参数:整数,枚举,指针(指向对象或函数),引用(引用对象或引用函数)。整数型较为常用。下面是一个例子。
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 库)中所包含的所有内容(包括常量、变量、结构、类和函数等)都被定义在命名空间 stdstandard 标准)中。

比如包括:

  • coutcin
  • vectorsetmapsort()

命名空间的基本使用

定义

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
    
  • 使用部分成员:所选成员可直接使用。
    using A::x;
    x = 3;
    A::y = 6;
    
  • 但任何情况下,都不应该出现命名冲突。

STL 初步

STL 简介

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

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

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

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

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

STL 容器

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

包括:

  • 简单容器(simple container),如 pairtuple
  • 序列容器(sequence container),如 vectorlist
  • 关系容器(associative container),如 mapset

STL 容器:pair

头文件为 <utility>

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

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

通过 firstsecond 两个成员变量获取数据。

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 可用于两个返回值的传递。

除此之外,pairmap 中大量使用。

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 的底层实现也是红黑树。

 

点赞 0

No Comments

Add your comment