首页 > > 程序设计 > C/C++ >

CPP笔记_泛型编程简单总结

2018-06-17 22:43:13来源：未知阅读 ()

　　本篇是基于《Essential C++》第三章泛型编程风格的一个简单总结

1 Iterator

　　vector<string>::iterator 表明此iterator是位于string vector定义内的一个嵌套类型；

　　vector<string>::const_iterator 只容许我们读取vector内的元素，但不容许任何写入操作；

2 容器

　　所有容器都支持的操作有：

“==”和“!=”操作符，返回true或者false
assignment（=）运算符，将一个容器复制给另一个容器。这是深度复制，而不是简单的引用。比如vector<int> ori; ori.insert(1); vector<int> copied = ori; ori.clear(); cout<<ori.size()<<" "<<copied.size(); 那么将输出“0 1”
empty()：当容器内无任何元素时返回true，否则false
size()：返回容器内目前持有的元素个数
clear()：删除所有元素
begin()：返回一个指向容器内第一个元素的iterator
end()：返回一个指向容器内最后一个元素的下一个位置的iterator
insert()：将单一或者某个范围内的元素插入容器内
erase()：将容器内的单一元素或者某个范围内的元素删除

容器	Vector	list	Deque
存储方式	连续内存	双向链接	连续内存
插入/删除	对末端的插入和删除效率很高，而对非末端的插入删除则由于需要大量复制而效率很低	对任意位置的插入删除都效率高	对头、尾的插入删除都效率高
随机读取	高	低	高
支持操作	push_back() pop_back()	push_back() pop_back() push_front() pop_front()	push_back() pop_back() push_front() pop_front()
	Pop操作并不返回删除的元素，要获取对应的元素，可以分别调用back(), front()

3 Function Object

　　技术背景：在定义一些泛型函数时，可能需要使用者传入一些比如less_than这样的函数指针，例如：

 1 //一个小于比较器
 2 bool less_than(int v1, int v2)
 3 {
 4     return v1 < v2 ? ture : flase;
 5 }
 6 
 7 //用来从原vec中过滤基于pred比较结果的数。pred即为使用这需要传入的指明比较意义的函数指针。
 8 vector<int> vec_filter(const vector<int> &vec, const int threshold, bool (*pred) (int, int))
 9 {
10     vector<int> result;
11     for (int i = 0; i < vec.size(); ++i)
12     {
13         if(pred(vec[i], threshold))
14         {
15             result.push_back(vec[i]);
16         }
17     }
18     return result;
19 }

　　我在使用vec_filter(vec, 100, less_than)的时候，就会得到一个把原vec中所有小于100的数的提取出来的result。但是这样的话，效率不高，因为在vec_filter的if判断中是通过函数指针来调用函数的。要是能使用inline就好了。function object就是为了这个而设计出来的。使用function object就可以让这个调用成为inline调用，提高效率。

　　为了使用function object，应该包含头文件#include<functional>，在标准库中定义了一组function object，包括算术运算、关系运算和逻辑运算三个类别：

六个算术运算：plus<type>, minus<type>, negate<type>, multiplies<type>, divides<type>, modules<type>
六个关系运算：less<type>, less_equal<type>, greater<type>, greater_equal<type>, equal_to<type>, not_equal_to<type>
三个逻辑运算：logical_and<type>, logical_or<type>, logical_not<type>

　　sample代码：

 1 //一个小于比较器
 2 bool less_than(int v1, int v2)
 3 {
 4     return v1 < v2 ? true : false;
 5 }
 6 
 7 //用来从原vec中过滤基于pred比较结果的数。pred即为使用这需要传入的指明比较意义的函数指针。
 8 template<typename Comp>
 9 vector<int> vec_filter(const vector<int> &vec, const int threshold, Comp pred)
10 {
11     vector<int> result;
12     for (int i = 0; i < vec.size(); ++i)
13     {
14         if(pred(vec[i], threshold))
15         {
16             result.push_back(vec[i]);
17         }
18     }
19     return result;
20 }
21 
22 int main()
23 {
24 
25     vector<int> vecint(100);
26     for(int i = 0; i < 100; ++i)
27     {
28         vecint.push_back(i);
29     }
30     vector<int> result = vec_filter(vecint, 45, less_than);
31     cout<<result.size()<<" "<<vecint.size()<<endl;
32     result = vec_filter(vecint, 68, less<int>());
33     cout<<result.size()<<" "<<vecint.size()<<endl;
34 }

