c++ - 使用 std::accumulate 和 std::string 有效

Question

我是STL算法爱好者，所以在工作中经常用到很多STL算法。但是，...

考虑以下简单示例: //编译器:Visual Studio 2010 Sp1。中央处理器:i5 3300MG。

struct FileInfo
{
   std::string filename_;
   std::string filename()const { return filename_;}
};

//works with 1000 FileInfos,  Elapsed: 127.947 microseconds
std::string sumof_filenames_1(std::vector<FileInfo> const& fv )
{
   std::string s;
   for( std::size_t ix = 0u; ix < fv.size(); ++ix) s += fv[ix].filename();
   return s;
}

//Elapsed: 7430.138 microseconds
std::string sumof_filenames_2(std::vector<FileInfo> const& fv )
{
   struct appender{  
     std::string operator()(std::string const& s, FileInfo const& f)const 
      { return s + f.filename(); } 
   };

   return std::accumulate( std::begin(fv), std::end(fv), std::string(), appender() );
}

//Elapsed: 10729.381 microseconds
std::string sumof_filenames_3(std::vector<FileInfo> const& fv )
{
      struct appender{
           std::string operator()(std::string & s, FileInfo const& f) const
           { return s+= f.filename(); }
      };
      std::accumulate( std::begin(fv), std::end(fv), std::string(), appender() );
}

问:如何使用 STL 算法(如 std::accumulate 或任何其他算法)优化 sum_of_filenames，以及如何实现 appender 仿函数？

测试:主要功能:

int main()
   {
enum{ N = 1000* 1 };
srand(14324);
std::vector<FileInfo> fv;
fv.reserve(N);
for(std::size_t ix = 0; ix < N; ++ix)
{
    FileInfo f;
    f.m_Filename.resize(  static_cast< int > ( rand() *  256 / 32768 ) + 15 , 'A');
    //for( std::size_t iy = 0; iy < f.m_Filename.size(); ++iy)
    //  f.m_Filename[iy] = static_cast<char>( rand() * 100 / 32768 + 28 );

    fv.push_back( f );
}

LARGE_INTEGER freq, start, stop;
QueryPerformanceFrequency(&freq);

{
    QueryPerformanceCounter(&start);

    std::string s = sumof_filenames_1(fv); 


    QueryPerformanceCounter(&stop);
    double elapsed = (stop.QuadPart - start.QuadPart)* 1000.0 / (double)(freq.QuadPart) * 1000.0;
    printf("Elapsed: %.3lf microseconds\n", elapsed);



    printf("%u\n", s.size());
}


{
    QueryPerformanceCounter(&start);

    std::string s = sumof_filenames_2(fv); 


    QueryPerformanceCounter(&stop);
    double elapsed = (stop.QuadPart - start.QuadPart)* 1000.0 / (double)(freq.QuadPart) * 1000.0;
    printf("Elapsed: %.3lf microseconds\n", elapsed);



    printf("%u\n", s.size());
}




{
    QueryPerformanceCounter(&start);

    std::string s = sumof_filenames_3(fv); 


    QueryPerformanceCounter(&stop);
    double elapsed = (stop.QuadPart - start.QuadPart)* 1000.0 / (double)(freq.QuadPart) * 1000.0;
    printf("Elapsed: %.3lf microseconds\n", elapsed);



    printf("%u\n", s.size());
}

Answer 1

尝试估计下面的函数

std::string sumof_filenames_3(std::vector<FileInfo> const& fv )
{
      struct appender{
           std::string & operator()(std::string & s, FileInfo const& f) const
           { return s+= f.filename(); }
      };

      return std::accumulate( std::begin(fv), std::end(fv), std::string(), appender() );
}

并使用 lambda 表达式

std::string sumof_filenames_3(std::vector<FileInfo> const& fv )
{
      return std::accumulate( std::begin(fv), std::end(fv), std::string(),
                              []( std::string &s, FileInfo const& f ) -> std::string &
                              {
                                 return s += f.filename();
                              } ); 
}

同样估计下面的循环

std::string sumof_filenames_1(std::vector<FileInfo> const& fv )
{
   std::string::size_type n = 0;
   for each ( FileInfo const& f in fv ) n +=  f.filename().size();

   std::string s;
   s.reserve( n );

   for( std::size_t ix = 0u; ix < fv.size(); ++ix) s += fv[ix].filename();       

   return s;
}

也对按以下方式定义的结构进行相同的估计

struct FileInfo
{
   std::string filename_;
   const std::string & filename()const { return filename_;}
};