[GeekBand] STL与泛型编程(1)

时间:2024-11-14 11:37:56

在C++语法的学习过程中,我们已经对模板有了基本的了解。泛型编程就是以模板为工具的、泛化的编程思想。本篇文章介绍了一些在之前的文章中没有涉及到的一些模板知识、泛型编程知识和几种容器。关于模板的一些重复知识在这里就不再进行赘述。

一、关于模板的知识点补充

 

1. 函数模板的参数推导与显式指定

通常情况下,我们一般采用参数的自动推导方式去使用函数模板。在自动推导时,为了确保推导的正确性,C++不允许任何形式的隐式类型转换。

这个限制就导致了如下的情况:

template
<class T>

int max(const T &a,const T &b)

{

    return a>b?a:b;

}

如果按照自动推导的方式,想要对1和2.0(int型和double型)进行比较,编译器是做不到的。为了解决这一问题,有如下两种方案:

第一种方案是显式进行类型转换。即max(double(1),2.0 );

第二种方案是采用显式指定模板的实例化,可采用这种语法:max<double>(1,2.0);

2. 模板的调用与匹配

当涉及到重载和模板共存时,编译器采用如下的顺序进行调用:

非模板重载函数 > 模板 > 进行隐式类型转换后再调用非模板重载函数。

当我们想强制调用模板函数时,可以使用如下的语法:

    Function_name <> (a,b);

利用一对尖括号表示要求调用模板方法。

3. 模板头中的常量使用

考虑如下的模板头:

template<typename T =
int, size_t r =
1024>

其中的第二模板参数为一个size_t类型(其本质为int类型)的常量,在模板类中的使用可以理解成是一个宏定义。

这种写法的好处在于,例如,你在这个模板类中定义了一个大小为r的缓冲区并对其进行操作。

如果这里r不是模板参数,则由于普通的数组大小定义只能是固定的,只能够申请动态数组。然而如果使用了数字作为模板参数,则相当于在实例化的时候,r对于这个模板就是一个常量,因此可以写出类似于int a[r]之类的语句。

另外,这里还涉及到了模板实参的默认值。注意,无论是类型名还是模板常量,均可以设置默认值。

 

二、泛型编程基础知识

 

1. Traits(特性)

    Traits通常以一种抽象类的形式存在,用于提取出不同类型变量的共同特点。然后将这种特点应用到运算之中。

[GeekBand] STL与泛型编程(1)    首先考虑如下求和函数:

template<typename T>

T Sigma(const T* const a,int n)

{

    int rlt =
0;

    for(i=0;i<n;i++)

        rlt += a[i];

}

    表面上看,这个求和函数不存在什么问题,然而,当我们将这一求和函数应用到这样的场景时:

char a[10]
=
"zzzzzzzz";

cout << Sigma(a,10);

结果却不是'z'对应的ASCII的9倍,而小于这个值。其原因在于,char类型的变量只能表示0~255之间的数字,当结果大于255时,发生了数据溢出。显然,这不是我们在求和的过程中希望看到的结果。Char,short求和的返回类型至少应该是int,float返回类型应该是double,int返回类型应该是long……

对于这个函数来说,所谓的"特性"就是他们的数值属性,将这个属性提取出来,可以采用模板的特化的办法:

template
<typename T>
class Sigmatraits {};

template
<>
class Sigmatraits<char>{

    public:
typedef
int ReturnType

}

template
<>
class Sigmatraits<short>{

    public:
typedef
int ReturnType

}

//新的Sigma的定义

typename Sigmatraits<T>::ReturnType

Sigma(const T *
const a,int n)

{

typedef
typename Sigmatraits<T>::ReturnType ReturnType;

ReturnType S = ReturnType ();

for(int i=0;i<n;i++)

     S+=a[i];

return S;

}

