C++ STL(自定义泛型算法)

xiaoxiao2021-02-28  6

本文,记录C++ STL 实现自定义泛型算法。 支撑C++成熟的STL是: 容器(vector、list、queue、stack、map、set等)泛型算法(sort、find、merge、replace等) 实现上述的关键是: function template技术,达到“与操作对象的类型相互独立”的目的。一对iterator(first和last),标示我们需要迭代的范围,实现“与容器无关”的诀窍,就是不要直接在容器上进行操作。 容器在此不展开,在此专门讲述STL::generic algorithm。 下面,整理自《Essential C++》对泛型算法的推导。从C的指针(结合函数指针)逐渐推理到C++的泛型算法,整个过程:证明泛型的通用性与实用性,加深对泛型的理解。最重要的是:这对以后自己构建泛型算法,有了根的基础。 最终目标: 元素类型无关操作类型无关容器类型无关 包含文件: <algorithm><functional> 备注:容器自行添加。 函数实现功能:从一个vector内找出小于10的所有元素。 vector<int> less_than_10(const vector<int> &vec) {      vector<int> nvec;      for(int ix = 0; ix < vec.size(); ++ix)           if(vec[ix] < 10)                nvec.push_back(vec[ix]);      return nvec; } 突破: 实现题目基本要求,编译通过,运行正确。 vector<int> less_than(const vector<int> &vec, int less_than_val) {      vector<int> nvec;      for(int ix = 0; ix < vec.size(); ++ix)           if(vec[ix] < less_than_val)                nvec.push_back(vec[ix]);      return nvec; } 突破: 函数功能扩展:任意服务对象(添加了less_than_val参数),函数通用性增强。 vector<int> filter(const vector<int> &vec, int filter_val, bool (*pred)(int, int)) {      vector<int> nvec;      for(int ix = 0; ix < vec.size(); ++ix)           if(pred(vec[ix], filter_val))                nvec.push_back(vec[ix]);      return nvec; } bool less_than(int v1, int v2) {      return v1 < v2 ? ture : false; } bool greater_than(int v1, int v2) {      return v1 > v2 ? ture : false; } 突破: 操作类型无关:可以自行定义操作类型(这里指:比较操作),如上述代码有小于、大于操作。 vector<int> filter(const vector<int> &vec, int val, less<int> <) {      vector<int> nvec;      vector<int>::const_iterator iter=vec.begin();      while((iter =                find_if(iter, vec.end(),                          bind2nd(lt, val))) != vec.end() )      {                nvec.push_back(*iter);                iter ++;      }      return nvec; } 突破: 使用C++的function object,从指针函数调用(call调用)转到inline函数,提高性能。传递function object实现,传递某组行为给函数。更加统一化,使用function object adapter与function object结合。继而使用iterator,实现元素类型无关的前提之一,不直接操作容器元素(避免vector连续、list不连续时,指针无效递增问题)。 template <typename InputIterator,           typename OutputIterator,           typename ElemType,           typename Comp> OutputIterator filter( InputIterator first, InputIterator last,         OutputIterator at,         const ElemType &val, Comp pred ) {     while (( first =              find_if( first, last,                       bind2nd( pred, val ))) != last )     {              cout << "found value: " << *first << endl;              // assign value, then advance both iterators              *at++ = *first++;     }     return at; } 突破: 元素类型无关:包括输入输出,更不管是int还是float容器类型无关:容器不指定array还是vector,亦或是list操作类型直接有用户输入,完全自定义。 综上可见,泛型算法的三个目标已经实现: 元素类型无关容器类型无关操作类型无关
转载请注明原文地址: https://www.6miu.com/read-1600003.html

最新回复(0)