4. STL学习笔记--算法

我不是女神ヾ 2022-04-12 20:12 268阅读 0赞

一、实验内容

本次实验主要讲述 STL 常用算法和基本算法，算法在日常的开发使用中能够提高不少的开发效率。

1.1 知识点

*  lambda 表达式
 *  常见基本算法

1.2 实验环境

*  g++
 *  ubuntu 16.04

1.3 代码获取

可以通过以下链接获取本课程的源码内容，本次实验内容主要包含在文件`Algorithm.h`。

//获取代码
    wget http://labfile.oss.aliyuncs.com/courses/1166/mySTL.zip
    
    //解压文件到Code目录
    unzip -q mySTL.zip -d ./Code/

二、lambda表达式定制操作

**泛型算法中的定制操作**

很多算法都会比较输入序列中的元素以达到排序的效果，通过定制比较动作，可以控制算法按照编程者的意图工作。 这里我们用排序算法举例。

*  普通排序算法，这样的排序算法只能按照从小到大排序，很多时候是不适用的。

template<class RandomIterator>
    void sort(RandomIterator first, RandomIterator last){
        if (first >= last || first + 1 == last)
            return;
        if (last - first <= 20)//区间长度小于等于20的采用冒泡排序更快
            return bubble_sort(first, last, pred);
            auto mid = mid3(first, last - 1, pred);
            auto p1 = first, p2 = last - 2;
            while (p1 < p2){
            while (pred(*p1, mid) && (p1 < p2)) ++p1;
                   while (!pred(*p2, mid) && (p1 < p2)) --p2;
                if (p1 < p2){
                    swap(*p1, *p2);
                }
            }
        swap(*p1, *(last - 2));//将作为哨兵的mid item换回原来的位置
        sort(first, p1, pred);
        sort(p1 + 1, last, pred);
    }

*  排序算法的定制操作,普通排序算法只能由小到大排序，并不智能。二排序算法的定制操作，次函数多了一个类型 BinaryPredicate，可以用来定制规则（如从大到小），增加了实用性。

template<class RandomIterator, class BinaryPredicate>
    void sort(RandomIterator first, RandomIterator last, BinaryPredicate pred){
        if (first >= last || first + 1 == last)
            return;
        if (last - first <= 20)//区间长度小于等于20的采用冒泡排序更快
            return bubble_sort(first, last, pred);
        auto mid = mid3(first, last - 1, pred);
        auto p1 = first, p2 = last - 2;
        while (p1 < p2){
            while (pred(*p1, mid) && (p1 < p2)) ++p1;
            while (!pred(*p2, mid) && (p1 < p2)) --p2;
            if (p1 < p2){
                swap(*p1, *p2);
            }
        }
        swap(*p1, *(last - 2));//将mid item换回原来的位置
        sort(first, p1, pred);
        sort(p1 + 1, last, pred);
    }

谓词

*  谓词相当于一个动作（将要干什么），比如有一个需求，希望从大到小排序，则可以先定义一个谓词（函数）。

bool comp(const int& v1,const int& v2)
    {
        return v1 > v2;
    }

*  将这个函数传递给 sort 算法，就可以按照从大到小排序。

sort(v.begin(),v.end(),comp);

lambda表达式

前面的例子中，定义了一个函数传递给 sort 算法。这个函数可以重复使用还好，如果只是使用一次的话就显得比较麻烦，而且浪费了空间。这种情况下就可以使用 lamada 表达式。lamada 表达式相较于谓词，它没有定义函数（没有函数名）。

sort(v.begin(),v.end(),[]comp(const int& v1,const int& v2){return v1 > v2;});//这种没有定义函数的指定动作（谓词）的方式就是lambda表达式。

三、STL算法

算法部分主要包含在头文件 "Algorithm.h" 、 "Functional” 和 “numeric ” 中。

*  "Algorithm.h"是所有 STL 头文件中最大的一个，其中常用到的功能范围涉及到比较、 交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
 *  "Functional”中则定义了一些模板类，用以声明函数对象，前面实验已经讲到。
 *  “Numeric ” 则包含一些数值运算操作，这个会在 STL 数值算法中讲到。

STL 算法大大小小差不多有 70+，下面列举一些我们实验需要常用的。

首先在 `include` 目录下创建 `Algorithm.h`。

*  find: 利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较,当匹配时,结束搜索,返回该元素的一个迭代器。用于查找。

函数原型:

template <class InputIterator, class T>
    InputIterator find(InputIterator first, InputIterator last, const T& val){
        for (; first != last; ++first){
            if (*first == val)
                break;
        }
        return first;
    }

*  sort: 以升序重新排列指定范围内的元素,重载版本使用自定义的比较操作。用于排序。

函数原型:

