linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

算法的泛化过程

时间:2017-02-15  来源:未知  作者:linuxsir首页

  将一个叙述完整的算法转化为程序代码,不是什么难事。然而,如何将算法独立与其所处理的数据结构之外,不受数据结构的羁绊呢?换个说法,如何将我们所写的程序算法适用于任何(或者大部分)未知的数据结构(比如array,vector,list等)呢?

  关键在于,只要把操作对象的型别加以抽象化,把操作对象的标示法和区间目标的移动行为抽象化,整个算法也就在一个抽象层面上工作了。整个过程称为算法的泛型化(generalized),简称泛化。

  以简单的循序查找为例,编写find()函数,在array中寻找特定值。面对整数array,写出如下程序:

int* find(int* arrayHead, int arraySize, int value)
{
    int i=0;
    for (; i<arraySize; ++i)
    {
        if (arrayHead[i] == value)
        {
            break;
        }
    }

    return &(arrayHead[i]);
}

  该函数在某个区间内查找value。返回的是一个指针,指向它所找到的第一个元素;如果没有找到,就返回最后一个元素的下一位置(地址)。

  “最后一个元素的下一位置”称为end。为什么不返回null?因为,end指针可以对其他种类的容器带来泛型效果,这是null所无法达到的。事实上一个指向array元素的指针,不但可以指向array内部任何位置,也可以指向array尾端以外的任何位置。只不过当指针指向array尾端以外的位置时,它只能用来与其他array指针相比较,不能提领(dereference)其值。

    const int arraySize = 7;
    int ia[arraySize] = {0, 1, 2, 3, 4, 5, 6};
    int* end = ia + arraySize;

    int * ip = find(ia, sizeof(ia)/sizeof(int), 4);
    if (ip == end)
    {
        cout<<"4 not found"<<endl;
    }
    else
    {
        cout<<"4 found. "<<*ip<<endl;
    }

  上述find()函数写法暴露了太多的实现细节(例如arraySize),为了让find()适用于所有类型的容器,其操作应该更抽象化些。让find()接受两个指针作为参数,标示一个操作区间:

int* find(int* begin, int*end, int value)
{
    while(begin !=end && *begin != value)
        ++begin;

    return begin;
}

  由于find()函数之内并无任何操作是针对特定整数array而发的,所以我们可以把它改成一个template:

template<typename T>
T* find(T* begin, T* end, const T& value)
{
    // 注意,以下用到了operator!=, operator*, operator++
    while (begin != end && *begin != value)
        ++begin;

    // 注意,以下返回操作用会引发copy行为
    return begin;
}

  注意数值传递由pass by value改为pass by reference const, 因为value的型别可为任意,对象一大,传递成本便会提升。

  在上述代码中,传入的指针必须支持以下四种操作行为:

  • inequality 判断不相等
  • dereferencelm 提领
  • prefix increment 前置式递增
  • copy 复制

  上述操作符可以被重载(overload),find()函数就可以从原声(native)指针的思想框框中跳脱出来。我们可以设计一个class,拥有原生指针的行为,这就是迭代器(iterator):

template<typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
    while(begin != end && *begin != value)
        ++begin;

    return begin;
}

  这便是完全泛型化的find()函数。

来自:STL源码剖析

STL源码剖析简体中文完整版(高清晰扫描带目录)PDF 下载见 http://www.linuxidc.com/Linux/2016-04/129761.htm

友情链接