使用C++对向量或链表进行排序

Question

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

该列表当前约有1000个记录。但是，我希望它能够扩展一点以防万一。

当我使用LinkedList通过搜索整个列表来插入时，需要大约20秒。现在，只需填充向量并输出到文件需要4秒钟（听起来太长了吗）？

我想使用merge sort或quick sort（在我看来，merge sort稍微容易一些）。我遇到的问题是，我没有看到许多使用对象而不是基本数据类型实现这些排序的示例。

我可以使用vector或LinkedList。到目前为止，从这个网站得到的反馈最有帮助。我希望有人能给我撒上魔法粉，使这对我更容易 :)

任何关于如何以相当不错的性能方式完成此操作的链接或示例都将不胜感激。由于我是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;  
    }  
}  

- Rich

---

C++ 风格提示：将 Iter 的声明移动到您首次使用它的位置附近。这样可以避免出现未初始化变量的大量代码。 - Daniel Earwicker

Answer 1

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

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));

这是所需的信息吗？

- Edouard A.

Answer 2

对链表进行排序将会是O(N^2)或需要外部随机访问存储。

向量和数组具有随机访问存储。排序可以是O(NlogN)。

在1000个元素时，您将开始看到O(N^2)和O(NlogN)之间的差异。在100万个元素时，您一定会注意到这种差异！

在非常特殊的情况下，可能会获得O(N)排序。(例如：对扑克牌进行排序。我们可以创建一个函数(card)，将每张卡映射到其排序位置。)

但是一般来说，O(NlogN)就是最好的了。所以你最好使用STL的sort()！
只需添加#include <algorithms>

---

您只需要添加一个operator<()或一个sort functor。

但是一个建议：天哪，如果您要按日期排序，请将其编码为表示自纪元以来的秒数的long int (mktime?)，或者至少使用"年/月/日-小时:分钟:秒.分数"格式。(并确保所有内容都是带前导零的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);
}

- Mr.Ree

---

排序链表的时间复杂度为_O(n²)_是从什么时候开始的呢？快速排序只需要双向迭代，因此在双向链表上（std::list是双向链表）与随机访问容器一样有效；而归并排序需要额外的存储空间，但它需要原始存储和额外存储都是前向可迭代的。 - Jan Hudec

Answer 3

STL头文件中有一个排序算法。

 <algorithm>

这是SGI手册的链接。

- Paul Nathan

Answer 4

在algorithm头文件中使用std::sort：

如果您为CFileInfo定义了运算符<，那么它应该可以正常工作。

或者，定义一个执行比较的函数对象，并将其作为单独的参数传递给sort函数。

- jalf

Answer 5

Rich -- 回答你最近的问题（而不是你最初的问题），最好/最简单的方法可能是使用sscanf()解析日期。理想情况下，你希望一开始就将其以数字形式存储。

对于一个"YYYY/MM/DD-HH:MM"字符串，你可以直接比较字符串。所有字符串的长度都相同，并且在从左到右读取时，你正在按照从最大时间增量到最小时间增量的顺序进行比较。

但是，比较字符串非常低效！

通常，日期以自1970年1月1日00:00:00 UTC以来的秒数为单位的time_t（整数）值存储。

mktime()或timegm()（如果你有timegm）将从你提供的"struct tm"构造一个time_t值。

示例代码：

#define SHOW(X)  cout << # X " = " << (X)

int
main()
{
  const string s = "2008/12/03 12:48";
  struct tm    datetime;
  time_t       t;

  memset( & datetime, 0, sizeof(datetime) );

  if ( 5 != sscanf( s.c_str(), "%d/%d/%d %d:%d",
                    & datetime.tm_year,
                    & datetime.tm_mon,
                    & datetime.tm_mday,
                    & datetime.tm_hour,
                    & datetime.tm_min  ) )
  {
    cout << "FAILED to parse:  \"" << s << "\"" << endl;
    exit(-1);
  }

    /* tm_year - The number of years since 1900. */
  datetime.tm_year -= 1900;

    /* tm_mon - The number of months since January, in the range 0 to 11. */
  datetime.tm_mon --;

    /* tm_mday - The day of the month, in the range 1 to 31. */
    /* tm_hour - The number of hours past midnight, in the range 0 to 23. */
    /* tm_min - The number of minutes after the hour, in the range 0 to 59. */
  // No change.

  /* If using mktime, you may need these to force UTC time:
   *   setenv("TZ","",1);
   *   tzset();
   */

  t = mktime( & datetime );

  SHOW( t ) << endl;
  SHOW( asctime( & datetime ) );
  SHOW( ctime( & t ) );
}

现在给定两个时间（日期）值，例如time_t t1, t2，您可以使用t1<t2进行比较。

- Mr.Ree