STL算法之基本算法＜stl_algobase.h＞

        STL标准规格中没哟区分基本算法或复杂算法，然后SGI却把常用的一些算法定义于<stl_algobase.h>之中，其他算法定义于<stl_algo.h>之中。以下一一列举这些基本算法。

目录

运用实例

equal,fill,fill_n,iter_swap, lexicographical_compare,max,min,mismatch,swap

equal

fill

fill_n

iter_swap

lexicographical_compare

max

min

mismatch

swap

运用实例

        我们首先来看基本算法的一些运行实例

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

template <class T> 
struct display {
    void operator() (const T&x) {
        cout << x << ' ';
    }
};


int main() {
    int ia[9] = {0,1,2,3,4,5,6,7,8};
    vector<int> iv1(ia, ia + 5); // 0,1,2,3,4
    vector<int> iv2(ia, ia+9);   // 0,1,2,3,4,5,6,7,8

    cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).first << endl; // ?
    cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin())).second << endl; // 5

    cout << equal(iv1.begin(), iv1.end(), iv2.begin()) << endl; // 1
    cout << equal(iv1.begin(), iv1.end(), iv2.begin() + 2) << endl; //0, false
    // 0,1,2,3,4 不等于 2,3,4,5,6

    fill(iv1.begin(), iv1.end(), 9);
    for_each(iv1.begin(), iv1.end(), display<int>()); // 9 9 9 9 9
    cout << endl;

    fill_n(iv1.begin(), 3, 7);
    for_each(iv1.begin(), iv1.end(), display<int>()); // 7 7 7 9 9
    cout << endl;

    vector<int>::iterator ite1 = iv1.begin();
    vector<int>::iterator ite2 = ite1;

    advance(ite2, 3);  // plus three times?
    cout << *ite1 << ' ' << *ite2 << endl; // 7 9
    
    iter_swap(ite1, ite2);
    cout << *ite1 << ' ' << *ite2 << endl; // 9 7
    for_each(iv1.begin(), iv1.end(), display<int>()); // 9 7 7 7 9
    cout << endl;

    cout << max(*ite1, *ite2) << endl; // 9
    cout << min(*ite1, *ite2) << endl; // 7

    
    swap(*iv1.begin(), *iv2.begin());
    for_each(iv1.begin(), iv1.end(), display<int>()); // 0 7 7 7 9
    cout << endl;
    for_each(iv2.begin(), iv2.end(), display<int>()); // 9 1 2 3 4 5 6 7 8
    cout << endl;

    //准备两个字符串数组
    string stra1[] = {"Jamie", "JJHou", "Jason"};
    string stra2[] = {"Jamie", "JJhou", "Jerry"};


   
    cout << lexicographical_compare(stra1, stra1 + 3, stra2, stra2 + 3) << endl;     // 1 (stra1 小于stra2)
    
    cout << lexicographical_compare(stra1, stra1+3, stra2, stra2+3, greater<string>()) << endl;     // 0 (stra1 不大于 stra2)
    return 0;
}

equal,fill,fill_n,iter_swap, lexicographical_compare,max,min,mismatch,swap

        这一节对运用实例中实际测试的算法进行说明。

equal

        如果两个序列在[first, last)区间内相等，equal()返回true。如果第二序列的元素比较多，多出来的元素不予考虑。因此，如果，我们希望保证两个序列完全相等，必选先判断其元素个数是否相同：

(vec1.size() == vec2.size() && equal(vec1.begin(), vec1.end(), vec2.begin())

抑或使用容器所提供的quality操作符，例如vec1 == vec2.如果第二序列的元素比第一序列少，这个算法内部进行迭代行为时，会超越序列的尾端，造成不可预测的结果。

        源码如下所示：

template <class InputIterator1, class InputIterator2>
inline bool equal(InputIterator1 first1, InputIterator1 last, InputIterator2 first2)
{
    for (;first1 != last1; ++first1, ++first2) {
        if (*first1 != *first2) return false;
    }
    return true;
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool equal(InputIterator1 first1, InputIterator1 last, InputIterator2 first2, BinaryPredicate binary_pred)
{
    for (;first1 != last1; ++first1, ++first2) {
        if (!binary_pred(*first1, *first2)) return false;
    }
    return true;
}

fill

        将[first, last)内的所有元素该填新值。

template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) {
    for(; first != last; ++first) {
        *first = value;
    }
}

fill_n

        将[first,first+n)改填为新值，返回的迭代器指向填入的最后一个元素的下一位置。

template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
    for (;n > 0; --n; ++first) {
        *first = value;
    }
    return first;
}

如果n超越了容器的现有大小，会造成什么结果呢？我们可以很容易从fill_n()的源代码知道，如果每次迭代进行的是assignment操作，是一种覆写操作；即当迭代器已经达到end后，对齐提领(dereference)操作是未定义的，可能会产生不可预期的结果。解决办法之一是，利用inserter()产生一个具有插入(insert)而非覆写(overwrite)能力的迭代器。inserter()可产生一个用来修饰迭代器的配接器(iterator adaper),用法如下

