C++对矢量或链表进行排序

Question

我有一个输入文件,我想根据时间戳排序,时间戳是每个记录的子字符串.我想存储多个属性

该列表目前约有1000条记录.但是,我希望它能够扩大一点以防万一.

当我使用链接列表通过搜索整个列表进行插入时,花了大约20秒.现在,只需填充一个矢量并输出到文件需要4秒钟(这听起来太长了)？

我想使用合并排序或快速排序(合并排序对我来说似乎更容易).我遇到的麻烦是我没有看到使用对象而不是原始数据类型实现这些排序的许多示例.

我可以使用矢量或链接列表.到目前为止,我从这个网站获得的反馈最有帮助.我希望有人可以洒上神奇的小精灵尘埃,让我更轻松:)

任何链接或示例以最简单的方式执行此操作具有相当不错的性能将是非常感谢.我对如何使用对象实现这些排序感到困惑,因为我是C++的新手:)

这是我的新代码的样子(尚无排序):

class CFileInfo  
{  
    public:  
    std::string m_PackLine;  
    std::string m_FileDateTime;  
    int m_NumDownloads;  
};  
void main()  
{  
    CFileInfo packInfo;  
    vector<CFileInfo> unsortedFiles;  
    vector<CFileInfo>::iterator Iter;  
    packInfo.m_PackLine = "Sample Line 1";  
    packInfo.m_FileDateTime = "06/22/2008 04:34";  
    packInfo.m_NumDownloads = 0;  
    unsortedFiles.push_back(packInfo);  
    packInfo.m_PackLine = "Sample Line 2";  
    packInfo.m_FileDateTime = "12/05/2007 14:54";  
    packInfo.m_NumDownloads = 1;  
    unsortedFiles.push_back(packInfo);  
    for (Iter = unsortedFiles.begin(); Iter != unsortedFiles.end(); ++Iter )   
    {  
        cout << " " << (*Iter).m_PackLine;  
    }  
}  

Answer 1

我不确定我是否正确理解了你的问题,是你定义排序函子的问题吗？STL排序通常被实现为内省排序,对于大多数情况非常好.

struct sort_functor
{
    bool operator()(const CFileInfo & a, const CFileInfo & b) const
    {

        // may be a little bit more subtle depending on what your strings look like
        return a.m_FileDateTime < b.m_FileDateTime;
    }
}

std::sort(unsortedFiles.begin(), unsortedFile.end(), sort_functor());

或者使用boost :: lambda

std::sort(unsortedFiles.begin(), 
    unsortedFile.end(),
    bind(&CFileInfo::m_FileDateTime, _1) < bind(&CFileInfo::m_FileDateTime, _2));

这是必要的信息吗？

Answer 2

对链表进行排序本质上可以是O(N ^ 2)或涉及外部随机存取存储.

向量具有随机存取存储.数组也是如此.排序可以是O(NlogN).

在1000个元素处,您将开始看到O(N ^ 2)和O(NlogN)之间的差异.在1,000,000个元素你肯定会注意到差异!

在非常特殊的情况下可以进行O(N)排序.(例如:对一副扑克牌进行排序.我们可以创建一个功能(卡片),将每张卡片映射到其分类位置.)

但总的来说,O(NlogN)和它一样好.所以你不妨使用STL的sort()!
只需添加#include <算法>

您需要添加的是运算符<().或者是一种排序函子.

但有一个建议:为了上帝的缘故,如果你打算对约会进行排序,要么将其编码为代表秒 - 自 - 纪元(mktime？)的长整数,要么至少使用"年/月/日" -hour:分钟:second.fraction"格式.(并且确保一切都是带有前导零的2(或4)位数!)比较"6/22/2008-4:34"和"12/5/2007-14:54"将需要解析!将"2008/06/22-04:34"与"2007/12/05-14:54"进行比较要容易得多.(虽然比比较两个整数的效率要低得多!)

Rich写道: 其他答案似乎进入语法更多,这是我真正缺乏的.

好.基本的"int"类型我们有:

#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << (i>0?", ":"") << DATA[i]; } cout << endl;

