三、效率对比

本文参考文献：：GeekBand课堂内容，授课老师：张文杰

        　　　　：C++ Primer 11 中文版（第五版）

                   ：网络资料： 叶卡同学的部落格  http://www.leavesite.com/

                                                             http://blog.sina.com.cn/s/blog_a2a6dd380102w73e.html

 

一、关于Vector的基本概念及相关算法简介

1、什么是vector？

　　简单的理解：数组！

     进一步的理解：变长一维的动态数组，连续存放的内存块，堆内分配内存。支持[]操作（一会就会用到），支持下标操作。

     再进一步的理解：vector表示对象的集合，集合中每个对象都有与之对应的索引（理解为下标），这里可以保存很多元素的对象，包括不限于，如int string、或者自己定义的类的对象等等。

 

2、Vector的初始化

有几种基本初始化方法：

vector
     
       v1 ;          //构造函数vector
      
        v2(v1) ;    //拷贝构造函数vector
       
         v2 =v1 ;   //拷贝赋值vector
        
          v1{ 0, 0, 30, 20, 0, 0, 0, 0, 10, 0 };   //初始化
        
       
      
     

 本文中采用最基本的方法进行初始化。

3、Vector基本操作

vector
     
        vec;vector
      
        vec2;vec.push_back(t);  //向v的尾端添加元素tvec.empty();vec.size();vec == vec2;  //相等类似的操作都有
      
     

四、迭代器

简单的理解：类似于指针。如下面的一句话，迭代器有一个优点，那就是所有的标准库容器都可以使用迭代器，具有极强的通用性。

 

vector
     
      ::iterator result = find_if(Vec1.begin(), Vec1.end(), bind2nd(not_equal_to
      
       (), unexpectedInt));
      
     

 

五、本文中可能会用到的一些（算法）操作：

1、函数 ：not_equal_to，重载了操作符（），判断左右两个数是否相等，不等返回值 TRUE、即1，相等返回 FALSE、即0.

    类似的函数有equal_to 

