STL的中心思想就是将容器和算法分开,分别独立设计和泛型化,然后通过迭代器来连接算法和容器。容器和算法利用C++ 中class template和function template机制来泛型化。设计STL的算法时,传递过来的参数往往是迭代器类型的参数,迭代器引用的容器数据类型当前是不确定的(template是在编译时确定数据类型的),当算法中需要利用迭代器所指对象的类型来定义或声明变量时,就会出现小小的困扰,因为C++中没有提供提取对象数据类型的操作(即使利用RTTI性质中的typied()来获取类型名,也不能用来做变量声明和定义之用)。这时我们就需利用function template的参数推导机制。下面举个简单例子来详细讨论一下:
//模板函数
template <class I>
void func(I iter){
...
}
这时想要在模板函数func里面定义一个迭代器引用的对象该怎么办?像我这样的初学者可能马上会想到容器中使用的方法,将该对象的类型也泛化,增加一个模板参数,即:
template <class I, class T>
void func(I iter){
T object;
...
}
可是这样可以吗?在容器的定义中如果要泛化类型,我们可以这样
template <class I, class T>
class Container{
...
T tObject;
I iObject;
typedef T* iter;
};
然后声明一个类型:
Container<int*, int> c;
而client在调用STL算法时并不需要了解容器的具体型别,因为它们是在容器声明时就已经设置好了,只需传入容器相应的迭代器。如果调用我们改进的func,编译时就会报错—— no matching function for call to 'func'。T类型是不确定的,因为T类型没有通过某种途径传递一个明确的类型过来。
如果这样像容器定义一样使用function template,我们调用
func<int*, int>(c.getIter()); //这样能行吗?确实可以编译通过,但感觉调用时不顺畅也很奇怪,也违背了STL设计的初衷。
那么该怎样解决这个问题呢?
其实STL中为迭代器指向对象的类型提供了专门技术——Traits编程技术,这里不作介绍,详见参考资料。template 参数推导机制只是简单的解决了部分 “迭代器所指对象的型别” 问题。利用参数推导机制,可以这样实现:
template <class I, class T>
void func_helper(I iter, T t){
T tmp;
... //这里做func原本该做的工作
}
template <class I>
void func(I iter){
func_helper(iter, *iter); //*iter作为附加参数
}
void caller(){
func(c.getIter());
}
可见func_helper中T的类型就是*iter类型,利用参数推导机制解决了上述问题。下面以插入排序为例,通过参数推导来解决实际问题,详细介绍下template function的实现。
插入排序的一般实现:
//普通版本
template<class T>
void insertSort(vector<T>& v){
int j;
for(int i = 1; i < v.size(); ++i)
{
T tmp = v[i];
for(j = i; j > 0 && tmp < v[j-1]; --j)
v[j] = v[j-1];
v[j] = tmp;
}
}
下面再按照STL算法的形式改写,STL sort的实现为带迭代器的双参数和附加函数子的三参数的两种形式。那么我们要:
(1)编写一个双参数和三参数的形式(为什么不能用一个带有默认参数值的三参数实例来实现呢?考虑一下),双参数实 际是三参数的一个特化,因此考虑用二参数函数调用三参数来实现。
(2)数组的访问由直接传入容器变为传入容器的迭代器;
(3)插入排序中tmp的类型和less<>仿函数的具体化要用到参数推导机制。
//STL版本
template<class I, class Cmp>
void insertSort(const I& begin, const I& end, Cmp lessThan);
template <class I, class T>
void _insertSort(const I& begin, const I& end, const T t);
template<class I, class T, class Cmp>
void _insertSort(const I& begin, const I& end, Cmp lessThan, const T& t);
template <class I>
void insertSort(const I& begin, const I& end){
if(begin != end)
_insertSort(begin, end, *begin); //这里要取begin所指向的值,避免越界,所以先判断
}
template <class I, class T>
void _insertSort(const I& begin, const I& end, const T t){
insertSort(begin, end, less<T>()); // 双参数调用三参数,less<T>中的类型也利用参数推导获取
}
template<class I, class Cmp>
void insertSort(const I& begin, const I& end, Cmp lessThan){
if(begin != end)
_insertSort(begin, end, lessThan, *begin);
}
//算法的具体实现
template<class I, class T, class Cmp>
void _insertSort(const I& begin, const I& end, Cmp lessThan, const T& t){
I j;
for(I i = begin+1; i != end; ++i){
T tmp = *i; //通过参数推导确定T类型
for(j = i; j != begin && lessThan(tmp, *(j-1)); --j)
*j = *(j-1);
*j = tmp;
}
}
上面就是个人对参数推导机制的粗浅理解,要深入了解迭代器指向对象的类型可参考《STL源码剖析》,以上代码来自于下面参考文献。代码都经过调试,可以正常运行。这里做一个学习过程的标记。
参考文献:
[1] 《STL源码剖析》
[2] 《数据结构与算法分析C++描述》
分享到:
相关推荐
在给定的“数据排序和查找——STL”主题中,我们将深入探讨STL如何帮助我们实现不同的排序和查找操作。这里主要涉及了选择排序、冒泡排序以及几种查找算法,包括二分查找、顺序查找和双向顺序查找。 1. **STL排序...
以题目《Orders》为例,该题要求对一系列订单进行处理,具体任务是在已知订单商品种类的情况下,计算出所有可能的仓库访问序列。此题可以运用STL中的算法来解决。 1. **输入解析**: - 输入中给出了一串小写字母,...
STL 之栈(csdn)————程序 STL(Standard Template Library)中的栈(Stack)是一种容器适配器,提供了FILO(先进后出)数据结构的实现。栈是一种 Last-In-First-Out(LIFO)的数据结构,即最后入栈的元素最先...
这里我们将深入探讨标题和描述中提到的几种排序算法,包括STL排序、选择排序、冒泡排序、快速排序、合并排序、插入排序、堆排序以及计数排序。 1. **STL排序**:C++标准模板库(STL)中的`std::sort`函数是基于...
在这个项目中,他与Meng Lee共同开发了一个庞大的库——标准模板库(STL),旨在定义一系列通用算法的同时保证效率。随着时间的发展,STL已经成为国际上广泛接受的一种新的编程范式。 ##### 1.3 STL 和 ANSI/ISO ...
STL,全称为Standard Template Library,是C++编程语言中不可或缺的部分,由Alexander Stepanov、Meng Lee和David R Musser共同开发。这个库包含了数据结构(容器)、算法和迭代器,旨在提供高效的编程工具,减少...
stl_function.h
STL(Standard Template Library,标准模板库)是C++编程语言中的一个重要组成部分,它是通过模板机制实现的泛型编程实例。STL的核心思想是将算法与数据结构分离,提供了一种高效且灵活的方式来处理各种数据操作。...
STL(Standard Template Library)中,set和map都是自动排序的,但是如何修改其排序准则呢?本文将对STL中的set和map进行详细的讲解,并提供修改排序准则的思路和实现代码。 一、STL中的set和map排序 在STL中,set...
STL(Standard Template Library,标准模板库)是C++编程语言中的一个重要组成部分,它提供了一系列高效、可重用的数据结构和算法。这个“STL中文手册 doc文档”显然是为了解决C++程序员在使用STL时遇到的问题,帮助...
本文将深入探讨三种常见的排序算法:堆排序、插入排序和优先队列排序(也称为堆排序的一种变体),并主要关注它们在大规模数据集上的运行时间性能。 首先,我们来看插入排序。插入排序是一种简单直观的排序算法,它...
在C++编程语言中,数据结构的实现常常借助于标准模板库(Standard Template Library,简称STL)。STL是C++库的一部分,提供了各种容器、迭代器、算法和函数对象,极大地简化了复杂数据结构的编程。 STL中的容器是...
在C++编程中,STL(Standard Template Library,标准模板库)是不可或缺的一部分,它提供了一种高效且灵活的方式来处理各种数据结构和算法。在这个专题里,我们将深入探讨C++STL中的排序算法,主要关注如何使用它们...
STL(Standard Template Library)是C++编程中非常重要的一部分,对于C++编程者来说, STL 的排序准则是一个非常重要的概念。今天,我们将讨论STL自定义排序准则的实现方法。 首先,我们来看一下STL中的排序准则。...
STL( Standard Template Library)是C++标准模板库,提供了大量通用容器、算法和迭代器,以满足大多数编程需求。STL源码剖析是深入了解C++语言和STL库的内部实现机制的重要步骤。 一、STL容器 STL容器是STL库的...
STL中的排序算法围绕着一个核心概念——迭代器(iterator),尤其是随机访问迭代器(Random Access Iterator)。这允许算法快速定位到序列中的任意位置,提高排序效率。所有排序算法接受一对迭代器作为参数,分别...
STL(Standard Template Library,标准模板库)是C++编程语言中的一部分,它提供了一组高效、灵活且可重用的容器、算法和迭代器。在这个案例中,我们特别关注的是`vector`容器,它是STL中最常用的一种动态数组。`...
STL(Standard Template Library,标准模板库)是C++编程中不可或缺的一部分,它提供了一系列高效、灵活的容器、迭代器和算法,极大地提高了代码的可复用性和效率。在这个详述STL排序的文章中,作者Winter ZT深入...
在这个“用STL实现基数排序算法”的项目中,我们可以看到如何利用STL的一些工具来简化基数排序的实现。首先,基数排序通常涉及到对数字每一位的处理,这可以通过迭代或递归的方式完成。在C++中,可以使用STL的迭代器...