template<class RandomIterator>
    void sort(RandomIterator first, RandomIterator last){
            return sort(first, last, less<typename iterator_traits<RandomIterator>::value_type>());
    }
    
    template<class RandomIterator, class BinaryPredicate>
    void sort(RandomIterator first, RandomIterator last, BinaryPredicate pred){
        if (first >= last || first + 1 == last)
            return;
        if (last - first <= 20)//区间长度小于等于20的采用冒泡排序更快
            return bubble_sort(first, last, pred);
        auto mid = mid3(first, last - 1, pred);
        auto p1 = first, p2 = last - 2;
        while (p1 < p2){//快速排序
            while (pred(*p1, mid) && (p1 < p2)) ++p1;
            while (!pred(*p2, mid) && (p1 < p2)) --p2;
            if (p1 < p2){
                swap(*p1, *p2);
            }
        }
        swap(*p1, *(last - 2));//将作为哨兵的mid item换回原来的位置
        sort(first, p1, pred);
        sort(p1 + 1, last, pred);
    }

*  swap: 交换存储在两个对象中的值。

函数原型:

template <class RandomAccessIterator, class Compare>
    void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp){
        mySTL::swap(*first, *(last - 1));
        if (last - first >= 2)
            mySTL::down(first, last - 2, first, comp);
    }

*  up:上溯算法，用于从下向上遍历

template<class RandomAccessIterator, class Compare>
    //heap上溯算法
    static void up(RandomAccessIterator first, RandomAccessIterator last, 
    RandomAccessIterator head, Compare comp){
        if (first != last){
            int index = last - head;
            auto parentIndex = (index - 1) / 2;
            for (auto cur = last; parentIndex >= 0 && cur != head; parentIndex = (index - 1) / 2){
                auto parent = head + parentIndex;//get parent
                if (comp(*parent, *cur))
                    mySTL::swap(*parent, *cur);
                cur = parent;
                index = cur - head;
            }
        }
    }

*  down:下降算法，用于从上向下遍历

template<class RandomAccessIterator, class Compare>
    //heap下降算法
    static void down(RandomAccessIterator first, RandomAccessIterator last, 
    RandomAccessIterator head, Compare comp){
        if (first != last){
        auto index = first - head;
        auto leftChildIndex = index * 2 + 1;
        for (auto cur = first; leftChildIndex < (last - head + 1) && cur < last; leftChildIndex = index * 2 + 1){
            auto child = head + leftChildIndex;//get the left child
            if ((child + 1) <= last && *(child + 1) > *child)//cur has a right child
                child = child + 1;
            if (comp(*cur, *child))
                mySTL::swap(*cur, *child);
            cur = child;
            index = cur - head;
            }
        }
    }

*  copy: 复制算法，常用于赋值

template<>
    inline char *copy(char *first, char *last, char *result){
        auto dist = last - first;
        memcpy(result, first, sizeof(*first) * dist);
        return result + dist;
    }

四、set算法

STL 中有关 set 给出了四种算法，分别是交集，并集， 差集，对称差集。但是此处的 set 不同于数学中的集合。数学中的集合允许元素以任意次数、任意次序出现，但此处的不允许元素重复出现，而且所有元素按序出现。这四种算法处理的结构也是有序的。

*  交集 set\_intersection

交集用于求出两个不同集合中的相同元素。

template<class InputIterator,class OutputIterator>
    OutputIt set_intersection(InputIterator first1, InputIterator last1,
                              InputIterator first2, InputIterator last2,
                              OutputIterator d_first){
        while (first1 != last1 && first2 != last2) {
                if (*first1 < *first2) {
                    ++first1;
                } 
                else  {
                    if (!(*first2 < *first1)) {
                        *d_first++ = *first1++;
                    }
                    ++first2;
                }
            }
            return d_first;
        }

*  并集 set\_union

将两个集合合并到一起，相同的元素只在并集中出现一次。

template<class InputIterator,class OutputIterator>
    OutputIt set_union(InputIterator first1, InputIterator last1,
                       InputIterator first2, InputIterator last2,
                       OutputIterator d_first)
    {
        for (; first1 != last1; ++d_first) {
            if (first2 == last2)
                return std::copy(first1, last1, d_first);
            if (*first2 < *first1) {
                *d_first = *first2++;
            } 
            else {
                *d_first = *first1;
                if (!(*first1 < *first2))
                    ++first2;
                ++first1;
            }
        }
        return std::copy(first2, last2, d_first);
    }

*  差集 set\_difference

在集合 1 中出现而没有在集合 2 出现的元素

template<class InputIterator, class OutputIterator>
    OutputIt set_difference(InputIterator first1, InputIterator last1,
                            InputIterator first2, InputIterator last2,
                            OutputIterator d_first)
    {
        while (first1 != last1) {
            if (first2 == last2) 
                return std::copy(first1, last1, d_first);
    
            if (*first1 < *first2) {
                *d_first++ = *first1++;
            } 
            else {
                if (! (*first2 < *first1)) {
                    ++first1;
                }
                ++first2;
            }
        }
        return d_first;
    }

五、实验总结

算法是编程的效率所在，好的算法可以减少空间的浪费，并且可以极大程度的提高时间效率。但是算法更多的是理论上的东西，注重的是学习过程，如果有更优的算法或者什么新奇的算法我们都可以添加到 Algorithm.h 在以后的编程过程中可以直接调用。