Сортировка связанного списка будет по сути быть либо O (N^2), либо включать внешнее хранилище произвольного доступа.
Векторы имеют хранилище с произвольным доступом. Так делают массивы. Сортировка может быть O (NlogN).
В 1000 элементах вы начнете видеть разницу между O (N^2) и O (NlogN). На 1,000,000 элементов вы определенно заметите разницу!
В особых ситуациях можно получить сортировку O (N). (Например: Сортировка колоды игральных карт. Мы можем создать функцию (карту), которая отображает каждую карту в ее отсортированную позицию.)
Но в целом, O (NlogN) так же хорош, как и он. Таким образом, вы можете также использовать сортировку STL()!
Просто добавьте #include < алгоритмы >
Все, что вам нужно добавить оператор <(). Или сортирующий функтор.
Но одно предложение: ради человека бога, если вы собираетесь сортировать по дате, либо кодировать его, как долго INT, представляющий секунды-Since-эпохи, или по крайней мере использовать (указываете ей?) «год/месяц/день-час: минута: вторая. фракция» формат. (И УБЕДИТЕСЬ, что все 2 (или 4) цифры с ведущими нулями!) Сравнение «6/22/2008-4: 34» и «12/5/2007-14: 54» потребует разбора! Сравнение «2008/06/22-04: 34» с «2007/12/05-14: 54» намного проще. (! Хотя по-прежнему гораздо менее эффективны, чем сравнения двух целых чисел)
Рич писал: другие ответы, кажется, чтобы получить в синтаксис более что то, что я действительно не хватает.
Ok. С основного типа «ИНТ» мы имеем:
#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);
}
Совет стиля C++: переместите объявление Iter ближе к первому месту, которое вы его используете. Это позволяет избежать большого объема кода, в котором у вас есть неинициализированная переменная. – 2008-12-01 20:41:57