template
     
          struct not_equal_to        : public binary_function<_Ty, _Ty, bool>    {    // functor for operator!=    bool operator()(const _Ty& _Left, const _Ty& _Right) const        {    // apply operator!= to operands        return (_Left != _Right);        }    };
     

 

2、bind1st 和 bind2nd

bind1st(const Fn2& Func,const Ty& left)  :1st指:传进来的参数应该放左边,也就是第一位bind2nd(const Fn2& Func,const Ty& right) :2nd指:传进来的参数应该放右边,也就是第二位

简单的两个例子：

#include "stdafx.h"#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #include 
           
            using namespace std;void ShowArray(vector
            
              &Vec){ vector
             
              ::iterator it = Vec.begin(); //it 是一个地址 while (it < Vec.end()) { cout << *it << endl; it++; }};int _tmain(int argc, _TCHAR* argv[]){ int a[] = { 1, 2, 100, 200 }; std::vector
              
                arr(a, a + 4); // 移除所有小于100的元素 arr.erase(std::remove_if(arr.begin(), arr.end(), std::bind2nd(std::less< int>(), 100)), arr.end()); ShowArray(arr); /**************************************/ printf("*******************************\n"); int b[] = { 1, 2, 100, 200 }; std::vector
               
                 arr2(b, b + 4); // 移除所有大于100的元素 arr2.erase(std::remove_if(arr2.begin(), arr2.end(), std::bind1st(std::less< int>(), 99)), arr2.end()); ShowArray(arr2);}
               
              
             
            
           
          
         
        
       
      
     

本例中因为仅判断是否为0 ，所有采用bind1st 和 bind2nd都一样。

 

3、remove_copy_if

remove_copy_if() 函数原型

template
     
         inline _OutIt remove_copy_if(_InIt _First, _InIt _Last,        _OutIt _Dest, _Pr _Pred)    {    // copy omitting each element satisfying _Pred    _DEBUG_RANGE(_First, _Last);    _DEBUG_POINTER(_Dest);    _DEBUG_POINTER(_Pred);    return (_Remove_copy_if(_Unchecked(_First), _Unchecked(_Last),        _Dest, _Pred,        _Is_checked(_Dest)));    }
     

 

remove_copy_if()的思考方式和copy_if()相反，若IsNotZero為true，則不copy，若為false，則copy。

 

remove_copy_if(Vec1.begin(), Vec1.end(), back_inserter(Vec2), IsNotZero);

此时要求： 当unexpectedInt 为0时，返回值为TRUE，不进行拷贝；当unexpectedInt 不为0时，返回值为FALSE，则进行copy。

bool IsNotZero(int unexpectedInt){    return (unexpectedInt == 0);}

 

 

二、三种不同方法来实现将查找拷贝操作

完成代码如下： 开发环境 VS2013 IDE

// Vector.cpp : 定义控制台应用程序的入口点。///*问题：给定一个 vector:v1 = [0, 0, 30, 20, 0, 0, 0, 0, 10, 0],希望通过 not_equal_to 算法找到到不为零的元素,并复制到另一个 vector: v2*//*要点一：    第一步、利用not_equal_to函数进行数值比较，区分vector某一元素是否是非0数据    第二步、查找所有的非0元素    第三步、将所有非0元素拷贝到v2中来要点二：效率问题    测试结果：    利用下标耗费时间最少，运行速度比较快，但不通用（vector可以利用下标）。    利用迭代器耗费时间较多，但更为通用。    利用C++ 11 remove_copy_if() algorithm 进行分析总结：    C++ 11 remove_copy_if() algorithm 代码最少，效率最高。*/#include "stdafx.h"#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #include 
           
            using namespace std;#pragma comment( lib,"winmm.lib" )//利用下标的方法void FiltArray0(vector
            
              &Vec1, vector
             
               &Vec2, const int unexpectedInt){ //测试时间 LARGE_INTEGER litmp; LONGLONG qt1, qt2; double dft, dff, dfm; QueryPerformanceFrequency(&litmp);//获得时钟频率 dff = (double)litmp.QuadPart; QueryPerformanceCounter(&litmp);//获得初始值 //测试时间开始 qt1 = litmp.QuadPart; int size = Vec1.size(); for (int i = 0; i
              

()(Vec1[i], unexpectedInt)) { Vec2.push_back(Vec1[i]); } else continue; } QueryPerformanceCounter(&litmp);//获得终止值 qt2 = litmp.QuadPart; dfm = (double)(qt2 - qt1); dft = dfm / dff;//获得对应的时间值 cout<<"下标方法测试时间为：" << dft << endl;}//使用迭代器void FiltArray1(vector

&Vec1, vector

&Vec2, const int unexpectedInt){ //测试时间 LARGE_INTEGER litmp; LONGLONG qt1, qt2; double dft, dff, dfm; QueryPerformanceFrequency(&litmp);//获得时钟频率 dff = (double)litmp.QuadPart; QueryPerformanceCounter(&litmp);//获得初始值 //测试时间开始 qt1 = litmp.QuadPart; //查找第一个不为0的数值 vector

::iterator result = find_if(Vec1.begin(), Vec1.end(), bind2nd(not_equal_to

(), unexpectedInt)); while (result != Vec1.end()) { Vec2.push_back(*result); //result结果的下一位开始查找不为0的数 result = find_if(result + 1, Vec1.end(), bind2nd(not_equal_to

(), unexpectedInt)); } QueryPerformanceCounter(&litmp);//获得终止值 qt2 = litmp.QuadPart; dfm = (double)(qt2 - qt1); dft = dfm / dff;//获得对应的时间值 cout << "迭代器方法测试时间为：" << dft << endl;}bool IsNotZero(int unexpectedInt){ return (unexpectedInt == 0);}void FiltArray2(vector

&Vec1, vector

&Vec2, const int unexpectedInt){ //测试时间 LARGE_INTEGER litmp; LONGLONG qt1, qt2; double dft, dff, dfm; QueryPerformanceFrequency(&litmp);//获得时钟频率 dff = (double)litmp.QuadPart; QueryPerformanceCounter(&litmp);//获得初始值 //测试时间开始 qt1 = litmp.QuadPart; // C++ 11 里的函数 //《effective STL》 :尽量用算法替代手写循环；查找少不了循环遍历 remove_copy_if(Vec1.begin(), Vec1.end(), back_inserter(Vec2), IsNotZero); QueryPerformanceCounter(&litmp);//获得终止值 qt2 = litmp.QuadPart; dfm = (double)(qt2 - qt1); dft = dfm / dff;//获得对应的时间值 cout << "利用拷贝算法测试时间为：" << dft << endl;}void ShowArray(vector

&Vec){ vector

::iterator it = Vec.begin(); //it 是一个地址 while (it < Vec.end()) { cout << *it << endl; it++; }}void ClearArray(vector

&Vec){ vector

::iterator it = Vec.begin(); //清空数据 while (it < Vec.end()) { it = Vec.erase(it); }}int main(){ vector

v1{ 0, 0, 30, 20, 0, 0, 0, 0, 10, 0 }; vector

v2; const int unexpectedInt = 0; /* 方案一： 利用数组下标sanzho */ FiltArray0(v1, v2, unexpectedInt); cout << "利用数组下标方案，V2中数据为：" << endl; ShowArray(v2); /* 方案二： 利用迭代器 */ ClearArray(v2); FiltArray1(v1, v2, unexpectedInt); cout << "利用迭代器方案，V2中数据为：" << endl; ShowArray(v2); /* 方案三： 利用拷贝算法 */ ClearArray(v2); FiltArray2(v1, v2, unexpectedInt); cout << "利用拷贝算法，V2中数据为：" << endl; ShowArray(v2); return 0;}