C++相关闲碎记录(7)

1、iterator trait迭代器特性

namespace std {
    struct output_iterator_tag {};
    struct input_iterator_tag {};
    struct forward_iterator_tag : public input_iterator_tag {};
    struct bidirectional_iterator_tag : public forward_iterator_tag{};
    struct random_access_iterator_tag : public bidirectional_iterator_tag{};
}

迭代器种类

namespace std {
    template <typename T>
    struct iterator_traits {
        typedef typename T::iterator_category   iterator_category;
        typedef typename T::value_type          value_type;
        typedef typename T::difference_type     difference_type;
        typedef typename T::pointer             pointer;
        typedef typename T::reference           reference;
    };
}

2、运用迭代器的value_type

typename std::iterator_traits<T>::value_type tmp;

?3、运用迭代器的iterator_category

如果希望针对不同的迭代器种类采用不同的实现方案，按照下面两个步骤。

1.使用迭代器种类作为附加参数，调用另外一个函数。

template <typename Iterator>
inline void foo(Iterator beg, Iterator end) {
    foo(beg, end, 
        std::iterator_traits<Iterator>::iterator_category());
}

2.针对不同的迭代器种类实现特例化，注意如果此处迭代器种类B为D类的父类，那么就只需要实现B类即可。

template <typename BiIterator>
void foo(BiIterator beg, BiIterator end, std::bidirectional_iterator_tag) {
    ...
}

template <typename RaIterator>
void foo(RaIterator beg, RaIterator end, std::random_access_iterator_tag) {
    ...
}

4、distance的实现

// general distance()
template <typename Iterator>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator pos1, Iterator pos2) {
    return distance(pos1, pos2,
                    std::iterator_traits<iterator>::iterator_category());
}

// distance for random-access iterators 
template <typename RaIterator>
typename std::iterator_traits<RaIterator>::difference_type
distance(RaIterator pos1, RaIterator pos2, std::random_access_iterator_tag) {
    return pos2 - pos1;
}

// distance for input, forward, and bidirectional iterators
template <typename InIterator>
typename std::iterator_traits<InIterator>::difference_type
distance(InIterator pos1, InIterator pos2, std::input_iterator_tag) {
    typename std::iterator_traits<InIterator>::difference_type d;
    for (d = 0; pos1 != pos2; ++pos1, ++d);
    return d;
}

?返回类型必须是迭代器距离类型（difference type），第二个特例化时使用了input迭代器，对于forward，bidirectional迭代器都有效，因为他们都是从input_iterator_tag派生出来的。

?5、用户自定义迭代器

让iterator trait 能够处理这样的迭代器，有两种方法：

1.提供必要的五种类型定义，就像iterator_traits结构所描述。

2.为iterator_traits 结构提供一个偏特化版本。

关于第一种方法，C++标准库提供了一个特殊的基类，iterator<>专门用来进行这一定义，只需这样指定类型：

class MyIterator : public std::iterator<std::bidirectional_iterator_tag,
                                type, std::ptrdiff_t, type*, type&> {
    ...
};

?其中第一个模板参数template用来定义迭代器的种类，第二个参数用来定义元素类型，第三个参数用来定义difference距离类型，第四个参数用来定义pointer类型，第五个参数用来定义reference类型。末尾的三个参数有默认值ptrdiff_t， type*和type&，所以通常简写如下：

class MyIterator : public std::iterator<std::bidirectional_iterator_tag, type>{
    ...
};

//assoiter.hpp
#include <iterator>

// class template for insert iterator for associative and unordered containers
template <typename Container>
class asso_insert_iterator : public std::iterator<std::output_iterator_tag, typename Container::value_type> {
protected:
    Container& container;   //container in which elements are inserted

public:
    // constructor
    explicit asso_insert_iterator(Container& c) : container(c) {
        std::cout << "init" << std::endl;
    }
    // assignment operator
    // inserts a value into the container
    asso_insert_iterator<Container>&
    operator=(const typename Container::value_type& value) {
        container.insert(value);
        return *this;
    }

    // dereferencing is a no-op that returns the iterator itself
    asso_insert_iterator<Container>& operator* () {
        std::cout << "call operator *" << std::endl;
        return *this;
    }

    // increment operator is a no-op that returns the ietrator itself
    // 这里的前置和后置++都是什么都没做，直接返回了自身容器的对象
    asso_insert_iterator<Container>& operator++() {
        return *this;
    }
    asso_insert_iterator<Container>& operator++(int) {
        return *this;
    }
};

// convenience function to create the inserter
template <typename Container>
inline asso_insert_iterator<Container> asso_inserter(Container& c) {
    std::cout << "asso_inserter" << std::endl;
    return asso_insert_iterator<Container>(c);
}

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include "print.hpp"
#include "assoiter.hpp"