int ia[3] = {0, 1, 2};
vector<int> iv{ia, ia + 3};
fill_n(inserter(iv, iv.begin()), 5, 7);   // 7 7 7 7 7 0 1 2

inserter(iv, iv.begin())和书中的inserter(iv.begin())略有差异

iter_swap

        将两个ForwarIterators所指的对象对调。如下图：

template<class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
    __iter_swap(a, b, value_type(a));
}


template<class ForwardIterator1, class ForwardIterator2, T*> void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

        Iter_swap()是“迭代器之value type”派上用场的一个好例子。是的，该函数必须知道迭代器的value type，才能够据此声明一个对象，用来暂时存放迭代器所指对象。为此，上述源代码特别设计了一个双层构造，第一层调用第二层，并多出了一个额外参数value_type(a)。这么一来，第二层就有value type可以用了。乍见之下我们可能会对这个额外参数在调用端和接受端的型别感到讶异，调用端是value_type(a),接受端是T*。只要找出iterator::value_type()的定义瞧瞧，就一目了然了:

template <class Iterator>
inline typename iterator_traits<Iterator>::value_type* value_type(const Iterator&) {
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

        这种双层结构在SGI STL中十分普遍，其实可以换一种写法

template<class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
    typename iterator_traits<ForwardIterator1>::value_type tmp = *a;
    *a = *b;
    *b = tmp;
}

lexicographical_compare

        以字典排列方式对两个序列[first1,last1)和[first2,last2)进行比较。比较操作针对两个序列中对应位置上的元素进行，并持续直到(1)某一组对象元素彼此不相等；（2）同时到达了last1和last2（当两个序列的大小相同）；（3）到达last1或last2(当两序列大小不同)

        当这个函数在对应位置上发现第一组不相等的元素时，有下列几种可能：

• 如果第一个序列的元素较小，返回true，否则返回false
• 如果达到last1而尚未达到last2，返回true
• 如果达到last2而尚未达到last1， 返回false
• 如果同时达到last1和last2，返回false

举个例子

string stra1[] = {"Jamie", "JJHou", "Jason"};
string stra2[] = {"Jamie", "JJhou", "Jason"};

   这个算法面对第一组元素对，判断其为相等，但面对第二

组元素对，判断其为不等。就字符串而言JJHou下雨JJhou，因为H在字典排列次序上小于h。于是这个算法再打第二组元素对停了下来。比较结果为true。

        第二个版本允许指定一个反函数comp作为比较操作之用，取代元素型别所提供的less-than操作符。

template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1
                             InputIterator2 first2, InputIterator2 last2) {
    for (; first1!=last1 && first2!=last2;++first1;++first2) {
        if (*first1 < *first2) {
            return true;
        }
        if (*first2 < *first1) {
           return false;
        }
    }
    return first1 == last1 && first2 != last2;
}

template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1
                             InputIterator2 first2, InputIterator2 last2, Compare comp) {
    for (; first1!=last1 && first2!=last2;++first1;++first2) {
        if ( comp(*first1, *first2)) {
            return true;
        }
        if ( comp(*first2, *first1)) {
           return false;
        }
    }
    return first1 == last1 && first2 != last2;
}

        为了增进效率，SGI还设计了一个特化版本，用于原生指针const unsigned char*:

inline bool lexicographical_compare(const unsigned char * first1
                                  , const char* last1
                                  , const char* first2
                                  , const char* last2) {
    const size_t len1 = last1 - first1;
    const size_t len2 = last2 - first2;

    const int result = memcmp(first1, first2, min(len1, len2));
    return result != 0 ? (result < 0) : len1 < len2;
}

max

        取两个对象中的较大值。有两个版本，版本一使用对象类型T所提供的greater-than操作符来判断大小，版本二使用仿函数comp判断大小。

template<class T>
inline const T& max(const T&a, const T&b) {
    return a < b ? b : a;
}

template<class T, class comp>
inline const T& max(const T&a, const T&b, Compare comp) {
    return comp(a, b) ? b : a;
}

min

        取两个对象的较小值。

template<class T>
inline const T& min(const T&a, const T&b) {
    return b < a ? b : a;
}

template<class T, class comp>
inline const T& min(const T&a, const T&b, Compare comp) {
    return comp(b, a) ? b : a;
}

mismatch

        用来平行比较两个序列，指出两者之间的第一个不匹配点。返回一对迭代器，分别指向两徐磊中不匹配的点。如下图所示

代码如下：

template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) {
    while(first1 != last1 && *first1 == *first2) {
        ++first1;
        ++first2;
    }
    return pair<InputIterator1, InputIterator2>(first1, first2);
}

template<class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate binary_pred) {
    while(first1 != last1 && binary_pred(*first1, *first2)) {
        ++first1;
        ++first2;
    }
    return pair<InputIterator1, InputIterator2>(first1, first2);
}

swap

        该函数用来交换两个对象

template <class T> 
inline void swap(T&a, T&b) {
    T tmp = a;
    a = b;
    b = tmp;
}

参考文档《STL源码剖析》---侯捷