算法的泛化过程

小鱼儿 2022-08-21 11:45 105阅读 0赞

读STL源码分析

前言  
**再好的编程技巧，也无法让一个笨拙的算法起死回生。**  
**选择了错误的算法，便注定了失败的命运。**

何为算法  
**以有限的步骤，解决逻辑或数学上的问题，Algorithms!**

算法分析  
**空间复杂度、时间复杂度**

分类  
**质变算法：会改变操作对象的值**，例如拷贝、互换。  
**非质变算法：不改变操作对象的值**，例如查找、匹配。

算法的泛化过程

举例说明：  
从一个array中寻找特定的值：

我们的直觉反应是：

int *find(int *array,int size,int target)
    {
        for(int i=0;i<size;i++)
        {
            if(array[i]==target)
                break;
        }
        return &(array[i]);
    }

上面的做法暴露了容器太多的实现细节，因此太过依赖特定容器。  
让find()接收两个指针作为参数：

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

为了不仅仅适用于array，我们使用模板：

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

上面的函数虽然能适用大部分容器，但是还还不能用于list，进一步演化：  
在C++中，上述操作符或操作行为都可以被重载。如果我们以一个原生指针指向某个list，则对该指针进行“++”操作并不能指向下一个串行节点，但如果哦我们设计一个class，拥有原生指针的行为，并使其”++“操作指向list的下一个节点，那么find()就可以施行于list容器上了。这便是迭代器（iterator）的观念。迭代器是一种行为类似指针的对象，下面将find()函数内的指针以迭代器取代

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