注意新的Sigma的定义中,typename Sigmatraits<T>::ReturnType 是返回值的类型。

 

    这里需要解释一下上面的返回值类型中,typename关键字的作用。

    在作为模板参数时,typename和class关键字的作用是完全相同的,当typename不作为class的同义字使用时,考虑如下代码:

struct A{

    typedef
int bar;

}

template<class T>

void foo(const T & t)

{

    T::bar *p; //这里是定义了一个p?还是T::bar作为一个变量乘以p?

}

int main()

{

    A x;

    foo(x);

}

上述代码看似没有什么问题,但是实际上是无法编译通过的。这涉及到了函数模板的二次编译。第一次编译时,对于函数模板foo,编译器不知道T::bar是一个什么东西。究竟是一个变量名,还是一个类型名?对于这种情况,C++规定默认情况下,class::member 表示一个成员变量,因此对于foo函数,则产生了"使用了未定义的变量p"的错误。如果要求member表示一个类型名,则必须显式地声明其为typename类型,即:

void foo(const T & t)

{

    typename T::bar *p; //通过编译

}

2. 迭代器(Iterator)——指针的泛化

    在之前C++的学习中,已经对迭代器进行了一个初步的介绍,迭代器的使用方法与指针类似。

  • 迭代器是容器和算法的接口,算法通常要以迭代器作为参数。
  • 迭代器使算法和容器分离开,使算法不再依赖于数据结构(容器)。
  • 迭代器又使算法和容器粘合在一起,使算法能够应用于不同的容器。

对于一般的STL迭代器,有以下的方法:

*iter

 存取实际元素

iter->member

 读取实际元素的成员

++iter

 向前步进,传回新位置

iter++

 向前步进,传回旧位置

--iter

 退步(传回新位置)

iter--

 退步(传回旧位置)

iter1== iter2

 判断两个迭代器是否相等

TYPE(iter)

 复制迭代器(copy构造函数)

TYPE()

 产生迭代器(default构造函数)

iter1=iter2

 赋值

另外,对于可以随机存取的数据结构,其还具有如下随机存取操作:

iter[n]  

取索引位置为n的元素

iter += n

 向前跳n个位置

iter -= n  

向后跳n个位置

iter + n  

传回iter之后的第n个位置

n + iter  

传回iter之后的第n个位置

iter - n  

传回iter之前的第n个位置

iter1 - iter2  

传回iter1和iter2之间的距离

iter1 < iter2  

判断iter1是否在iter2之前

iter1 > iter2  

判断iter1是否在iter2之后

iter1 <= iter2

判断iter1是否不在iter2之后

iter1 >= iter2

判断iter1是否不在iter2之前

    在之后即将介绍的数据结构中,Vector的迭代器就是可随机存取的迭代器,而List的迭代器是不可随机存取的迭代器。

    3. 容器适配器(Adaptor)——由多能到专能

    

适配器是指,STL在自身的底层数据结构基础上,通过对一些功能的删减,使之成为更加具有针对性的容器。在STL中,指的是栈、队列、优先级队列这三种数据结构。

    

4. 内存分配器(Allocator)——管理容器的内存分配

    

各种容器的第二个参数就是内存分配器,通常情况下不需要特殊指定,只需要使用其默认参数即可。标准库中allocator类定义在头文件memory中,他将内存分配的过程和对象构造过程分离开来。allocator也是一个模板类,定义时需指明这个可以分配的对象类型,这样才能确定合适的内存大小与位对齐方法。例如:

allocator<string> alloc;
定义了一个可以分配string的allocator对象

auto
const p=alloc.allocate(n);
//分配n个未初始化的string内存

注意,allocator分配的内存都是未经过初始化的。可以简单的理解成,先将内存分配好,然后进行类似定位new的构造。

allocator<T> a

定义名为a的allocator对象,可以分配内存或构造T类型的对象。

a.allocate(n)

分配原始的构造内存以保存T类型的n个对象.

a.deallocate( p, n )