int
main()  
{
    // Creating and Sorting a stack-based array.
  int d [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
  PRINT(d,10);
  sort( d, d+10 );
  PRINT(d,10);

  cout << endl;

    // Creating a vector.
  int eData [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
  vector<int> e;
  for(int i=0; i<10; i++ )
    e.push_back( eData[i] );

    // Sorting a vector.
  PRINT(e,10);
  sort(e.begin(), e.end());
  PRINT(e,10);
}

有了你自己的类型,我们有:

class Data
{  
public:  
  string m_PackLine;  
  string m_FileDateTime;  
  int    m_NumberDownloads;

    /* Lets simplify creating Data elements down below. */
  Data( const string & thePackLine  = "",
        const string & theDateTime  = "",
        int            theDownloads = 0 )
      : m_PackLine        ( thePackLine  ),
        m_FileDateTime    ( theDateTime  ),
        m_NumberDownloads ( theDownloads )
    { }

    /* Can't use constructor with arrays */
  void set( const string & thePackLine,
            const string & theDateTime,
            int            theDownloads = 0 )
    {
      m_PackLine        = thePackLine;
      m_FileDateTime    = theDateTime;
      m_NumberDownloads = theDownloads;
    }

    /* Lets simplify printing out down below. */ 
  ostream & operator<<( ostream & theOstream ) const
    {
      theOstream << "PackLine=\"" << m_PackLine
                 << "\"   fileDateTime=\"" << m_FileDateTime
                 << "\"   downloads=" << m_NumberDownloads;
      return theOstream;
    }


    /*
     * This is IT!  All you need to add to use sort()!
     *  Note:  Sort is just on m_FileDateTime.  Everything else is superfluous.
     *  Note:  Assumes "YEAR/MONTH/DAY HOUR:MINUTE" format.
     */
  bool operator< ( const Data & theOtherData ) const
    { return m_FileDateTime < theOtherData.m_FileDateTime; }

};

    /* Rest of simplifying printing out down below. */ 
ostream & operator<<( ostream & theOstream, const Data & theData )
  { return theData.operator<<( theOstream ); }


    /* Printing out data set. */
#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << "[" << i << "]  " << DATA[i] << endl; }  cout << endl;

int
main()
{  
    // Creating a stack-based array.
  Data d [10];
  d[0].set( "Line 1", "2008/01/01 04:34", 1 );
  d[1].set( "Line 4", "2008/01/04 04:34", 4 );
  d[2].set( "Line 0", "2008/01/00 04:34", 0 );
  d[3].set( "Line 2", "2008/01/02 04:34", 2 );
  d[4].set( "Line 8", "2008/01/08 04:34", 8 );
  d[5].set( "Line 6", "2008/01/06 04:34", 6 );
  d[6].set( "Line 3", "2008/01/03 04:34", 3 );
  d[7].set( "Line 5", "2008/01/05 04:34", 5 );
  d[8].set( "Line 9", "2008/01/09 04:34", 9 );
  d[9].set( "Line 7", "2008/01/07 04:34", 7 );

    // Sorting a stack-based array.
  PRINT(d,10);
  sort( d, d+10 );
  PRINT(d,10);

  cout << endl;

    // Creating a vector.
  vector<Data> e;
  e.push_back( Data( "Line 1", "2008/01/01 04:34", 1 ) );
  e.push_back( Data( "Line 4", "2008/01/04 04:34", 4 ) );
  e.push_back( Data( "Line 0", "2008/01/00 04:34", 0 ) );
  e.push_back( Data( "Line 2", "2008/01/02 04:34", 2 ) );
  e.push_back( Data( "Line 8", "2008/01/08 04:34", 8 ) );
  e.push_back( Data( "Line 6", "2008/01/06 04:34", 6 ) );
  e.push_back( Data( "Line 3", "2008/01/03 04:34", 3 ) );
  e.push_back( Data( "Line 5", "2008/01/05 04:34", 5 ) );
  e.push_back( Data( "Line 9", "2008/01/09 04:34", 9 ) );
  e.push_back( Data( "Line 7", "2008/01/07 04:34", 7 ) );

    // Sorting a vector.
  PRINT(e,10);
  sort(e.begin(), e.end());
  PRINT(e,10);
}