int main() {
    std::unordered_set<int> coll;
    // cerate inserter for coll
    // inconvenient way
    // 调用了模板类的构造函数
    asso_insert_iterator<decltype(coll)> iter(coll);  // init 

    // insert elements with the usual iterator interface
    // 使用了自定义的赋值操作，内部是调用了insert方法
    *iter = 1;
    // 这里的前置和后置++都只是返回了容器对象，没有别的操作
    iter++;
    *iter = 2;
    iter++;
    *iter = 3;
    PRINT_ELEMENTS(coll);

    // create inserter for coll and insert elements
    // convenient way
    asso_inserter(coll) = 44;
    asso_inserter(coll) = 55;
    PRINT_ELEMENTS(coll);

    // use inserter with an algorithm
    std::vector<int> vals = {33, 67, -4, 13, 5, 2};
    std::copy(vals.begin(), vals.end(),
              asso_inserter(coll));
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
init
call operator *
call operator *
call operator *
3 2 1
asso_inserter
init
asso_inserter
init
44 55 3 2 1
asso_inserter
init
call operator *
call operator *
call operator *
call operator *
call operator *
call operator *
13 -4 33 5 44 55 3 67 2 1

6、function object 拥有内部状态

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
#include "print.hpp"

using namespace std;

class IntSequence {
private:
    int value;
public:
    IntSequence(int initialValue) : value(initialValue) {}
    int operator() (){
        return ++value;
    }
};

int main() {
    list<int> coll;
    // 这里的function object是值传递，所以不记录最终的状态
    generate_n(back_inserter(coll), 9, IntSequence(1));
    PRINT_ELEMENTS(coll);

    generate(next(coll.begin()), prev(coll.end()), IntSequence(42));
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
2 3 4 5 6 7 8 9 10
2 43 44 45 46 47 48 49 10

有三种方法可以运用了function object的算法中获取结果或者反馈。

1.在外部持有状态，并让function object指向他。

2.以by reference 的方式传递function object。

3.利用for_each()算法返回值。

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
#include "print.hpp"

using namespace std;

class IntSequence {
private:
    int value;
public:
    IntSequence(int initialValue) : value(initialValue) {}
    int operator() (){
        return ++value;
    }
};

int main() {
    list<int> coll;
    IntSequence seq(1);
    // 生命引用方式
    generate_n<back_insert_iterator<list<int>>, int, IntSequence&>(back_inserter(coll), 4, seq);
    PRINT_ELEMENTS(coll);

    // 这里是临时变量，值传递
    generate_n(back_inserter(coll), 4, IntSequence(42));
    PRINT_ELEMENTS(coll);

    // 这里是指传递，但是seq在上次引用传递时保留了状态，这里是从5开始
    generate_n(back_inserter(coll), 4, seq);
    PRINT_ELEMENTS(coll);
    // 这里还是从5开始
    generate_n(back_inserter(coll), 4, seq);
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
2 3 4 5 
2 3 4 5 43 44 45 46
2 3 4 5 43 44 45 46 6 7 8 9
2 3 4 5 43 44 45 46 6 7 8 9 6 7 8 9

通过for_each获取返回值

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MeanValue {
private:
    long num; //number of elements
    long sum; //sum of all elements
public:
    MeanValue() : num(0), sum(0) {}
    void operator() (int elem) {
        ++num;
        sum += elem;
    }
    double value() {
        return static_cast<double>(sum) / static_cast<double>(num);
    }
};


int main() {
    vector<int> coll = {1, 2, 3, 4, 5,6,7,8};
    MeanValue mv = for_each(coll.begin(), coll.end(), MeanValue());
    cout << "mean value: " << mv.value() << endl;
    return 0;
}
输出：mean value: 4.5

7、predicate 判断式 vs. Function object 函数对象

#include <iostream>
#include <list>
#include <algorithm>
#include "print.hpp"

using namespace std;

class Nth {
private:
    int nth;              //call for which to return true
    int count;            //call counter
public:
    Nth(int n) : nth(n), count(0) {
    }
    bool operator() (int) {
        return ++count == nth;
    }
};

int main() {
    list<int> coll = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    PRINT_ELEMENTS(coll, "coll:   ");
    
    //remove third element 
    list<int>::iterator pos;
    pos = remove_if(coll.begin(), coll.end(), Nth(3));
    coll.erase(pos, coll.end());
    PRINT_ELEMENTS(coll, "3rd removed: ");
}
输出：
coll:   1 2 3 4 5 6 7 8 9 10 
3rd removed: 1 2 4 5 7 8 9 10

?上述结果中3和6都被删除了，为什么会这样，因为该算法的常见做法是在其内部保留predicate的一份拷贝。

template <typename ForwIter, typename Predicate>
ForwIter std::remove_if(ForwIter beg, ForwIter end, Predicate op) {
    beg = find_if(beg, end, op);
    if (beg == end) {
        return beg;
    } else {
        ForwIter next = beg;
        return remove_copy_if(++next, end, beg, op);
    }
}

使用find_if查找到第一个元素，接下来又实用op操作后面的元素，后面的一次仍让会删除掉第三个元素，也就是整体的第6个元素。

8、预定义的Function object

negate<type>()	-param
plus<type>()	param1+param2
minus<type>()	param1-param2
multiplies<type>()	param1*param2
divides<type>()	param1/param2
modulus<type>()	param1%param2
equal_to<type>()	param1==param2
not_equal_to<type>()	param1!=param2
less<type>()	param1<param2
greater<type>()	param1>param2
less_equal<type>()	param1<=param2
greater_equal<type>()	param1>=param2
logical_not<type>()	!param
logical_and<type>()	param1 && param2
logical_or<type>()	param1 || param2
bit_and<type>()	param1 & param2
bit_or<type>()	param1 | param2
bit_xor<type>()	param1 ^ param2

?