释放内存,在名为p的T*指针中包含的地址处保存T类型的n个对象。

a.construct( p, t )

在T*指针p所指向的内存中构造一个新元素。运行T类型的复制构造函数用t初始化该对象

a.destroy(p)

运行T*指针p所指向的对象的析构函数。

    使用Allocator的目的在于把容器的底层进一步抽离开来。

三、 几种常用的容器介绍

    1. Vector

    Vector是一个能够存放任意类型的动态数组,能够增加和压缩。

    Vector定义在<vector>中,使用时需要#include <vector>;

    1.1 创建方法

vector c               

创建一个空的vector。

vector c1(c2)          

复制一个vector

vector c(n)            

创建一个vector,含有n个数据,数据均已缺省构造产生

vector c(n, elem)      

创建一个含有n个elem拷贝的vector

vector c(beg,end)      

创建一个含有n个elem拷贝的vector

    其中第五种方法,beg和end是两个迭代器/指针,它可以用来把传统的数组存储到容器中,例如:

int a[10]
=
{1,2,3,4,5,6,7,8,9,0};

vector x(a,a+10);

    1.2 其他成员函数

c.assign(beg,end)

c.assign(n,elem)

将[beg; end)区间中的数据赋值给c。

将n个elem的拷贝赋值给c。

c.at(idx)  

传回索引idx所指的数据,如果idx越界,抛出out_of_range。

c.back()

传回最后一个数据,不检查这个数据是否存在。

c.begin()

传回迭代器中的第一个数据地址。

c.capacity()

返回容器中数据个数。

c.clear()

移除容器中所有数据。

c.empty()

判断容器是否为空。

c.end()

指向迭代器中末端元素的下一个,指向一个不存在元素。

c.erase(pos)

c.erase(beg,end)

删除pos位置的数据,传回下一个数据的位置。

删除[beg,end)区间的数据,传回下一个数据的位置。

c.front()

传回第一个数据。

c.insert(pos,elem)

c.insert(pos,n,elem)

c.insert(pos,beg,end)

在pos位置插入一个elem拷贝,传回新数据位置。

在pos位置插入n个elem数据。无返回值。

在pos位置插入在[beg,end)区间的数据。无返回值。

c.max_size()

返回容器中最大数据的数量。

c.pop_back()

删除最后一个数据。

c.push_back(elem)

在尾部加入一个数据。

c.rbegin()

传回一个逆向队列的第一个数据。

c.rend()

传回一个逆向队列的最后一个数据的下一个位置。

c.resize(num)

重新指定队列的长度。

c.reserve()

保留适当的容量。

c.size()

返回容器中实际数据的个数。

c1.swap(c2)

swap(c1,c2)

交换两个容器中的全部元素。

    几点说明:

1. C.at(idx)方法进行越界检查,而C[idx]不进行越界检查。一般情况下,最好使用不进行检查的方式,这是出于效率考虑的,异常检测的效率过低。

2. 其中的"位置"指的都是迭代器。

3. vector的迭代器是随机存取迭代器。

    1.3 erase与remove_if()的联合使用

    remove_if 定义在<algorithm>中,使用前需要先进行包含。

    例如如下代码:

v.erase(remove_if(v.begin(),v.end(),ContainsString(L"C++")),v.end())

    这个代码删除了v中所有包含"C++"子串的元素。

remove_if(iter1,iter2,bool)函数并不是真正的删除函数,他是在两个迭代器的中间部分找到所有bool为1的元素,并将其移动至尾部,随后返回第一个满足条件的元素的迭代器。然后,erase方法将这个迭代器一直到v.end()中间的所有元素删除,也就实现了按照筛选条件进行删除的要求。

 

另外的两个常用基本容器List、deque和Vector的操作基本上是一样的,只不过是实现方式有所不同,导致各个操作的效率不相同;此外,另两个基本容器具有后插入的push_front和pop_front操作。