　　可能标准库提供的function object不能满足需求，标准库还提供了两个bingder adapter(绑定适配器)。这两个绑定器的作用都是将一元function object变成function object，其中bind1st将指定值绑定到第一个参数，bind2nd将指定值绑定到第二个参数，示例代码：

 1 template<typename Comp>
 2 vector<int> vec_filter(const vector<int> &vec, Comp pred)
 3 {
 4     vector<int> result;
 5     for (int i = 0; i < vec.size(); ++i)
 6     {
 7         if(pred(vec[i]))
 8         {
 9             result.push_back(vec[i]);
10         }
11     }
12     return result;
13 }
14 
15 int main()
16 {
17 
18     vector<int> vecint;
19     for(int i = 0; i < 100; ++i)
20     {
21         vecint.push_back(i);
22     }
23     vector<int> result = vec_filter(vecint, bind1st(less<int>(), 45));
24     cout<<result.size()<<" "<<vecint.size()<<endl; //54   100
25     binder2nd<less<int>> bind2 = bind2nd(less<int>(), 45);
26     result = vec_filter(vecint, bind2);
27     cout<<result.size()<<" "<<vecint.size()<<endl;  //45  100
28 }

　　我们可以在7行的if中，pred就只需要传入一个参数了。而且对比bind1st和bind2nd两个函数的效果，bind1st因为把45绑定在第一个参数，那么在if中，只要vec[i]比45大，条件就会成立，所以输出54。同理，bind2nd输出45.

　　如何自定义一个function object？

　　当编译器遇到一个语句 lt(ival); 的时候，lt可能是什么？有三种可能：函数名称，函数指针，还有一种可能就是一个提供了function call运算符的的function object，即lt是一个class object。那么编译器将把上述语句自动转换为：lt.operator(ival); 因此，自定义function object的关键也就出来了，就是定义一个operator()运算符。

class LessThan{
private:
    int mVal;
public:
    LessThan(int val){mVal = val;}
    /************************************************************************/
    /* 特征。0：operator()操作符； 1：inline；2：const函数；  */
    /************************************************************************/
    inline bool operator()(int val) const {return val < mVal;};
};

4 Iterator Inserter

　　背景问题：在所有“会对元素进行复制行为”的泛型算法中，比如copy(), copy_backwards(), remove_copy(), replace_copy(), unique_copy()等等，他们的实现中每复制一个元素，都会使用赋值(assignment， =)来实现，那么就存在一个问题，即目标容器的容易必须足够大，否则就会产生溢出错误。即对使用者提出了这样的一个要求：保证目的容器的容量足够大。比如下面代码就会报错：

1     vector<int> vecint;
2     for(int i = 0; i < 100; ++i)
3     {
4         vecint.push_back(i);
5     }
6     vector<int> vec2; //假如改为vector<int> vec2(vecint.size())则会正常运行
7     copy(vecint.begin(), vecint.end(), vec2.begin());

　　STL为了能够消除使用者的这个负担，提供了三个insertion adapter：back_inserter(), inserter(), front_inserter()(由于vector并没有push_front()，所以这个只使用于list和deque), 他们会分别使用push_back()，insert()和push_front()来替代赋值（=）操作。示例代码：

1     vector<int> vecint;
2     for(int i = 0; i < 100; ++i)
3     {
4         vecint.push_back(i);
5     }
6     vector<int> vec2;
7     copy(vecint.begin(), vecint.end(), back_inserter(vec2));
8     cout<<vec2.size();   //输出100

5 Iostream Iterator

　　效果：使用iterator来替代输入输出流的表达方式。标准库中提供istream_iterator和ostream_iterator两个类来分别支持单一类型的元素读取和写入，使用时应该先#include <iterator>。示例代码：

 1     //从cin中输入单词，然后写入到文件word.txt
 2     //常用表达方式
 3     string word;
 4     vector<string> vec_word;
 5     while (cin>>word)
 6     {
 7         vec_word.push_back(word);
 8     }
 9     ofstream out_file("word.txt");
10     for (int i = 0; i < vec_word.size(); ++i)
11     {
12         out_file<<vec_word[i] <<" ";
13     }
14 
15     //使用iostream iterator
16     istream_iterator<string> str_in(cin); //创建输入流迭代器，可以从任何输入流创建
17     istream_iterator<string> eof;
18     copy(str_in, eof, vec_word);
19     //创建输出流迭代器，可以从任何输出流创建
20     ostream_iterator<string> out_file_itr(ofstream("word.txt"), " ");
21     copy(vec_word.begin(), vec_word.end(), out_file_itr);